华师一附中OI组

标题: 202003 pmn的变形使用讲课 [打印本页]
作者: admin    时间: 2020-3-14 18:38
标题: 202003 pmn的变形使用讲课
1、复习标准的pmn
2、体会相邻的数字差小于4 和 间隔排列
3、任意个的组合的两种写法
4、数字分解，1*2的骨牌覆盖，装箱问题的理解。
5、加一个参数的简洁写法。
6、布尔数组的用法（8皇后问题）。
7、深度不确定的搜索（因数分解）。


作者: admin    时间: 2020-3-14 20:04
重要讲讲第三个知识点：任意个组合的两种写法：
第一种dfs(int i) 和前面一样，枚举第i个位置选哪个数字。
第二种dfs(int i) 新思路：第i个数字是否被选中。
体会：第一种 按位置选人，第二种，按人选
作者: admin    时间: 2020-3-14 20:10
第一种，和前面的一样，但是去掉递归程序里面的if (i>n) ，因为每个都要输出，不是到n个才输出
  1. /// 5个选任意个
  2. #include <iostream>
  3. using namespace std;
  4. const int mm=10;
  5. int a[mm],n=5;
  6. void pr(int x)
  7. { for (int i=1;i<=x;i++)  cout<<a[i];cout<<endl; }
  8. void dfs(int i)
  9. {
  10.         pr(i-1);
  11.         for (int k=a[i-1]+1;k<=n;k++)
  12.         {a[i]=k;dfs(i+1);}
  13. }
  14. int main()
  15. {        a[0]=0;        dfs(1);return 0;}
复制代码
作者: admin    时间: 2020-3-14 20:16
第二种，枚举每个数组，两种情况，选和不选
  1. /// 5个选任意个
  2. #include <iostream>
  3. using namespace std;
  4. const int mm=10;
  5. bool b[mm];  ///布尔数组 表示这个人是否被选
  6. int n=5;
  7. void pr()   ///输出时候枚举是否被选
  8. { for (int i=1;i<=n;i++) if(b[i]==1) cout<<i;cout<<endl; }
  9. void dfs(int i)
  10. {
  11.         if(i>n) pr();
  12.         else  
  13.         for (int k=0;k<=1;k++)  ///枚举选和不选两种情况 0 -不选 1 选
  14.         {b[i]=k;dfs(i+1);}
  15. }
  16. int main()
  17. {        dfs(1);return 0;}
复制代码
作者: admin    时间: 2020-3-14 20:16
两种思路有相似，也有不同，好好体会。一般情况下，第2中用的多点，因为更简洁。01两种情况，可以不用循环。
作者: admin    时间: 2020-3-14 20:48
下面看 1025 数的划分，我们用最笨的pmn来做，因为好想呀。
化成程序问题：
1-n共N个数子，选出k和，总和是n就满足条件，后面一个>=前面一个，这个和组合有点相似。
第一版，最笨的程序：
  1. /// 1025
  2. #include <iostream>
  3. using namespace std;
  4. const int mn=210;
  5. const int mk=7;
  6. int a[mk],n,k,ans=0;
  7. void pr()
  8. {
  9.         int i,s=0;
  10.         for (i=1; i<=k; i++) s+=a[i];
  11.         if (s==n)
  12.         {
  13.                 cout<<++ans<<':';
  14.                 for (i=1; i<=k; i++)  cout<<a[i]<<' ';
  15.                 cout<<endl;
  16.         }
  17. }
  18. void dfs(int i)
  19. {
  20.         if (i>k) pr();
  21.         else for (int j=a[i-1]; j<=n; j++) ///k被前年用了
  22.                 {
  23.                         a[i]=j;
  24.                         dfs(i+1);
  25.                 }
  26. }
  27. int main()
  28. {
  29.         n=20,k=4; ///20 分成4 组
  30.         a[0]=1;
  31.         dfs(1);
  32.         return 0;
  33. }
复制代码


这个程序很笨，容易超时，但是思想是可行的，我们慢慢来优化它
作者: admin    时间: 2020-3-14 20:50
第一个优化，前面k-1个已经枚举出来了的话，最后一个不用枚举，只需要n-前面k-1个的和就是，加上这个优化。
第二个优化，第1个数一定不能取到n/k+1，第2个数一定不能取到n/(k-1)+1,****为什么：因为第2个数大于等于第1个，第三个大于等于第2个，要是a1>n/k+1，那么a2>n/k+1,** ak>n/k+1，全部加起来就>n了。

  1. /// 1025
  2. #include <iostream>
  3. using namespace std;
  4. const int mn=210;
  5. const int mk=7;
  6. int a[mk],n,k,ans=0;
  7. void pr()
  8. {
  9.         int i,s=0;
  10.         for (i=1; i<=k-1; i++) s+=a[i]; ///前面k-1个的和
  11.         a[k]=n-s;
  12.         if (a[k]>=a[k-1])
  13.         {
  14.                 cout<<++ans<<':';
  15.                 for (i=1; i<=k; i++)  cout<<a[i]<<' ';
  16.                 cout<<endl;
  17.         }
  18. }
  19. void dfs(int i)
  20. {
  21.         if (i>k-1) pr();
  22.         else for (int j=a[i-1]; j<=n/(k-i+1)+1; j++) ///k被前面用了
  23.                 {
  24.                         a[i]=j;
  25.                         dfs(i+1);
  26.                 }
  27. }
  28. int main()
  29. {
  30.         n=20,k=4; ///20 分成4 组
  31.         a[0]=1;
  32.         dfs(1);
  33.         return 0;
  34. }
复制代码

这些优化的方法是考试的重点，平常一般考搜索的话，大家都会动笔，但是谁做得好呢？差别就在优化。
作者: admin    时间: 2020-3-14 21:09
1049装箱问题： 本质就是选出任意个数字，加起来的总和<=V 又最近接V，那我枚举所有的可能求出所有的总和，看看谁最接近V就是了。套用第二种组合的做法：仅仅改动了输出部分，加上了求和和判断。
  1. /// 5个选任意个
  2. #include <iostream>
  3. using namespace std;
  4. const int mm=33;/// 最多
  5. bool b[mm];  ///布尔数组 表示这个人是否被选
  6. int V,n,sum,a[mm],ans;
  7. void pr()   
  8. {
  9.         sum=0;
  10.         for (int i=1; i<=n; i++) if(b[i]==1) sum+=a[i];
  11.         if (sum<=V)
  12.          ans=min(ans,V-sum);/// 求最小值
  13. }
  14. void dfs(int i)
  15. {
  16.         if(i>n) pr();
  17.         else
  18.                 for (int k=0; k<=1; k++) ///枚举选和不选两种情况 0 -不选 1 选
  19.                 {
  20.                         b[i]=k;
  21.                         dfs(i+1);
  22.                 }
  23. }
  24. int main()
  25. {
  26.         cin>>V>>n;ans=999999;
  27.         for (int i=1;i<=n;i++) cin>>a[i];
  28.         dfs(1);
  29.         cout<<ans;
  30.         return 0;
  31. }
复制代码


但是这样做超时了一些解，因为效率不高，哪些地方可以改进呢？
作者: admin    时间: 2020-3-21 19:35
接上：显然，当sum>V 的时候没有必要再做了，后面的装不下呀，所以sum>V直接终止，后面的不用是搜索。
当sum==V。也不用做了，最小值就是0。（和刚才那个>有点区别）
不要在最后一起统计sum，而是每次加入新物品的时候更新sum，同时判断sum<=V
  1. #include <iostream>
  2. using namespace std;
  3. int ans=999999;
  4. int n,V,a[40],sum;
  5. bool b[40];
  6. void pr()
  7. {
  8.                 if (sum<=V) ans=min(ans,V-sum);
  9. }
  10. void dfs(int i)
  11. {
  12.         if (i>n) pr();
  13.         else
  14.         {
  15.                 b[i]=0;  ///不选 没变化
  16.                 dfs(i+1);
  17.                
  18.                 b[i]=1;///选了  
  19.                 sum+=a[i];///总和加了
  20.                 if (sum<=V) dfs(i+1);   ///超了 就没有下一个了！
  21.                 sum-=a[i];///退回去
  22.         }
  23. }
  24. int main()
  25. {
  26.         cin>>V>>n;
  27.         for (int i=1; i<=n; i++) cin>>a[i];
  28.         dfs(1);
  29.         cout<<ans;
  30. }
复制代码
作者: admin    时间: 2020-3-21 19:37
另外一种理解，用dfs(v,i)表示v体积下装i个物品的最小值。那么选择第i个物体，就变成了dfs(V-a(i),i+1)，不选，就是dfs(V,i+1)。
作者: admin    时间: 2020-3-21 19:56
1*2 的骨牌去覆盖2*2的格子有两种情况：
1 1
2 2
和
1 2
1 2
其实就是骨牌横着摆和竖着摆两种，1*2覆盖4*4的格子呢，有36种情况：
请你编程显示出来。
可以理解成间隔排列的加强版
作者: admin    时间: 2020-3-21 20:03
首先，显然想的到，枚举横着和竖着两种情况，知道第8块放下去为止
void pr(){ 打印棋盘}
void dfs(int i)
{  if (i>8) pr();
    else
    {
      横排
      竖排
    }
}
作者: admin    时间: 2020-3-21 20:05
棋盘怎么表示，我建议大家用a(0)-a(15)表示16个格子，当然也人想用a(1)(1)到 a(4)(4)，等下你就会发现a(0)-a(15)好！
作者: admin    时间: 2020-3-21 20:07
横着排，那么要求i不在最右一列，a(i)和 a(i+1)都==0
竖着排，那么要求i不在最后一行，a(i)和 a(i+4)都==0
那么其他的求和间隔排列一样了。
作者: admin    时间: 2020-3-21 20:20
程序和间隔拍列有相似，可以对比看看，
  1. #include <iostream>
  2. using namespace std;
  3. int a[20],k=0,ans;
  4. void pr()  ///很有水平
  5. {
  6.         cout<<endl<<++ans;
  7.         for (int i=0; i<=15; i++)
  8.         {
  9.                 if (i%4==0) cout<<endl;
  10.                 cout<<a[i]<<' ';
  11.         }
  12. }
  13. void  dfs(int i)
  14. {
  15.         if (i>15) pr();
  16.         else  if (a[i]>0)  dfs(i+1);
  17.         else
  18.         {
  19.                 ///heng
  20.                 if ( (i%4<3) && a[i+1]==0)
  21.                 {
  22.                         k++;
  23.                         a[i]=a[i+1]=k; ///放
  24.                         dfs(i+2);
  25.                         a[i]=a[i+1]=0; ///还回来 同间隔排列
  26.                         k--;
  27.                 }
  28.                 ///shu
  29.                 if ((i/4<3) && a[i+4]==0)
  30.                 {
  31.                         k++;
  32.                         a[i]=a[i+4]=k; ///放
  33.                         dfs(i+1);
  34.                         a[i]=a[i+4]=0; ///还回来 同间隔排列
  35.                         k--;
  36.                 }
  37.         }
  38. }
  39. int main()
  40. {
  41.         dfs(0);
  42.         return 0;
  43. }
复制代码
作者: admin    时间: 2020-3-21 20:48
8皇后问题：8*8的国际象棋棋盘，摆8个皇后，相互不攻击，皇后攻击同一行，同一列，正反两斜对角线的子。
搜索，总共8个皇后，每个皇后8个位置可能，满足条件就行，和8选8有相似之处：
void  dfs(int i)
{  
    if(i>9)  pr();
    else for (int k=1;k<=8;k++)
      if (can(i,k))  第i行可以放在第k个位置
       {
            a(i)=k;dfs(i+1);
        }
}
那么重点就在写函数can(i,k) 上
暴力搜索
bool  can(int i,int k)
{  
     bool b=1;
     for (int j=1;j<=i-1;j++)  if a(j)==k  b=0;   前面i-1 行某个和我同列
     for (int j=1;j<=i-1;j++)  if j+a(j)==k+i  b=0;    前面i-1 行某个和我同对角线
     for (int j=1;j<=i-1;j++)  if ???  b=0;   前面i-1 行某个和我同反对角线
  returnb;
}
作者: admin    时间: 2020-3-21 20:51
这个8皇后请自己完成
作者: admin    时间: 2020-3-21 20:53
所谓因数分解，就是
100=2*50
100=2*2*25
100=4*25
***
所有的分解情况，这个题显然也可以递归
dfs(i)表示把i分解，要是i==1就不能分解了，否则，可以分解出一个j（i%j==0） 然后继续去分解dfs(i/j)。
作者: admin    时间: 2020-3-21 20:56
void  dfs(int i)
if i==1 return
else for (int j=a[x-1];j<=i;j++)  后面的因子大于等于前面一个
  if (i%j==0)  {a[x]=j;dfs(i/j);}
作者: 张溯源    时间: 2020-5-9 20:52
我们还可以用这种方法来算二的一百次方的最少计算次数，和因数分解很像，上代码：
作者: 张溯源    时间: 2020-5-9 20:54
  1. #include <iostream>
  2. using namespace std;
  3. int n,x,a[20]= {0,1,2};
  4. void pr()
  5. {
  6.         if (a[n]==100)
  7.                 {
  8.                         for(int i=1; i<=n; i++)
  9.                                 cout<<a[i]<<' ';
  10.                         cout<<endl;
  11.                         n--;///精妙的一句！！！
  12.                 }
  13. }
  14. bool canp(int i,int k)
  15. {
  16.         bool b=0;
  17.         for(int j1=1; j1<=i-1; j1++)
  18.                 for(int j2=1; j2<=i-1; j2++)
  19.                         if (a[j1]+a[j2]==k) b=1;
  20.         return b;
  21. }
  22. void dfs(int i)   /// 找第i个数
  23. {
  24.         if(i>=n+1)        pr();
  25.         else
  26.                 for(int k=a[i-1]+1; k<=2*a[i-1]; k++)
  27.                         if(canp(i,k))
  28.                                 {
  29.                                         a[i]=k;
  30.                                         dfs(i+1);
  31.                                 }
  32. }
  33. int main()
  34. {
  35.         x=100;
  36.         n=20;
  37.         dfs(3);
  38.         return 0;
  39. }
复制代码




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