[关闭]
@Moritz 2019-03-26T04:26:10.000000Z 字数 6452 阅读 469

第七章 暴力求解法

aoapc_2nd C++ 所有文稿

7.1 简单枚举

例题 7-1 除法

输入正整数n，从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a~j恰好为数字0-9的一个排列。

思路：即使参考了书上的思路，看上去很容易实现，实际上真正上手写出来代码花了几个多小时，再次深刻地体现了现在纸上写好细节思路的重要性，以及对应功能用函数实现使到代码简化的必要性。

  1. /*19:48*/
  2. /*21:04*/
  3. #include <iostream>
  4. #include <cmath>
  5. using namespace std;
  6. int a[20],n,cnt=0;
  7. int turn_5(int x=1,int y=5){//把除数（数组的前五个数）化成整数
  8.     int tot=0;
  9.     float e=0.0;
  10.     for(int i=x;i<=y;i++){
  11.         tot=tot+a[i]*pow(10,e);
  12.         //printf("i=%d tot=%d\n",i,tot);
  13.         e=e+1.0;
  14.     }
  15.     return tot;
  16. }
  18. int devi(int x,int n,int a=5){//把被除数拆成5个数字，以便判重
  19.     int e=1;
  20.     for(int i=1;i<n;i++) e*=10;
  21.     x/=e;
  22.     x=x%10;
  23.     return x;
  24. }
  27. void find_5(int cur){//生成除数的所有可能
  28.     /*递归边界，判重*/
  29.     if (cur>5) {
  30.         if (turn_5()*n<=99999) {
  31.             bool ok=true;
  32.             int x=turn_5()*n;
  33.             for(int i=6;i<=10;i++){
  34.                 a[i]=devi(x,i-5,5);
  35.                 for(int j=1;j<i;j++){
  36.                     if (a[j]==a[i]){
  37.                         //printf("turn_5=%d x=%d a[%d]=a[%d]==%d\n",turn_5(),x,i,j,a[i]);
  38.                         ok=false;
  39.                         break;
  40.                     }
  41.                 }
  42.             }
  43.             if (ok){//如果不重复 输出
  44.                 if (cnt++)
  45.                     cout<<endl;
  46.                 for(int i=10;i>=6;i--) cout<<a[i];
  47.                 cout<<'\\';
  48.                 for(int i=5;i>=1;i--) cout<<a[i];
  49.                 cout<<'\='<<n;
  51.             }
  52.         }
  53.         return;
  54.     }
  56. /*生成除数的排列*/
  57.     for(int i=0;i<=9;i++){
  58.         bool ok=true;
  59.         for(int j=1;j<cur;j++){
  60.             if (a[j]==i){
  61.                 ok=false;
  62.                 break;
  63.             }
  64.         }
  65.         if (ok){
  66.             a[cur]=i;
  67.             find_5(cur+1);
  68.         }
  69.     }
  71. }
  73. int main(){
  74.     cin>>n;
  75.     memset(a,0,sizeof(a));
  76.     find_5(1);
  77.     system("pause");
  78.     return 0;
  79. }

出现的几个难题（自己挖的坑）：

例题 7-2 最大乘积

输入n个元素组成的序列S，找出一个乘积最大的连续子序列，如果最大的乘积不是正数，则输出0。（1<=n<=10,-10<=Si<=10)

思路：直接循环枚举，没啥难度，反而一开始还想多了，开始写solve递归函数……

  1. /*21:32*/
  2. /*21:44*/
  4. #include <iostream>
  6. using namespace std;
  7. long long max_mu=0;
  8. int a[20],n;
  10. int mu(int x,int y){
  11.     int tot=1;
  12.     for(int i=x;i<=y;i++) tot*=a[i];
  13.     return tot;
  14. }
  16. int main(){
  17.     int en=0;
  18.     while(cin>>n){
  19.         memset(a,0,sizeof(a));
  20.         max_mu=0;
  21.         for(int i=0;i<n;i++) cin>>a[i];
  22.         for(int i=0;i<n-1;i++){
  23.             for(int j=1;j<n;j++){
  24.                 if (j-i>=1){
  25.                     max_mu=(max_mu>mu(i,j)?max_mu:mu(i,j));
  26.                 }
  27.             }
  28.         }
  29.         if(en++) cout<<endl;
  30.         cout<<max_mu;
  31.     }
  32.     system("pause");
  33.     return 0;
  34. }

7.2 枚举排列

7.2.1 生成1~n的排列

写就是了

  1. /*21:49*/
  2. /*21:57*/
  3. #include <iostream>
  4. using namespace std;
  5. const int maxn=1000;
  6. int a[maxn],n;
  7. void print_per(int cur){
  8.     if (cur>=n){
  9.         cout<<"(";
  10.         int co=0;
  11.         for(int i=0;i<n;i++){
  12.             if (co++) cout<<",";
  13.             cout<<a[i];
  14.         }
  15.         cout<<")"<<endl;
  16.         return;
  17.     }
  18.     for(int i=1;i<=n;i++){
  19.         bool ok=true;
  20.         for(int j=0;j<cur;j++){
  21.             if (a[j]==i){
  22.                 ok=false;
  23.                 break;
  24.             }
  25.         }
  26.         if(ok){
  27.             a[cur]=i;
  28.             print_per(cur+1);
  29.         }
  30.     }
  31. }
  33. int main(){
  34.     cin>>n;
  35.     print_per(0);
  36.     system("pause");
  37.     return 0;
  38. }

7.2.2 生成可重集的排列

  1. /*22:04*/
  2. /*22:23*/
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. const int maxn=1000;
  7. int a[maxn],n,p[maxn],re[10];
  9. int count(int x,int cur){//优化
  10.     int tot=0;
  11.     for(int i=0;i<cur;i++){
  12.         if (a[i]==x) tot++;}
  13.     return tot;
  14. }
  16. void print_per(int cur){
  17.     if (cur>=n){
  18.         cout<<"(";
  19.         int co=0;
  20.         for(int i=0;i<n;i++){
  21.             if (co++) cout<<",";
  22.             cout<<a[i];
  23.         }
  24.         cout<<")"<<endl;
  25.         return;
  26.     }
  27.     for(int i=0;i<=n;i++){//从p0-pn取值
  28.         if (i==0||p[i]!=p[i-1]){//注意！！！：此举避免了出现重复的排列，例如（1,1,1）的情况
  29.             if (count(p[i],cur)<re[p[i]]){//如果现有a元素中p元素各值的数量未满
  30.                 a[cur]=p[i];
  31.                 print_per(cur+1);
  32.             }
  33.         }
  34.     }
  35. }
  37. int main(){
  38.     cin>>n;
  39.     memset(p,0,sizeof(p));
  40.     memset(a,0,sizeof(a));
  41.     memset(re,0,sizeof(re));
  42.     for(int i=0;i<n;i++){
  43.         cin>>p[i];
  44.         re[p[i]]++;//优化书中代码，只需统计一次p中p[i]出现的次数
  45.     }
  46.     sort(p,p+n);
  47.     print_per(0);
  48.     system("pause");
  49.     return 0;
  50. }

7.3 子集生成

看了下，没怎么管。 -2019.3.8

7.4 回溯法

7.4.1 八皇后问题

看完分析之后试写了一下

  1. /*10:14*/
  2. /*10:58*/
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <utility>
  9. using namespace std;
  11. int a1[20],a2[20],cnt=0;
  12. pair<int,int> point[10];//存放皇后的坐标
  13. map<set<pair<int,int> > ,int> m;
  15. bool an1(int x,int y,int cur){//判断(x,y)点主对角线上是否有皇后
  16.     /*if (a1[y-x+7]==0) return true;
  17.     return false;*/
  18.     for(int i=1;i<cur;i++){
  19.         if (point[i].first+point[i].second==x+y) return false;
  20.     }
  21.     return true;
  22. }
  24. bool an2(int x,int y,int cur){//判断的对角线上是否有皇后
  25.     /*if (a2[y+x]==0) return true;
  26.     return false;*/
  27.     for(int i=1;i<cur;i++){
  28.         if (point[i].first-point[i].second==x-y) return false;
  29.     }
  30.     return true;
  31. }
  33. void search(int cur){
  34.     if (cur>8){
  35.         set<pair<int,int>> p;
  36.         for(int i=1;i<=8;i++){
  37.             p.insert(make_pair((point[i]).first,(point[i]).second));
  38.         }
  39.         if (!m.count(p)){
  40.             m[p]=1;
  41.             printf("Case %d\n",++cnt);
  42.             for(int i=1;i<=8;i++){
  43.                 printf("Point %d:(%d,%d)\n",i,point[i].first,point[i].second);
  44.             }
  45.         }
  46.         return;
  47.     }
  48.     for(int x=1;x<=8;x++){//确定x坐标
  49.         bool ok_x=true;
  50.         for(int i=1;i<cur;i++){//y坐标判重
  51.             if ((point[i]).first==x){
  52.                 ok_x=false;
  53.                 break;
  54.             }
  55.         }
  56.         if (ok_x){
  57.             for(int y=1;y<=8;y++){
  58.                 bool ok_y=true;
  59.                 for(int j=1;j<cur;j++){//x坐标判重
  60.                     if ((point[j]).second==y){
  61.                         ok_y=false;
  62.                         break;
  63.                     }
  64.                 }
  65.                 if (ok_y){
  66.                     if (an1(x,y,cur)&&an2(x,y,cur)){
  67.                         point[cur].first=x;
  68.                         point[cur].second=y;
  69.                         search(cur+1);
  70.                     }}}}}}
  72. int main(){
  73.     memset(a1,0,sizeof(a1));
  74.     memset(a2,0,sizeof(a2));
  75.     memset(point,0,sizeof(point));
  76.     search(1);
  77.     system("pause");
  78.     return 0;
  79. }
  80. /*
  81. （输出的点和坐标已省略，共92组解
  82. Process returned 0 (0x0)   execution time : 57.719 s
  83. Press any key to continue.
  84. */

没有意识到，其实直接规定每行有一个皇后就可以了，不用进行y坐标的判重，算法复杂度明显提高，运行时间将近一分钟，并且还需要运用map进行判重。

优化之后：

  1. /*2.1 去掉了map判重*/
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <string.h>
  5. #include <utility>
  6. using namespace std;
  8. int cnt=0;
  9. pair<int,int> point[10];//存放皇后的坐标
  11. bool an1(int x,int y,int cur){//判断(x,y)点主对角线上是否有皇后
  12.     for(int i=1;i<cur;i++){
  13.         if (point[i].first+point[i].second==x+y) return false;
  14.     }
  15.     return true;
  16. }
  18. bool an2(int x,int y,int cur){//判断的对角线上是否有皇后
  19.     for(int i=1;i<cur;i++){
  20.         if (point[i].first-point[i].second==x-y) return false;
  21.     }
  22.     return true;
  23. }
  25. void search(int cur){
  26.     if (cur>8){
  27.         printf("Case %d\n",++cnt);
  28.         for(int i=1;i<=8;i++){
  29.             printf("Point %d:(%d,%d)\n",i,point[i].first,point[i].second);
  30.         }
  31.         return;
  32.     }
  34.     for(int y=1;y<=8;y++){
  35.         bool ok_y=true;
  36.         for(int j=1;j<cur;j++){//x坐标判重
  37.             if ((point[j]).second==y){
  38.                 ok_y=false;
  39.                 break;
  40.             }
  41.         }
  42.         if (ok_y){
  43.             if (an1(cur,y,cur)&&an2(cur,y,cur)){
  44.                 point[cur].first=cur;
  45.                 point[cur].second=y;
  46.                 search(cur+1);
  47.             }
  48.         }
  49.     }
  50. }
  52. int main(){
  53.     memset(point,0,sizeof(point));
  54.     search(1);
  55.     system("pause");
  56.     return 0;
  57. }
  60. /*至此，完成，11：11
  62. Process returned 0 (0x0)   execution time : 0.156 s
  63. Press any key to continue.
  64. */

7.4.2 其他应用举例

例题 7-5 困难的串

一开始理解出现偏差，误以为第k小的困难串长度等于k，输入为30 3的时候输出错误，然后修改得乱七八糟

  1. /*10:27*/
  3. #include <iostream>
  4. #include <string>
  5. using namespace std;
  6. int n,l;
  7. string str(80,'0'),str2(80,'0');//string初始化，否则str[cur-1]=c语句会造成溢出
  8. void solve(int cur){
  9.     if (cur>n){
  10.         cout<<str<<endl;
  11.         system("pause");
  12.         return;
  13.     }
  14.     else{
  15.         for(int i=0;i<l;i++){
  16.             char c='A'+i;
  17.             bool ok=true;
  18.             cout<<"enter loop cur="<<cur<<endl;
  19.             for(int len=1;len<cur/2;len++){
  20.                 if (str.substr(cur-len)==str.substr(cur-len*2,len)){
  21.                     cout<<str.substr(cur-len)<<endl;
  22.                     cout<<str.substr(cur-len*2,len)<<endl;
  23.                     cout<<str<<endl;
  24.                     ok=false;
  25.                     break;
  26.                 }
  27.             }
  28.             cout<<"loop ok cur="<<cur<<endl;
  29.             if (ok){
  30.                 str[cur-1]=c;
  31.                 solve(cur+1);
  32.             }
  33.         }
  34.     }
  35. }
  37. int main(){
  38.     cin>>n>>l;
  39.     //solve(1);
  40.     int cur=1,cnt=0;
  41.     while(cnt<=n){
  42.         bool ok=true;
  43.         char c;
  44.         for(int i=0;i<l;i++){
  45.             c='A'+i;
  46.             str2[cur-1]=c;
  47.             //cout<<"enter loop cur="<<cur<<endl;
  48.             ok=true;
  49.             for(int len=1;len<=cur/2;len++){
  50.                 //cout<<str.substr(cur-len,len)<<endl;
  51.                 //cout<<str.substr(cur-len*2,len)<<endl;
  52.                 if (str2.substr(cur-len,len)==str2.substr(cur-len*2,len)){
  53.                     //cout<<str.substr(cur-len,len)<<endl;
  54.                     //cout<<str.substr(cur-len*2,len)<<endl;
  55.                     ok=false;
  56.                     break;
  57.                 }
  58.             }
  59.             if (ok) {
  60.                 //cout<<"loop ok cur="<<cur<<endl;
  61.                 cnt++;
  62.                 str[cur-1]=c;
  63.                 str2[cur-1]=c;
  64.             }
  65.         }
  66.         cur++;
  67.     }
  68.     for(int i=0;i<cur;i++) cout<<str[i];
  69.     system("pause");
  70.     return 0;
  71. }
  73. /*运行结果：
  74. 7 3
  75. CBBB0请按任意键继续. . .
  76. 不改了，看书*/

书上照搬，发现30 3无输出

挖个坑先

例题 7-6 带宽

2019.3.8

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注