递归实现pmn

admin

假设有m个人，选出n个人出来照相，请问有多少种情况。
这是一个非数值计算的典型题目:

若只选出一个人出来照相是很简单的。只要枚举1-5五种情况就可以了 for (i=1;i<=5;i++) cout<<i;


要选两个人出来的话，先选一个，再选第二个，但是有个条件，第二个人不能和第一个人一样，只有两个人，这个简单 判断下i!=j就可以了
   for (i=1;i<=5;i++) for (j=1;j<=5;i++) if (i!=j) cout<<i<<j;


三个人就比较麻烦了，要判断3个人互不相同，需要写(i!=j) &&  (j!=k) && (k!=i) 。外面的循环要写3重，要是人再多一点，这样写肯定不行。


让选择的对象不重复还有一种做法就是类似约瑟夫、三连击那样的布尔数组，用b(1)-b(10)表示10个人是否被选，b(i)=1表示i还没有被选，那么每次选择之前判断b(i)==1，若Y表示可以选，N就不能选，这样可以避免写好多的互不相等的判断。


像递归大楼里面的求最大数，阶乘、辗转相除法GCD等一样，循环可以化成递归，这个题我们用如下框架写递归：


void pmn(int i) ///选择第i个人
{  if (i>n) pr();///递归出口，若选择的人已经有了n个，那就完成这一轮的选择并输出
   else  
   for (int k=1;k<=m;k++)  ///有m个选择的可能
    if (b[k]) ///要是此人没有被选择就可以选择
     {   a(i)=k; ///第i个位置上放这个人
         b[k]=0; ///这个人已经被选了
         pmn(i+1) ; ///递归去选择下一个人
        b[k]=0; ///这个人又可以被下一次选择了！！
     }
}

主程序中先给b数组赋初值1，然后调用pmn(1)就可以了。

这个程序的执行过程要好好体会一下。

admin

第8题：我们先简化一下，11223344八选八会做吧。
然后选完之后在判断1和1之间有间隔了几个。这个一种很直观的方法，尽管效率低。

1. #include <iostream>
   
2. using namespace std;
   
3. int a[10];///选后的数
   
4. int  b[]= {0,2,2,2,2}; ///整数数组表示选择情况
   
5. bool check()  ///判断1和1 之间有几个 2和2 之间有几个
   
6. {    int x1,x2;
   
7.    for (int i=1;i<=8;i++)  if (a[i]==1) {x1=i;break;}
   
8.    for (int i=8;i>=1;i--)  if (a[i]==1) {x2=i;break;}
   
9.    ///剩下的不想写 好累！
   
10.    bool b=(x2-x1==2);
    
11.    
    
12.    return (b);
    
13. }
    
14. void pr() /// 输出
    
15. {
    
16.         if (check())
    
17.         {
    
18.                 for (int i=1; i<=8; i++) cout<<a[i];
    
19.                 cout<<endl;
    
20.         }
    
21. 
    
22. }
    
23. void pmn(int i)  /// 选择第i个数
    
24. {
    
25.         if (i>8) pr();
    
26.         else
    
27. 
    
28.                 for (int k=1; k<=4; k++) /// 4种可能
    
29.                         if (b[k]>0) ///还有可以的选择
    
30.                         {
    
31.                                 a[i]=k;  // 选择它
    
32.                                 b[k]--; ///次数减1
    
33.                                 pmn(i+1); /// 选下一个数
    
34.                                 b[k]++; ////!!!! 这个数还回来！
    
35.                         }
    
36. }
    
37. int main()
    
38. {
    
39.         pmn(1);
    
40.         return 0;
    
41. }
    

复制代码

admin

标准的pmn程序如下：

1. #include <iostream>
   
2. using namespace std;
   
3. int a[5];///选后的数
   
4. bool b[]= {1,1,1,1,1,1}; ///布尔数组表示选择情况
   
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)  ///已经选择了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.         pmn(1);
    
27.         return 0;
    
28. }
    

复制代码

有的教科书上写的时候pmn进来的时候不是if而是for，把if写到for循环里面去，这其实没有太大的区别，就像循环，有的是先判断在执行，有的是先执行再判断，思路是一样的，但是我更喜欢也建议大家写我这种先判断再循环的。

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

admin

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

张溯源

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 发表于 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 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

第7题同第六题，就是判断标准有点不一样。

admin

第六题：多了一个约束条件，我们多加一个判断，abs(a(i)-k)<4，但是要特殊考虑第一个数，他前面没有，所以他不用判断。
for (int k=1;k<=8;k++)
{
    b1=(i==1); //是不是第一个数
    b2=(abs(k-a(i-1))<4) ;
    if ((b1|| b2) && (b[k]==1)) {****}
}

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. int a[10];///选后的数
   
5. int  b[]= {0,1,1,1,1,1,1,1,1,1}; ///整数数组表示选择情况
   
6. void pr() /// 输出
   
7. {
   
8.         for (int i=1; i<=8; i++) cout<<a[i];
   
9.         cout<<endl;
   
10. 
    
11. }
    
12. void pmn(int i)  /// 选择第i个数
    
13. {
    
14.         ///已经选择了3个数
    
15.         if (i>8) pr();
    
16.         else
    
17. 
    
18.                 for (int k=1; k<=8; k++) /// 4种可能
    
19.                 {
    
20.                         bool b1=(i==1);
    
21.                         bool b2=(abs(k-a[i-1])<4);
    
22.                         bool b3=b[k]>0;
    
23.                         if (b1||b2 && b3) ///还有可以的选择
    
24.                         {
    
25.                                 a[i]=k;  // 选择它
    
26.                                 b[k]--; ///次数减1
    
27.                                 pmn(i+1); /// 选下一个数
    
28.                                 b[k]++; ////!!!! 这个数还回来！
    
29.                         }
    
30.                 }
    
31. }
    
32. int main()
    
33. {
    
34.         pmn(1);
    
35.         return 0;
    
36. }
    

复制代码

答案是 1042 个

admin

第五题：有重复的排列或者组合。我们不用bool数组，改用int数组，用一个减一，不像布尔，用一下就没了。

1. #include <iostream>
   
2. using namespace std;
   
3. int a[5];///选后的数
   
4. int  b[]= {0,3,2,2}; ///整数数组表示选择情况
   
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.           ///已经选择了3个数
    
13.              if (i>3) pr();
    
14.              else
    
15. 
    
16.                 for (int k=1; k<=3; k++) /// 五个可能
    
17.                         if (b[k]>0) ///还有可以的选择
    
18.                         {
    
19.                                 a[i]=k;  // 选择它
    
20.                                 b[k]--; ///次数减1
    
21.                                 pmn(i+1); /// 选下一个数
    
22.                                 b[k]++; ////!!!! 这个数还回来！
    
23.                         }
    
24. }
    
25. int main()
    
26. {
    
27.         pmn(1);
    
28.         return 0;
    
29. }
    

复制代码

我这个写的是排列 大家自己改成组合。