ios程序员面试宝典七

时间：2024-11-04 20:35:07 学人智库我要投稿

相关推荐

ios程序员面试宝典（七）

经典试题主要是一些经典的算法题。例如，八皇后问题，经典矩形生成和汉诺塔大数乘法等。通过本小节可以了解这些经典题目的一种求解方式。

ios程序员面试宝典（七）

面试题194 八皇后问题

【出现频率】★★★ 【关键考点】

 八皇后问题介绍;  回溯法介绍;

 八皇后问题算法分析。【考题分析】

八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出：在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格;要求皇后之间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法?

回溯算法也叫试探法，它是一种搜索问题的解的方法。回溯算法的基本思想是在一个包含所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

八皇后问题有很多中解法，其中使用回溯法进行求解是其中一种。而回溯发也是最直接的一种解法，也较容易理解。

八皇后问题的回溯法算法，可以采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。例如，a[1]=5，表示在棋盘的第一例的第五行放一个皇后。程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。

【答案】

八皇后问题可以使用回溯法进行求解，程序实现如下：

#include

#define Queens 8 //定义结果数组的大小，也就是皇后的数目

int a[Queens +1]; //八皇后问题的皇后所在的行列位置，从1开始算起，所以加1 int main() { int i,k,flag,not_finish=1,count=0; //正在处理的元素下标，表示前i-一个元素已符合要求，正在处理第i个元素 i=1; a[1]=1; //为数组的第一个元素赋初值 printf("The possible configuration of 8 queens are: "); while(not_finish) //not_finish=1:处理尚未结束 { while(not_finish&&i<=Queens ) //处理尚未结束且还没处理到第Queens 个元素 { for(flag=1,k=1;flag&&k1&&a[i]==Queens ) a[i]=1; //当a[i]为Queens 时将a[i]的值置 else if(i==1&&a[i]==Queens ) not_finish=0; //当第一位的值达到Queens 时结束 else a[i]++; //将a[i]的值取下一个值 } else if(a[i]==Queens ) a[i]=1; else a[i]++; //将a[i]的值取下一个值 } else if(++i<=Queens ) if(a[i-1]==Queens ) a[i]=1; //若前一个元素的值为Queens 则a[i]=1 else a[i]=a[i-1]+1; //否则元素的值为前一个元素的下一个值 } if(not_finish) { ++count; printf((count-1)%3?" [%2d]: ":" [%2d]: ",count); for(k=1;k<=Queens k++) //输出结果 printf(" %d",a[k]); if(a[Queens -1]<queens p="" else<="" queens="">

a[Queens -1]=1;

i=Queens -1; //开始寻找下一个满足条件的解 } }

}

面试题195 经典矩形

【出现频率】★★★ 【关键考点】

 经典矩形问题介绍;  特点分析。【考题分析】

经典矩形问题指的是利用数字生成一个矩阵，而该矩阵刚好是一个正方形。该矩阵内的数字是有规律的排序而形成矩形。比较常见的有以下几种形式。

第1种矩阵的形式，如下：

11 12 19 10 14 13 18 11 15 16 17 12 16 15 14 13

第2种矩阵的形式，如下：

11 12 16 17 13 15 18 13 14 19 12 14 10 11 15 16

第3种矩阵的形式，如下：

11 12 13 4 12 13 14 5 11 16 15 6 10 19 18 7

第4种矩阵的形式，如下：

17 16 15 16 18 11 14 15 19 12 13 14 10 11 12 13

【答案】

根据矩阵的特点，可以使用以下程序输出上述矩阵：

void Rectangle1() { const int N=20;

int i=0,j=0,a[N][N]; int lap=1,m=1,n;

while(1) //开始循环 {

cout<<" 请输入矩阵的行数N(N>=2): "; cin>>n;

cout<< p="">

if(n>=2) break; }

cout<<"第1种矩形："<<endl; p="" lap++;<="">

while(lap<=n) {

if(lap%2==0) {

for(j++;i<lap;i++) p="" a[i][j]="m++;" i--;<="">

for(j--;j>=0;j--) a[i][j]=m++;j++; } else {

for(i++;j<lap;j++) p="" a[i][j]="m++;" j--;<="">

for(i--;i>=0;i--) a[i][j]=m++;i++; }

lap++; }

for(i=0;i<n;i++) p="" {<="">

for(j=0;j< p="">

cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; p="" }<="" cout<

cout<< p="">

int nSnake[N][N];

cout<<"第2种矩形："<<endl; p="" 开始输出矩阵="" {<="" s="1,nNum=1;" int="" i="0,j=0;">

if(s==1) {

nSnake[i][j]=nNum; if(i-1<0) {

if(j+1==n) i++; lse j++; s=-1; } else

if(j+1==n) {

i++; s=-1;

} else {

i--; j++; } } else {

nSnake[i][j]=nNum; if(j-1<0) {

if(i+1==n) j++; else i++; s=1; } else

if(i+1==n) {

j++; s=1; }

else {

i++; j--; } }

nNum++;

if(nNum>n*n) break; }

for(i=0;i<n;i++) p="" {<="">

for(j=0;j< p="">

cout<<setw(4)<<setiosflags(ios::left)<<nsnake[i][j]; p="" }<="" cout<

cout<< p="">

cout<<"第3种矩形："<

int x1,x2,y1,y2; //x1，x2，y1，y2为上、下、左、右边界 m=1,s=1; //s标记数组元素升降，s==1为升，s==-1为降 x1=0;y1=0;x2=n;y2=n; while(1) {

if(s==1) {

for(j;j<y2;j++) {="" a[i][j]="m++;" s="-1;" for(j;j="" else="" }="" i--;j--;x2--;="" for(i;i=y1;j--) a[i][j]=m++; j++;i--;y1++;

for(i;i>=x1+1;i--) a[i][j]=m++; i++;j++;x1++; s=1; }

if(m>n*n) break; }

for(i=0;i<n;i++) p="" {<="">

for(j=0;j< p="">

cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; p="" }<="" cout<

cout<< p="">

cout<<"第4种矩形："<

x1=0;y1=0;x2=n;y2=n;

if(n%2==0) //求余 {j=n-1;y2=n-1;s=1;} else

{i=n-1;y1=1;s=-1;} while(1) {

if(s==1) {

for(i;i=y1;j--) a[i][j]=m--; j++;i--;y1++; s=-1; } else {

for(i;i>=x1;i--) a[i][j]=m--; i++;j++;x1++; for(j;j<y2;j++) p="" a[i][j]="m--;" }<="" s="1;">

if(m<1) break; }

for(i=0;i<n;i++) p="" {<="">

for(j=0;j< p="">

cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; p="" }<="" cout<

cout<< p="">

[ios程序员面试宝典（七）]

【ios程序员面试宝典七】相关文章：

iOS开发设计程序员面试题(2)09-30

iOS开发/设计程序员面试题汇总09-13

iOS面试题07-10

100个iOS开发/设计程序员面试题07-31

iOS面试题集合06-25

ios基础面试题07-28