华师一附中OI组

标题: 递归实现pmn [打印本页]
作者: admin    时间: 2020-2-29 18:36
标题: 递归实现pmn
假设有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    时间: 2020-2-29 18:50
变形题目：
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    时间: 2020-2-29 18:51
标准的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    时间: 2020-2-29 19:22
第二题： 选任意个人，不要 if (i>3) ，因为这句话控制着什么时候输出，我每次选择都要输出。相应的变化，pr()函数要加上一个区间值。
作者: admin    时间: 2020-2-29 19:24
第三题：一样选择，但是输出的时候不输出数字，而是输出数字对应的字符。
定义string s="HSYIT";改pr()
for (int i=1; i<=3; i++) cout<<s的第a(i)-1位;
作者: admin    时间: 2020-2-29 19:27
第四题：组合问题也很常用，我们强行规定 后面的数字要比前面的大，就可以限制重复的出现，
改for循环为：        for (int k=a[i-1]+1; k<=5; k++)  

因为后面比前面大，所以不会出现重复现象，b数组就没有存在的意义了。可以去掉b数组相关的操作
作者: admin    时间: 2020-2-29 20:03
第五题：有重复的排列或者组合。我们不用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

  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    时间: 2020-2-29 20:08
第六题：多了一个约束条件，我们多加一个判断，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;

  11. }
  12. void pmn(int i)  /// 选择第i个数
  13. {
  14.         ///已经选择了3个数
  15.         if (i>8) pr();
  16.         else

  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    时间: 2020-2-29 20:14
第7题同第六题，就是判断标准有点不一样。
作者: admin    时间: 2020-2-29 20:16
第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.         }

  22. }
  23. void pmn(int i)  /// 选择第i个数
  24. {
  25.         if (i>8) pr();
  26.         else

  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. }
复制代码


作者: 张溯源    时间: 2020-2-29 20:51
本帖最后由 张溯源 于 2020-2-29 20:52 编辑
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. }
复制代码
作者: 张溯源    时间: 2020-2-29 21:33
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. }
复制代码

只是加了一个判断质数嘛~~~
没什么好说的，和第六题差不多。
~~~程序仅供参考~~~
作者: 张溯源    时间: 2020-2-29 21:36
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-3-1 13:15
楼上张同学，做得很好！！
大家向张同学学习！
作者: admin    时间: 2020-3-14 18:07
为了便于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都是和这个模型相似的，就像是有的灵长类的动物都是两个眼睛，一个鼻子，两只耳朵而且位置都相似的一样，但是他们和爬行类有显然的区别。要熟记这种模型和解法。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2