C C++程序员面试宝典——第17章 思维拓展

第3篇C/C++专业应用·224·第17章思维拓展本章主要介绍一些面试时与思维拓展相关的内容，例如一些经典常见的问题的算法的实现、面试经验分享以及群体面试这种情况地介绍解答。通过本章可以知道除了专业知识以外，在面试时也会遇到其他的情况，例如多个考官的群体面试如何应对等。应试者可以根据自己的实际情况，有目的地加强这些方面能力。17.1经典试题经典试题主要是一些经典的算法题。例如，八皇后问题，经典矩形生成和汉诺塔大数乘法等。通过本小节可以了解这些经典题目的一种求解方式。面试题194八皇后问题【出现频率】★★★【关键考点】八皇后问题介绍；回溯法介绍；八皇后问题算法分析。【考题分析】八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出：在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后之间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法？回溯算法也叫试探法，它是一种搜索问题的解的方法。回溯算法的基本思想是在一个包含所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。八皇后问题有很多中解法，其中使用回溯法进行求解是其中一种。而回溯发也是最直接的一种解法，也较容易理解。八皇后问题的回溯法算法，可以采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。例如，a[1]=5，表示在棋盘的第一例的第17章思维拓展·225·第五行放一个皇后。程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。【答案】八皇后问题可以使用回溯法进行求解，程序实现如下：#includestdio.h#defineQueens8//定义结果数组的大小，也就是皇后的数目inta[Queens+1];//八皇后问题的皇后所在的行列位置，从1开始算起，所以加1intmain(){inti,k,flag,not_finish=1,count=0;//正在处理的元素下标，表示前i-一个元素已符合要求，正在处理第i个元素i=1;a[1]=1;//为数组的第一个元素赋初值printf(Thepossibleconfigurationof8queensare:\n);while(not_finish)//not_finish=1:处理尚未结束{while(not_finish&&i=Queens)//处理尚未结束且还没处理到第Queens个元素{for(flag=1,k=1;flag&&ki;k++)//判断是否有多个皇后在同一行if(a[k]==a[i])flag=0;for(k=1;flag&&ki;k++)//判断是否有多个皇后在同一对角线if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))flag=0;if(!flag)//若存在矛盾不满足要求，需要重新设置第i个元素{if(a[i]==a[i-1])//若a[i]的值已经经过一圈追上a[i-1]的值{i--;//退回一步，重新试探处理前一个元素if(i1&&a[i]==Queens)a[i]=1;//当a[i]为Queens时将a[i]的值置elseif(i==1&&a[i]==Queens)not_finish=0;//当第一位的值达到Queens时结束elsea[i]++;//将a[i]的值取下一个值}elseif(a[i]==Queens)a[i]=1;elsea[i]++;//将a[i]的值取下一个值}elseif(++i=Queens)if(a[i-1]==Queens)a[i]=1;//若前一个元素的值为Queens则a[i]=1elsea[i]=a[i-1]+1;//否则元素的值为前一个元素的下一个值}if(not_finish){++count;printf((count-1)%3?[%2d]::\n[%2d]:,count);for(k=1;k=Queens;k++)//输出结果printf(%d,a[k]);if(a[Queens-1]Queens)第3篇C/C++专业应用·226·a[Queens-1]++;//修改倒数第二位的值elsea[Queens-1]=1;i=Queens-1;//开始寻找下一个满足条件的解}}}面试题195经典矩形【出现频率】★★★【关键考点】经典矩形问题介绍；特点分析。【考题分析】经典矩形问题指的是利用数字生成一个矩阵，而该矩阵刚好是一个正方形。该矩阵内的数字是有规律的排序而形成矩形。比较常见的有以下几种形式。第1种矩阵的形式，如下：11121910141318111516171216151413第2种矩阵的形式，如下：11121617131518131419121410111516第3种矩阵的形式，如下：1112134121314511161561019187第4种矩阵的形式，如下：17161516181114151912131410111213【答案】根据矩阵的特点，可以使用以下程序输出上述矩阵：voidRectangle1(){constintN=20;第17章思维拓展·227·inti=0,j=0,a[N][N];intlap=1,m=1,n;while(1)//开始循环{cout\n请输入矩阵的行数N(N=2):;cinn;coutendl;if(n=2)break;}cout第1种矩形：endl;//开始输出矩阵a[i][j]=m++;lap++;while(lap=n){if(lap%2==0){for(j++;ilap;i++)a[i][j]=m++;i--;for(j--;j=0;j--)a[i][j]=m++;j++;}else{for(i++;jlap;j++)a[i][j]=m++;j--;for(i--;i=0;i--)a[i][j]=m++;i++;}lap++;}for(i=0;in;i++){for(j=0;jn;j++)coutsetw(4)setiosflags(ios::left)a[i][j];coutendl;}coutendl;intnSnake[N][N];cout第2种矩形：endl;//开始输出矩阵i=0,j=0;ints=1,nNum=1;//s标记升降方向，斜向上为升(s==1)，斜向下为降(s==-1)while(1){if(s==1){nSnake[i][j]=nNum;if(i-10){if(j+1==n)i++;lsej++;s=-1;}elseif(j+1==n){i++;第3篇C/C++专业应用·228·s=-1;}else{i--;j++;}}else{nSnake[i][j]=nNum;if(j-10){if(i+1==n)j++;elsei++;s=1;}elseif(i+1==n){j++;s=1;}else{i++;j--;}}nNum++;if(nNumn*n)break;}for(i=0;in;i++){for(j=0;jn;j++)coutsetw(4)setiosflags(ios::left)nSnake[i][j];coutendl;}coutendl;cout第3种矩形：endl;//开始输出矩阵i=0,j=0;intx1,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;jy2;j++)a[i][j]=m++;j--;i++;y2--;for(i;ix2;i++)a[i][j]=m++;i--;j--;x2--;s=-1;}else{第17章思维拓展·229·for(j;j=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(mn*n)break;}for(i=0;in;i++){for(j=0;jn;j++)coutsetw(4)setiosflags(ios::left)a[i][j];coutendl;}coutendl;cout第4种矩形：endl;//开始输出矩阵i=0,j=0;m=n*n;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;ix2;i++)a[i][j]=m--;i--;j--;x2--;for(j;j=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;jy2;j++)a[i][j]=m--;j--;i++;y2--;s=1;}if(m1)break;}for(i=0;in;i++){for(j=0;jn;j++)coutsetw(4)setiosflags(ios::left)a[i][j];coutendl;}coutendl;//输出结束标志}第3篇C/C++专业应用·230·面试题196汉诺塔【出现频率】★★★★【关键考点】汉诺塔简介；汉诺塔算法。【考题分析】汉诺塔问题描述：有3根杆子A、B、C。A杆上有若干碟子，碟子按照从小到大的顺序从上往下放。目标是将A杆上的碟子全部移到C杆上，而且移动后碟子的顺序和原来A杆上一样是有序的。在移动的过程中，每次只能移动一个碟子，而且小的只能叠在大的上面。求如何移动碟子的方法。汉诺塔问题是一个经典的递归问题。利用递归的算法进行实现，比较简单。例如，要将m个碟子从A移动到C，可以认为如果能够先将m－一个碟子移动到B，再将A剩下的最大的碟子移动到C，然后再将B上的m－一个碟子移动到C即可。【答案】前面在第4章曾经介绍过汉诺塔的递归代码，这里使用最简略的代码如下：#includeiostream#includestringvoidHanno(inti,stringa,stringb,stringc);intmain(){cout输入要移动的数目:;intn;cinn;coutendl;Hanno(n,A,B,C);}voidHanno(inti,stringa,stringb,stringc){if(i==1){coutacendl;//当只有一个碟子时直接将其从A移动到C}else{Hanno(i-1,a,c,b);//将i－一个碟子从A借助C移动到Bcoutacendl;//将A剩下的最大的碟子移动到CHanno(i-1,b,a,c);//将i－一个碟子从B借助A移动到C}}注意：虽然递归算法是最直接的算法，也是比较容易理解的。但是在一些系统资源紧缺的设备上进行开发时，使用递归算法很可能导致资源耗尽。因此需要根据具体的情况对算法进行优化，减少递归的使用。第17章思维拓展·231·面试题197新娘和新郞问题【出现频率】★★★【关键考点】问题介绍；算法分析。【考题分析】问题介绍：3对情侣参加婚礼，3