|
|
簡單而且經(jīng)典的搜索題，用回溯做。對于什么是回溯什么是DFS我分不清。就是按位逐個判斷，直到找到結(jié)果，或者出界退出。
 #include<iostream>
#include<cmath>
using namespace std ;
int n, a[111], k, ans[22], anscnt ;
  int p[42]=  {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0,
 0,0,23,0,0,0,0,0,29,0,31,0,0,0,0,0,37,0,0,0,41} ;
int rev[100][20], revcnt ;
void DFS( int m, int geshu )
{
 int i, j ;
  if( geshu == n && p[1+m] ){
cout << ans[0] ;
for( i=1; i<n; ++i ){
cout << " " << ans[i] ;
rev[revcnt][i] = ans[i] ;
 }
++revcnt ;
cout << "\n" ;
}
else if( geshu == n )
return ;
for( j=2; j<=n; ++j ){
if( j<p[j+m] && !a[j] ){
a[j] = 1 ;
ans[geshu] = j ;
DFS( j, geshu+1 ) ;
a[j] = 0 ;
}
}
}
int main( )
{
int i, j ;
for( j=1; cin >> n; ++j ){
cout << "Case "<< j << ":\n" ;
for( i=0; i<111; ++i )
a[i] = 0 ;
revcnt = 0 ;
k = 1 ;
ans[0] = 1 ;
anscnt = 1 ;
DFS( 1, 1 ) ;
cout << "\n";
}
return 0 ;
}
|