回溯法---四皇后+桥本分数式（回溯模板应用）

为了提升自己，同时也为了比赛做准备，我又开始学起了算法

回溯算法模板（超有用，对于这类题直接套模板就好）//适合情景——————>>>>>需要暴力计算的题

/*输入正整数n,m（n>m）    */ 

i=1;a[i]=元素初值；
while(1)
{
    
    g=1;
    for(k=i-1;k>=1;k--)
        if(<约束条件1>)
            g=0;
    if(g&&<约束条件2>)
        cout<<"有效解"<<endl;
    
    if(i<n&&g)    //如果个数不足，接着往下算 
    {
        i++;
        a[i]=<取值点始点>;
        continue;
    } 
    while(a[i]==<回溯点>&&i>1)i--;        //向前回溯 
    if(a[i]==n&&i==1) 
        break;                            //回溯到头了，结束回溯 
    else
        a[i]=a[i]+1;
}

View Code

下面是具体题目的应用：

　　四皇后题---->可推广至n皇后

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n,i,a[10];
 8     int g,k;
 9     n=4;i=1;
10     a[i]=1;
11     while(1){
12         g=1;
13         for(k=i-1;k>=1;k--)
14             if(a[i]==a[k]||abs(a[i]-a[k])==i-k)//不能同行且不能为45度 
15                 g=0;
16         //输出解 
17         if(g&&i==4)
18         {    
19             for(i=1;i<5;i++)
20                 cout<<a[i];
21                 cout<<endl;
22         }
23         if(i<n&&g){
24             i++;
25             a[i]=1;
26             continue;
27         }
28         while(a[i]==n&&i>1)i--;        //向前回溯 
29         if(a[i]==n&&i==1)
30             break;                    //退出循环 
31         else
32             a[i]=a[i]+1;
33         
34         
35     }
36     return 0; 
37 }

View Code

　　桥本分数式：

　　日本数学家桥本吉彦教授于1973年10月在我国山东举行的中日美三国数学教育研讨会上向与会者提出以下填数趣题：

　　把1,2, . . . 9这9个数填入下列算式的9个方格中(数字不得重复)，使下列等式成立。

口口口

——— + ——— = ———

口口口口口口
　　桥本教授当即给出了一个解答，这一填数趣题的解是否唯一？如果不唯一究竟有多少个解？
　　d试求出所有解答（等式左边两边分数交换次序只算一个解答）；

　　答案：10

　　套模板的步骤：

　　　　元素初值：a[1]=1,数组元素初值取1
　　　　取值点：a[i]=1,各个元素从1开始取值
　　　　回溯点：a[i]=9，各元素的值到9之后,开始回溯
　　　　约束条件1： a[i]==a[k]||a[1]>a[4]
　　　　约束条件2： i==9&& a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2
　　　　其中： m1=a[2]*10+a[3];
　　　　m2=a[5]*10+a[6];
　　　　m3=a[8]*10+a[9];

　　　　从题干中找出如下几点之后，就可以开始套模板了

 1 /*桥本分析式*/
 2 #include<iostream>
 3 #include<math.h>
 4 using namespace std;
 5 
 6 
 7 int main()
 8 {
 9     int i,n=9,g,k,w=0;
10     long m1,m2,m3;
11     int a[10];
12     i=1;a[i]=1;
13     while(1)
14     {
15         g=1;
16         for(k=i-1;k>=1;k--)
17             if(a[i]==a[k]||a[1]>a[4])
18                 g=0;
19         
20         if(g==1&&i==9)
21         {    
22             m1=a[2]*10+a[3];
23             m2=a[5]*10+a[6];
24             m3=a[8]*10+a[9];
25             if(a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2)
26             {
27                 w++;
28                 cout<<a[1]<<"/"<<m1<<"+"<<a[4]<<"/"<<m2<<"="<<a[7]<<"/"<<m3<<endl; 
29             }
30         }    
31         if(i<n&&g)
32         {
33             i++;
34             a[i]=1;
35             continue;
36         }    
37         while(a[i]==n&&i>1)i--;
38         if(a[i]==n&&i==1)
39             break;
40         else
41             a[i]=a[i]+1;    
42      } 
43     cout<<w<<endl;
44     return 0;
45 }

View Code

总结：