递归实现pmn

张溯源

admin 发表于 2020-2-29 20:16
第8题：我们先简化一下，11223344八选八会做吧。
然后选完之后在判断1和1之间有间隔了几个。这个一种很直 ...

1. //第八题
   
2. #include<iostream>
   
3. using namespace std;
   
4. int a[10];
   
5. int b[8]={0,2,2,2,2};
   
6. bool check()
   
7. {
   
8.         int x1,x2;
   
9.         for(int i=1;i<=8;i++)
   
10.                 if(a[i]==1)
    
11.                 {
    
12.                         x1=i;
    
13.                         break;
    
14.                 }
    
15.         for(int i=8;i>=1;i--)
    
16.                 if(a[i]==1)
    
17.                 {
    
18.                         x2=i;
    
19.                         break;
    
20.                 }
    
21.         bool book1=(x2-x1==2);
    
22.         
    
23.         int xx1,xx2;
    
24.         for(int i=1;i<=8;i++)
    
25.                 if(a[i]==2)
    
26.                 {
    
27.                         xx1=i;
    
28.                         break;
    
29.                 }
    
30.         for(int i=8;i>=1;i--)
    
31.                 if(a[i]==2)
    
32.                 {
    
33.                         xx2=i;
    
34.                         break;
    
35.                 }
    
36.         bool book2=(xx2-xx1==3);
    
37.         
    
38.         int xxx1,xxx2;
    
39.         for(int i=1;i<=8;i++)
    
40.                 if(a[i]==3)
    
41.                 {
    
42.                         xxx1=i;
    
43.                         break;
    
44.                 }
    
45.         for(int i=8;i>=1;i--)
    
46.                 if(a[i]==3)
    
47.                 {
    
48.                         xxx2=i;
    
49.                         break;
    
50.                 }
    
51.         bool book3=(xxx2-xxx1==4);
    
52.         
    
53.         int xxxx1,xxxx2;
    
54.         for(int i=1;i<=8;i++)
    
55.                 if(a[i]==4)
    
56.                 {
    
57.                         xxxx1=i;
    
58.                         break;
    
59.                 }
    
60.         for(int i=8;i>=1;i--)
    
61.                 if(a[i]==4)
    
62.                 {
    
63.                         xxxx2=i;
    
64.                         break;
    
65.                 }
    
66.         bool book4=(xxxx2-xxxx1==5);
    
67.         
    
68.         return (book1 && book2 && book3 && book4);
    
69. }
    
70. void pr()
    
71. {
    
72.         if(check())
    
73.         {
    
74.                 for(int i=1;i<=8;i++)
    
75.                         cout<<a[i];               
    
76.                 cout<<endl;
    
77.         }
    
78. }
    
79. void pmn(int i)
    
80. {
    
81.         if(i>8)
    
82.                 pr();
    
83.         else
    
84.                 for(int k=1;k<=4;k++)   
    
85.                         if(b[k]>0)  
    
86.                         {
    
87.                                 a[i]=k;   
    
88.                                 b[k]--;   
    
89.                                 pmn(i+1);
    
90.                                 b[k]++;   
    
91.                         }
    
92. }
    
93. int main()
    
94. {
    
95.         pmn(1);
    
96.         return 0;
    
97. }

复制代码

张溯源

admin 发表于 2020-2-29 20:14
第7题同第六题，就是判断标准有点不一样。

1. #include<iostream>
   
2. using namespace std;
   
3. int sum;
   
4. int a[3];
   
5. bool isp(int added)
   
6. {
   
7.         int i=2;
   
8.         while(i*i<=added)
   
9.         {
   
10.                 if(added%i==0)
    
11.                         return false;
    
12.                 i++;
    
13.         }
    
14.         return true;
    
15. }
    
16. bool isnext(int a,int b)
    
17. {
    
18.         if(a+1==b)
    
19.                 return true;
    
20.         else
    
21.                 return false;
    
22. }
    
23. void pmn(int i)
    
24. {
    
25.         if(i>2)
    
26.         {
    
27.                 if(isp(a[1]+a[2]) && isnext(a[1],a[2]))
    
28.                 {
    
29.                         sum++;
    
30.                         cout<<a[1]<<"+"<<a[2]<<"="<<a[1]+a[2]<<endl;
    
31.                 }
    
32.         }
    
33.         else
    
34.                 for(int k=a[i-1]+1;k<=8;k++)
    
35.                         {
    
36.                                 a[i]=k;
    
37.                                 pmn(i+1);                       
    
38.                         }         
    
39. }
    
40. int main()
    
41. {
    
42.         pmn(1);
    
43.         cout<<sum;
    
44.         return 0;
    
45. }

复制代码

只是加了一个判断质数嘛~~~
没什么好说的，和第六题差不多。
~~~程序仅供参考~~~

张溯源

admin 发表于 2020-2-29 19:22
第二题： 选任意个人，不要 if (i>3) ，因为这句话控制着什么时候输出，我每次选择都要输出。相应的变化，p ...

1. #include<iostream>
   
2. using namespace std;
   
3. int a[5];
   
4. int b[8]={1,1,1,1,1,1,1,1};
   
5. void pr(int x)
   
6. {
   
7.     for(int i=1;i<=x;i++)
   
8.                 cout<<a[i]<<" ";
   
9.     cout<<endl;
   
10. }
    
11. void pmn(int i)
    
12. {
    
13.     int k;
    
14.         pr(i-1);
    
15.     for(k=1;k<=5;k++)
    
16.         if(b[k]==1)
    
17.         {
    
18.             a[i]=k;
    
19.             b[k]=0;
    
20.             pmn(i+1);
    
21.             b[k]=1;
    
22.         }
    
23. }
    
24. int main()
    
25. {
    
26.     pmn(1);
    
27.     return 0;
    
28. }

复制代码

附上代码
~~~仅供参考~~~
运行结果长这样的：

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 5
1 2 3 5 4
1 2 4
1 2 4 3
1 2 4 3 5
1 2 4 5
1 2 4 5 3
1 2 5
1 2 5 3
1 2 5 3 4
1 2 5 4
1 2 5 4 3
1 3
1 3 2
1 3 2 4
1 3 2 4 5
1 3 2 5
1 3 2 5 4
1 3 4
1 3 4 2
1 3 4 2 5
1 3 4 5
1 3 4 5 2
1 3 5
1 3 5 2
1 3 5 2 4
1 3 5 4
1 3 5 4 2
1 4
1 4 2
1 4 2 3
1 4 2 3 5
1 4 2 5
1 4 2 5 3
1 4 3
1 4 3 2
1 4 3 2 5
1 4 3 5
1 4 3 5 2
1 4 5
1 4 5 2
1 4 5 2 3
1 4 5 3
1 4 5 3 2
1 5
1 5 2
1 5 2 3
1 5 2 3 4
1 5 2 4
1 5 2 4 3
1 5 3
1 5 3 2
1 5 3 2 4
1 5 3 4
1 5 3 4 2
1 5 4
1 5 4 2
1 5 4 2 3
1 5 4 3
1 5 4 3 2
2
2 1
2 1 3
2 1 3 4
2 1 3 4 5
2 1 3 5
2 1 3 5 4
2 1 4
2 1 4 3
2 1 4 3 5
2 1 4 5
2 1 4 5 3
2 1 5
2 1 5 3
2 1 5 3 4
2 1 5 4
2 1 5 4 3
2 3
2 3 1
2 3 1 4
2 3 1 4 5
2 3 1 5
2 3 1 5 4
2 3 4
2 3 4 1
2 3 4 1 5
2 3 4 5
2 3 4 5 1
2 3 5
2 3 5 1
2 3 5 1 4
2 3 5 4
2 3 5 4 1
2 4
2 4 1
2 4 1 3
2 4 1 3 5
2 4 1 5
2 4 1 5 3
2 4 3
2 4 3 1
2 4 3 1 5
2 4 3 5
2 4 3 5 1
2 4 5
2 4 5 1
2 4 5 1 3
2 4 5 3
2 4 5 3 1
2 5
2 5 1
2 5 1 3
2 5 1 3 4
2 5 1 4
2 5 1 4 3
2 5 3
2 5 3 1
2 5 3 1 4
2 5 3 4
2 5 3 4 1
2 5 4
2 5 4 1
2 5 4 1 3
2 5 4 3
2 5 4 3 1
3
3 1
3 1 2
3 1 2 4
3 1 2 4 5
3 1 2 5
3 1 2 5 4
3 1 4
3 1 4 2
3 1 4 2 5
3 1 4 5
3 1 4 5 2
3 1 5
3 1 5 2
3 1 5 2 4
3 1 5 4
3 1 5 4 2
3 2
3 2 1
3 2 1 4
3 2 1 4 5
3 2 1 5
3 2 1 5 4
3 2 4
3 2 4 1
3 2 4 1 5
3 2 4 5
3 2 4 5 1
3 2 5
3 2 5 1
3 2 5 1 4
3 2 5 4
3 2 5 4 1
3 4
3 4 1
3 4 1 2
3 4 1 2 5
3 4 1 5
3 4 1 5 2
3 4 2
3 4 2 1
3 4 2 1 5
3 4 2 5
3 4 2 5 1
3 4 5
3 4 5 1
3 4 5 1 2
3 4 5 2
3 4 5 2 1
3 5
3 5 1
3 5 1 2
3 5 1 2 4
3 5 1 4
3 5 1 4 2
3 5 2
3 5 2 1
3 5 2 1 4
3 5 2 4
3 5 2 4 1
3 5 4
3 5 4 1
3 5 4 1 2
3 5 4 2
3 5 4 2 1
4
4 1
4 1 2
4 1 2 3
4 1 2 3 5
4 1 2 5
4 1 2 5 3
4 1 3
4 1 3 2
4 1 3 2 5
4 1 3 5
4 1 3 5 2
4 1 5
4 1 5 2
4 1 5 2 3
4 1 5 3
4 1 5 3 2
4 2
4 2 1
4 2 1 3
4 2 1 3 5
4 2 1 5
4 2 1 5 3
4 2 3
4 2 3 1
4 2 3 1 5
4 2 3 5
4 2 3 5 1
4 2 5
4 2 5 1
4 2 5 1 3
4 2 5 3
4 2 5 3 1
4 3
4 3 1
4 3 1 2
4 3 1 2 5
4 3 1 5
4 3 1 5 2
4 3 2
4 3 2 1
4 3 2 1 5
4 3 2 5
4 3 2 5 1
4 3 5
4 3 5 1
4 3 5 1 2
4 3 5 2
4 3 5 2 1
4 5
4 5 1
4 5 1 2
4 5 1 2 3
4 5 1 3
4 5 1 3 2
4 5 2
4 5 2 1
4 5 2 1 3
4 5 2 3
4 5 2 3 1
4 5 3
4 5 3 1
4 5 3 1 2
4 5 3 2
4 5 3 2 1
5
5 1
5 1 2
5 1 2 3
5 1 2 3 4
5 1 2 4
5 1 2 4 3
5 1 3
5 1 3 2
5 1 3 2 4
5 1 3 4
5 1 3 4 2
5 1 4
5 1 4 2
5 1 4 2 3
5 1 4 3
5 1 4 3 2
5 2
5 2 1
5 2 1 3
5 2 1 3 4
5 2 1 4
5 2 1 4 3
5 2 3
5 2 3 1
5 2 3 1 4
5 2 3 4
5 2 3 4 1
5 2 4
5 2 4 1
5 2 4 1 3
5 2 4 3
5 2 4 3 1
5 3
5 3 1
5 3 1 2
5 3 1 2 4
5 3 1 4
5 3 1 4 2
5 3 2
5 3 2 1
5 3 2 1 4
5 3 2 4
5 3 2 4 1
5 3 4
5 3 4 1
5 3 4 1 2
5 3 4 2
5 3 4 2 1
5 4
5 4 1
5 4 1 2
5 4 1 2 3
5 4 1 3
5 4 1 3 2
5 4 2
5 4 2 1
5 4 2 1 3
5 4 2 3
5 4 2 3 1
5 4 3
5 4 3 1
5 4 3 1 2
5 4 3 2
5 4 3 2 1

admin

楼上张同学，做得很好！！
大家向张同学学习！

admin

为了便于pmn的变形，我们再次复习一下标准的pmn程序，这里我把每句话的意思都标在上面，

1. #include <iostream>
   
2. using namespace std;
   
3. int a[9];///选后的数
   
4. bool b[9]; ///布尔数组表示选择情况
   
5. void pr() /// 输出
   
6. {
   
7.         for (int i=1; i<=3; i++) cout<<a[i];
   
8.         cout<<endl;
   
9. }
   
10. void pmn(int i)  /// 选择第i个数
    
11. {
    
12.         if (i>3)  ///程序出口，再不需要被选择了
    
13.                 pr(i);   ///处理函数
    
14.         else
    
15.                 for (int k=1; k<=5; k++) /// 枚举可能性
    
16.                         if (b[k]==1) ///判断可行性（和上一句有一定的联系）
    
17.                         {
    
18.                                 a[i]=k;  // 选择它
    
19.                                 b[k]=0; ///选择引起的变化
    
20.                                 pmn(i+1); /// 选下一个数
    
21.                                 b[k]=1; ////!!!!恢复变化
    
22.                         }
    
23. }
    
24. int main()
    
25. {
    
26.         for(int i=1; i<=5; i++) b[i]=1; ///相关变量初值
    
27.         pmn(1);
    
28.         return 0;
    
29. }
    

复制代码

所有的dfs都是和这个模型相似的，就像是有的灵长类的动物都是两个眼睛，一个鼻子，两只耳朵而且位置都相似的一样，但是他们和爬行类有显然的区别。要熟记这种模型和解法。