【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

【

算法分析

】

解空间：从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；

约束条件：与左边相邻的数的和是一个素数，且没有被用过。

边界条件：第20个数还要判断和第1个数的和是否素数，是就输出，不是就回溯

【算法流程】

1、数据初始化；  

2、递归填数：判断第i个数填入是否合法；

A、如果合法：填数；

     判断是否到达目标（20个已填完）：是，打印结果；

     不是，递归填下一个；

B、如果不合法：选择下一种可能；

代码：

1 #include
        
          2 #include
         
           3 #include
          
             4 using namespace std; 5  6 int a[10],tot=0; 7 bool b[10]; 8  9 bool su(int x,int y){10     if(x==1) return 1;11     int k=2;int i=x+y;12     while(k<=sqrt(i)&&i%k!=0)k++;13     if(k>sqrt(i)) return 1;14     else return 0;15 }16 17 int print(){18     tot++;19     for(int i=1;i<=6;i++){20         cout<
           
            <<" ";21     }cout<
           
          
         
        

【例

2

】

设有

n

个整数的集合｛

1,2,

…

,n

｝，从中取出任意

r

个数进行排列（

r<n

），试列出所有的排列。

 

【算法分析】

解空间：从第1个位置开始，每个空位有n种选择

约束条件：只要没有被用过就可

边界条件：够了r 个数就可以输出

代码：

1 #include
           
             2 #include
            
              3 using namespace std; 4  5 int a[10],n,r,tot; 6 int b[10]; 7  8 int print(){ 9     tot++;10     for(int i=1;i<=r;i++)11       cout<
             
              <<" ";12     cout<
              
               >n>>r;30     Search(1);31     cout<
               
                <
               
              
             
            
           

【例

2

扩展

】

设有

n

个整数的集合｛

1,2,

…

,n

｝，从中取出任意

r

个数进行组合（

r<n

），试列出所有的组合。

代码：

1 #include
            
              2 #include
             
               3 using namespace std; 4  5 int a[100],n,m,tot; 6 bool b[100]; 7  8 int Search(int k){ 9     if(k>m){10         tot++;11         for(int i=1;i<=m;i++){12             cout<
              
               <<" ";13         }cout<
               
                =a[k-1]&&!b[i]){18                 a[k]=i;19                 b[i]=true;20                 Search(k+1);21                 b[i]=false;22             }23     }24 }25 26 int main(){27     cin>>n>>m;28     Search(1);29     cout<
                
                 <
                
               
              
             
            

【例

3

】

任何一个大于

1

的自然数

n

，总可以拆分成若干个小于

n

的

自然数之和。

【问题分析】

（1）本题需要注意，任给自然数n，能否给出所有不同的拆分。

10=3+7与10=7+3是同一种拆分。

（2）如何求出所有的拆分。

下面分析拆分过程：

取n=7来说明：

第一步：将n拆分为2项之和

7=1+6

7=2+5

7=3+4

拆分的特点是第2个加数总大于第1个加数。

第二步：只要第2个加数仍然大于1，就可按第一步重复拆分，例如：

7=1+6 可以继续拆分获得

7=1+1+5

7=1+2+4

7=1+3+3

其中7=1+1+5又可继续拆分获得

7=1+1+1+4

7=1+1+2+3

 

..................

 

最后获得共14种拆分法

 

1 #include
              
                2 #include
               
                 3 using namespace std; 4  5 int a[100],n,tot=1; 6  7 int print(int t){ 8     /*tot++;*/ 9     cout<
                
                 <<"=";10     for(int i=1;i<=t-1;i++){11         cout<
                 
                  <<"+";12     }cout<
                  
                   <
                   
                    =a[t-1]&&i
                    
                     >n;29 Search(n,1);30 /*cout<
                     
                      <
                     
                    
                   
                  
                 
                
               
              

例4：n皇后问题

   在n×n的国际象棋棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,需满足的条件是：

  同一行、同一列、同一对角线上只能有一个皇后。求所有满足要求的放置方案。当n=4时有2种放置方法

（2，4，1，3），（3，1，4，2）

 

算法描述：

1.产生一种新放法

2.冲突，继续找，直到找到不冲突----不超范围

3.if 不冲突 then   k<nàk+1

                k=nà一组解

4.if 冲突 then 回溯

 

1 #include
                
                  2 #include
                 
                   3 using namespace std; 4  5 bool b[100],c[100],d[100]; 6 int a[100],n,tot; 7  8 int print(){ 9     tot++;10     for(int i=1;i<=n;i++){11         cout<
                  
                   <<" ";12     }cout<
                   
                    >n;34     Search(1);35     cout<
                    
                     <