递归实现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

变形题目：
1、5个人中选出3个人照相有多少种照相的方法？
2、5个人中选出任意个人出来照相有多少种方法？
3、HSYIT五个人中选出3个人照相有多少种照相的方法？
4、5个人中选出3个人去参加培训班有多少种方法（组合，没有顺序）
5、3个蓝色球，2个红色球，2个黄色球中选出3个球有多少种颜色组合（多重选择）
6、1-8八个数字排成一排，相邻的两个数字之差的绝对值小于4，有多少种排法（有限制的pmn）
7、1-8八个数字排成一排，相邻的两个数字之和为质数，有多少种排法（有限制的pmn）
8、11223344八个数字排成一排，1和1之间隔一个数，2和2之间间隔2个数，n和n之间间隔n个数，怎么排 （多种约束条件）

admin

第二题： 选任意个人，不要 if (i>3) ，因为这句话控制着什么时候输出，我每次选择都要输出。相应的变化，pr()函数要加上一个区间值。

admin

第三题：一样选择，但是输出的时候不输出数字，而是输出数字对应的字符。
定义string s="HSYIT";改pr()
for (int i=1; i<=3; i++) cout<<s的第a(i)-1位;

admin

第四题：组合问题也很常用，我们强行规定 后面的数字要比前面的大，就可以限制重复的出现，
改for循环为：        for (int k=a[i-1]+1; k<=5; k++)  

因为后面比前面大，所以不会出现重复现象，b数组就没有存在的意义了。可以去掉b数组相关的操作

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. }
    

复制代码

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

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

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