20200307 pmn讲课

admin

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

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

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

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
    
14. 
    
15.                 for(int k=a[i-1]; k<=5; k++)
    
16. 
    
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

5、1-8八个数字排成一排，相邻两个数之差的绝对值<4。怎么办？
增加一个条件，除第一个之外，|a(i)-a(i-1)|<4
但是这个条件写起来不简单  应该是 ：  (i==1)   ||  (|a(i)-a(i-1)|<4)   隐含了一个条件 i==1

admin

6、11223344排成一排，两个1之间隔1个数字，两个2之间隔2个数字，**，求所有的排法。
这个题的放置条件更复杂。