做一道面试题

2,巧排数字,将1,2,...,19,20这20个数字排成一排,使得相邻的两个数字之和为一个素数,且
首尾两数字之和也为一个素数。编程打印出所有的排法。

初一看,我以为很简单,又是那种教科书章节后面习题式的题目,再一想,发现没那么简单.最简单和最暴力的做法是,枚举所有可能的排列组合,然后依次验证,符合条件的就打印出来,所有可能是20的阶乘,而且怎么实现呢?可能是这样,第一层循环,遍历1到20,第二层循环,遍历1到20中不等于第一层循环的数....这太可怕了,完全无法想象.必须另想办法.

为了便于思考,将问题的规模缩小,比如1到5,这里面的两个数相加,最大值是9,可能是素数是3 5 7,很明显,相加能够得到素数的组合是有限的,例如2+4就不应该考虑,只有相加能够落在3 5 7这个范围的数对才有意义,我将这样的数对称为pair,一个pair就是一个二维数组.排列的时候应该以pair为单位,而不是以单个数字为单位.可以列出3 5 7对应的pair如下

3 5 7
12
14
16
23
25
32
34
41
43
52

显然,这些数对是进行排列组合的基本单位,如果第一个pair是12,那么如何寻找下一个数?只能是到以2开头的pair中去找,我将pair中第二个数叫做rightside,找第三个数的方法是这样,遍历以2开头的pair,如果pair的rightside不等于前面已经排列的数,那么将这个数加入到排列中,根据这个rightside的值找到以rightside开头的pair组,进行和上次循环同样的操作,这是一个递归模型.而且保存排列的数据结构很适合用栈,对于所有的pair,只要将第一个数和第二个数推入栈,那么下面的动作都是同样的方法.顺着这个思路写了一个程序,可以运行,但是没有任何结果,原来是12345的任何组合都不符合规定的要求,所以我直接采用1到20,这次结果有多的出乎想象.代码如下

/*--
 * 题:排列1到n,使之每个相邻数之和为素数,首尾之和为素数,以1到5为例
 * 1到5似乎没有这样的组合,
 * 改为1到20,结果似乎过于庞大,如果输出到文本文件,有几十M
 * 而且是提前按下了CTRL + C,全部的结果可能是个天文数字
 *
 * Author: 张
 * 
++*/
#include <iostream>
using namespace std;
const int 20;
typedef struct _pair
{
  
int length;
  
int pairs[7][2];
numpair;
  
int stack[n];
  
int top = -1;

  
void recursive();
  
struct _pair pair1 = {7,{{1,2},{1,4},{1,6},{1,10},{1,12},{1,16},{1,18}}};
/*  pair1.length = 2;
  pair1.pairs[0][0] = 1;
  pair1.pairs[0][1] = 2;
  pair1.pairs[1][0] = 1;
  pair1.pairs[1][1] = 4;
*/
  
numpair pair2={7,{{2,1},{2,3},{2,5},{2,9},{2,11},{2,15},{2,17}}};
  
numpair pair3={7,{{3,2},{3,4},{3,8},{3,10},{3,14},{3,16},{3,20}}};
  
numpair pair4={7,{{4,1},{4,3},{4,7},{4,9},{4,13},{4,15},{4,19}}};
  
numpair pair5={6,{{5,2},{5,6},{5,8},{5,12},{5,14},{5,18}}};
  
numpair pair6={6,{{6,1},{6,5},{6,7},{6,11},{6,13},{6,17}}};
  
numpair pair7={5,{{7,4},{7,6},{7,10},{7,12},{7,16}}};
  
numpair pair8={5,{{8,3},{8,5},{8,9},{8,11},{8,15}}};
  
numpair pair9={6,{{9,2},{9,4},{9,8},{9,10},{9,14},{9,20}}};
  
numpair pair10={6,{{10,1},{10,3},{10,7},{10,9},{10,13},{10,19}}};
  
numpair pair11={6,{{11,2},{11,6},{11,8},{11,12},{11,18},{11,20}}};
  
numpair pair12={5,{{12,1},{12,5},{12,7},{12,11},{12,17}}};
  
numpair pair13={5,{{13,4},{13,6},{13,10},{13,16},{13,18}}};
  
numpair pair14={5,{{14,3},{14,5},{14,9},{14,15},{14,17}}};
  
numpair pair15={5,{{15,2},{15,4},{15,8},{15,14},{15,16}}};
  
numpair pair16={5,{{16,1},{16,3},{16,7},{16,13},{16,15}}};
  
numpair pair17={5,{{17,2},{17,6},{17,12},{17,14},{17,20}}};
  
numpair pair18={5,{{18,1},{18,5},{18,11},{18,13},{18,19}}};
  
numpair pair19={4,{{19,4},{19,10},{19,12},{19,18}}};
  
numpair pair20={4,{{20,3},{20,9},{20,11},{20,17}}};
  
//pair2.length = 
  //
  //1-based
  
numpair pairs[n+1] = {pair1,pair1,pair2,pair3,pair4,pair5,pair6,pair7,
  
pair8,pair9,pair10,pair11,pair12,pair13,pair14,pair15,pair16,pair17,
  
pair18,pair19,pair20};

int main()
{


  
int 0;
  
int 0;

  
for<= i++)
  {
    
for (pairs[i].length j++)
    {
      
top++;
      
stack[top] = pairs[i].pairs[j][0];
      
top++;
      
stack[top] = pairs[i].pairs[j][1];
      
recursive();
      
top--;
      
    }
  }


  
for(pair1.length i++ )
  {
    
for(j++)
      
cout << pair1.pairs[i][j];
  }
  
  
return 0;
}
void recursive()
{
  
if(top == n-1)
  {
    
int z;
    
for (z=0pairs[stack[top]].length;z++)
    {
      
if(stack[0] == pairs[stack[top]].pairs[z][1]) break;
    }
    
if (pairs[stack[top]].length)
    {
      
//ok ,we find it
      
int k;
      
for (k=0;<= topk++)
        
cout << stack[k] << " " ;
      
cout << endl;
    }
    
    
top--;
    
return;
  }
  
int x;
  
for (x  pairs[stack[top]].length;x++)
  {
    
int rightside pairs[stack[top]].pairs[x][1];
    
int 0;
    
for (<= top y++)
    {
      
if(rightside == stack[y]) break;
    }
    
if(<= topcontinue;
    
else
    
{
      
//should recursive
      
top++;stack[top] = rightside;
      
recursive();
    }
  }
  
//这里top只是局部变量在自减,没有起作用,改为全局变量
  
top--;

}

说明:main中的循环应该很好理解,recursive中,for(y=0 ... 是检查当前的righside是否和栈中的数字重复,如果不重复,则入栈,并递归,否则continue.当栈满了之后,需要检查首尾之和是否为素数,方法是检查第一个数是否在当前栈顶所指向的pairs数组的rightside之中,如果成立,ok,找到一个排列,打印输出.

总算有一个勉强能用的方案,不过这是面试题,真的到了那个场合,不会有这么多时间用来实现,不知道有没有更好的方法可以当场实现的.

update:23:21 2011-3-2

总算又连通了网络,想看看还有没有别的方法,搜了一下,原来这是个很著名的题目,解法就更多了.看了几个算法,有些新的认识了.理论上,这是一个回溯问题,或者,深度优先的完全搜索,名字听起来似乎很复杂,其实就是栈的一种应用,各种算法都不同程度的用到了栈,每次退栈就是一次回溯.不管各种算法的形式有何区别,其本质是一样的.我的这个版本里面,recursive函数每次返回都是一次回溯,每次进入都是一次深度优先的前进.任何时候recursive函数都是处在某一个深度层次,并遍历该层次的所有可能解.如果递归不变量来解释,那么在任何递归的层次中有以下量是确定的:top的值代表当前的深度,pairs[stack[top]]所对应的数组是所有可能解的范围,函数的任务很明确:遍历每一个解,如果合适的,就加入栈中并递归,深度又增加一层,下一次是同样的动作,不变量也是同样的含义.发生回溯只有两种情况,一是找到一个排列,而是当前深度的所有可能解都已经遍历.