题目：巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之 和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。
先说下这道题的思路，肯定是应该用回溯的方法。穷举则运算的量太大不适合，而递归空间复杂度也太大。
先放入第一个数 1，然后依次放入2、3、4···，每次放入时判断与前一个数之和是否为素数，若是则继续放入，若不是则回退一步，选后一个数。这样直到放完。
伪算法：
0. 初始化 标记所有数在每个位置都能放置。
1. 从剩下的数选最小的一个且能在此位置放置的，放入数组，若没有数满足到3，若已放完到4.
2. 判断放入的数与前一个数之和是否为素数（第一个不判断，最后一个要与它前一个和第一个数判断） 是素数回到1，不是素数，标记此数不能在这个位置放置到1.
3. 回退一步，即将前面一个数取出，并且标记此位置之后的位置，所有数都能放置。到1.
4. 打印出结果。到5.
5. 判断是否退空，若没退空到3.。退空结束。
这里我将放数，退数模仿成进栈、出栈。然后输出结果到文件时声明了
一个友元函数，方便一些。
下面是源代码 ( 编译器 VC++ 8.0 )
// Stack.h #ifndef STACK_H #define STACK_H class Stack{ public : Stack(); bool Push(); bool Pop(); void Display(); bool IsFull(); int GetTop(); long TheCount(); friend void FileDisplay( const Stack & ); // 输出到文件 private : bool IsPrime( int ); private : long count; // 解数 int top; int value[ 21 ]; // 结果 bool state[ 21 ][ 21 ]; // 状态 [位置][数] }; #endif // STACK_H /// :~// Stack.cpp #include " Stack.h " #include < iostream > #include < fstream > #include < cstring > // memset() #include < math.h > using namespace std;Stack::Stack(){ memset(value, 0 , 21 * sizeof ( int )); memset(state, true , 21 * 21 * sizeof ( bool )); top = 0 ; count = 0 ;} void Stack::Display(){ for ( int i = 1 ;i <= 20 ;i ++ ) cout << value[i] << " " ; cout << endl;} bool Stack::IsFull(){ return (top == 20 );} bool Stack::Push(){ if (top == 20 ) // 已填完 return false ; top ++ ; for ( int i = 1 ;i <= 20 ;i ++ ) { // 测试i是否满足 if (state[top][i]) { bool flag = true ; for ( int j = 1 ;j < top;j ++ ) { // 判断前面是否用过此数 if (value[j] == i) { flag = false ; break ; } } if (flag) { if (top == 20 ) { if ( ! IsPrime(i + value[ 1 ])) // 最后一个数要判断与第一个数之和是否为素数 { state[ 20 ][i] = false ; continue ; } } if (IsPrime(i + value[top - 1 ])) // 判断与其前一个数之和是否为素数 { state[top][i] = false ; value[top] = i; if (top == 20 ) count ++ ; // 填完 return true ; } else { state[top][i] = false ; } } } } top -- ; return false ; // 没有满足条件的数 返回false } bool Stack::Pop(){ if (top == 0 ) // 栈空返回false return false ; state[top][value[top]] = false ; memset(state[top + 1 ], true , 21 * sizeof ( int )); // 其后位置所有数可再用 value[top] = 0 ; top -- ; return true ;} bool Stack::IsPrime( int e){ if (e % 2 == 0 ) return false ; for ( int i = 3 ;i <= sqrt(( float )e);i += 2 ) { if (e % i == 0 ) return false ; } return true ;} int Stack::GetTop(){ return top;} long Stack::TheCount(){ return count;} void FileDisplay( const Stack & a){ ofstream out ( " Answer.txt " ,std::ios_base::app); out << " No. " << a.count << endl; for ( int i = 1 ;i <= 20 ;i ++ ) out << a.value[i] << " " ; out << endl;}
memset(char* ,value,long)这个函数初始化比较快一点，它把起始于某一特定地址的内存(该内存作为第一个参数)从起始地址直至气候的n(n作为第三个参数)个字节的所有内存都设置成同一个特定的值(该值作为第二个参数)
// main.cpp #include < iostream > #include " Stack.h " using namespace std; int main(){ Stack a; bool s = true ; while (s) // 循环直到栈空，即不能再回退，则所有已测试完 { if (a.Push()) { /* 继续往内填数 */ } else { s = a.Pop(); // 不能再填则回退一步 } if (a.IsFull()) { FileDisplay(a); } } return 0 ;}
这个结果共有1千多万组，这是不考虑相对位置即不把它看成一个圆。
若有高手有更好算法，还请指点。
