华师一附中OI组

标题: 20200307 pmn讲课 [打印本页]
作者: admin    时间: 2020-3-7 19:23
标题: 20200307 pmn讲课
1、m个中选n个的基本程序：
  1. #include <iostream>
  2. using namespace std;
  3. const int mn=10;
  4. const int mm=20; ///m中选 n
  5. int a[mn];
  6. bool b[mm];
  7. int m,n,i;
  8. void pr()
  9. {
  10.         for (int i=1; i<=n; i++) cout<<a[i];
  11.         cout<<endl;
  12. }
  13. void dfs(int i)   ///  寻找第i的位置上的数
  14. {
  15.         if (i>n) pr();
  16.         else for (int k=1; k<=m; k++)
  17.                         if (b[k]==1)
  18.                         {
  19.                                 a[i]=k; /// 选择
  20.                                 b[k]=0; ///标记
  21.                                 dfs(i+1); ///选下一个
  22.                                 b[k]=1; ///复位
  23.                         }
  24. }
  25. int main()
  26. {
  27.         m=8,n=5;   ///假设8选5
  28.         for (int i=1; i<=mm-1; i++) b[i]=1; ///标记可选
  29.         dfs(1); ///从第一个开始
  30.         return 0;
  31. }
复制代码
作者: admin    时间: 2020-3-7 19:27
2、改成m个中选n个组合 ，组合不讲顺序，所以123也就是321,312。
转换点：强制认为后面比前面大，就限制了一些重复的选择。
改动：
1、k的取值  不是从1开始，而是要比前面大，所以从a[i-1]+1开始
2、因为后面比前面大，所以绝对不会重复，所以不需要b数组。

程序如下：
  1. #include <iostream>
  2. using namespace std;
  3. const int mn=10;
  4. const int mm=20; ///m中选 n
  5. int a[mn];
  6. bool b[mm];
  7. int m,n,i;
  8. void pr()
  9. {
  10.         for (int i=1; i<=n; i++) cout<<a[i];
  11.         cout<<endl;
  12. }
  13. void dfs(int i)   ///  寻找第i的位置上的数
  14. {
  15.         if (i>n) pr();
  16.         else for (int k=a[i-1]+1; k<=m; k++)
  17.                         ///if (b[k]==1)
  18.                         {
  19.                                 a[i]=k; /// 选择
  20.                         ///        b[k]=0; ///标记
  21.                                 dfs(i+1); ///选下一个
  22.                         ///        b[k]=1; ///复位
  23.                         }
  24. }
  25. int main()
  26. {
  27.         m=8,n=5;   ///假设8选5
  28.         ///for (int i=1; i<=mm-1; i++) b[i]=1; ///标记可选
  29.         a[0]=0 ; /// 最好加上，因为a[1-1]没有初值
  30.         dfs(1); ///从第一个开始
  31.         return 0;
  32. }
复制代码

作者: admin    时间: 2020-3-7 19:30
3、m个中选任意个的组合，
改动if (i>n) 这个地方。因为这里控制着输出，不是到n输出，而是任意个都要输出
  1. #include <iostream>
  2. using namespace std;
  3. const int mn=10;
  4. const int mm=20; ///m中选 n
  5. int a[mn];
  6. bool b[mm];
  7. int m,n,i;
  8. void pr(int i)
  9. {
  10.         for (int j=1; j<=i-1; j++) cout<<a[j];
  11.         cout<<endl;
  12. }
  13. void dfs(int i)   ///  寻找第i的位置上的数
  14. {
  15.         pr(i); ///要加一个参数
  16.         for (int k=a[i-1]+1; k<=m; k++)
  17.                         ///if (b[k]==1)
  18.                         {
  19.                                 a[i]=k; /// 选择
  20.                         ///        b[k]=0; ///标记
  21.                                 dfs(i+1); ///选下一个
  22.                         ///        b[k]=1; ///复位
  23.                         }
  24. }
  25. int main()
  26. {
  27.         m=8,n=5;   ///假设8选5
  28.         ///for (int i=1; i<=mm-1; i++) b[i]=1; ///标记可选
  29.         a[0]=0 ; /// 最好加上，因为a[1-1]没有初值
  30.         dfs(1); ///从第一个开始
  31.         return 0;
  32. }
复制代码


而且这里pr函数还有一个细节，加一个参数。这是编程基本功，你会吗？
作者: admin    时间: 2020-3-7 19:50
4、有重复怎么办？假设111223455中选3个，有多少种组合的选法。
重复的时候，不要用布尔数组，改用整数数组，用一个少一个而不是用和不用两种状态！

  1. #include <iostream>
  2. using namespace std;
  3. int a[10];///存放选后的数字
  4. int b[6]= {0,3,2,1,1,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)
  11. {
  12.         if(i>3)pr();
  13.         else

  15.                 for(int k=a[i-1]; k<=5; k++)

  17.                         if(b[k]>0)
  18.                         {
  19.                                 a[i]=k;
  20.                                 b[k]--;
  21.                                 pmn(i+1);
  22.                                 b[k]++;
  23.                         }
  24. }
  25. int main()
  26. {
  27.         a[0]=1;
  28.         pmn(1);
  29.         return 0;
  30. }
复制代码

注意这里又有个问题，是可以重复的，所以后面选出来的数可以和前面一样，k的初值就是a(i)，而不是前面那样的a(i-1)+1，完美的话还要赋初值a(0)=1;
作者: admin    时间: 2020-3-7 20:22
5、1-8八个数字排成一排，相邻两个数之差的绝对值<4。怎么办？
增加一个条件，除第一个之外，|a(i)-a(i-1)|<4
但是这个条件写起来不简单  应该是 ：  (i==1)   ||  (|a(i)-a(i-1)|<4)   隐含了一个条件 i==1
作者: admin    时间: 2020-3-7 20:23
6、11223344排成一排，两个1之间隔1个数字，两个2之间隔2个数字，**，求所有的排法。
这个题的放置条件更复杂。



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