文章目录
一、穷举法
定义
穷举法是算法设计中经常使用的一种方法，基本思想是问题的要求将问题的所有可能的输入一一进行验证，看是否满足问题的条件，从而找到可能的解。问题解有三种情况：有多个解，单个解或无解。穷举法又名枚举法，暴力破解法等。
算法思路
采用穷举算法解题的基本思路：
（1）确定穷举对象、穷举范围和判定条件；
（2）穷举可能的解，验证是否是问题的解。
算法优缺点
- 由于穷举法一般是现实生活中问题的“直译”，因此比较直观，易于理解；穷举法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。
- 用穷举法解题的最大的缺点是运算量比较大，解题效率不高，如果穷举范围太大（一般以不超过两百万次为限），在时间上就难以承受。
示例：
皇后问题。所谓的n皇后问题，是指在n×n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，
皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。后问题等价于在n×n格的棋盘上放置n个皇后，
任何2个皇后不放在同一行或同一列或同一斜线上。 为了使问题更加有趣，我们需要求在n×n的棋盘上，放置k个皇后，共有多少种可能的方案数？
输入 两个正整数n和k，（n,k<=10） 输出 一个整数，表示方案数
int main(){int i,j,t,temp,n,k,flag,sum;sum=0;scanf("%d%d",&n,&k);int a[n];for(i=0;i<pow(n,n);i++){temp=i;for(j=0;j<n;j++){a[j]=temp%n;temp=temp/n;} flag=1;for(t=0;t<n;t++){for(j=t+1;j<n;j++){if(a[t]==a[j] || abs(j-t)==abs(a[t]-a[j])){flag=0;break; }}}if(flag==1)sum++;}printf("%d",sum);return 0;
}
处理机调度：用两台处理机A和B处理n个作业。设第i个作业交给A处理需要时间ai，交给B处理需要时间bi。
由于各作业的特点和机器的性能关系，ai和bi之间没有明确的大小关系。 既不有将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。
设计一个算法，使得这两台机器处理完这n个作业的时间最短。输入 第一行一个整数n，表示任务数（1<=n<=20）。 第二行n个整数，分别表示第i个任务在机器A上的处理时间。
第三行n个整数，分别表示第i个任务在机器B上的处理时间。处理时间数据范围（1~40）
输出 一个整数，表示最少的完成这些任务的时间 。
int main(){int n,i,j,temp,t,timeA,timeB,maxAB,Min; Min=10000;scanf("%d",&n);int a[n],b[n];for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)scanf("%d",&b[i]);for(i=0;i<pow(2,n);i++){timeA=timeB=0;temp=i;for(j=0;j<n;j++){if(temp%2==1)timeA+=a[j];elsetimeB+=b[j];temp=temp/2;}t=timeA>timeB?timeA:timeB;Min=Min>t?t:Min;}printf("%d",Min);
}
敢死队：G将军有一支训练有素的军队，这个军队除了G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。
现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要
求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。请问，G将军有多少种派出敢死队的方法。 注意，G将军也可以作为一个士兵进入敢死队。输入 输入的第一行包含一个整数n（1<=n<=20），表示包括G将军在内的军队的人数。 军队的士兵从1至n编号，G将军编号为1。
接下来n-1个数，分别表示编号为2, 3, …, n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。输出 一个整数，表示方法数
int main(){int i,j,t,num,n,temp,flag;scanf("%d",&n);int a[n],b[n];a[0]=-1;num=0;for(i=1;i<n;i++)scanf("%d",&a[i]);for(i=0;i<pow(2,n);i++){temp=i;for(j=0;j<n;j++){b[j]=temp%2;temp=temp/2;}flag=1;for(t=1;t<n;t++){if(b[t]==1&&b[a[t]-1]==1){flag=0;break;}}if(flag==1)num++;}printf("%d",num-1);return 0;
}
警匪110：匪警请拨110,即使手机欠费也可拨通！为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！
某批警察叔叔正在进行智力训练： 12 3 4 5 6 7 8 9 = 110
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9
就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。
请你利用计算机的优势，帮助警察叔叔快速找到所有答案。形如： 12+34+56+7-8+9 123+4+5+67-89 … 为了使问题更加有趣，我们把后面的数字110换成n。注意：这里只要求你计算方案数。不必输出每种方案。输入
一个整数n，如题所述。(-2000000000<=n<=2000000000)
输出 一个整数，表示方案数。
int main(){int str[9]={1,2,3,4,5,6,7,8,9};int i,j,temp,sum,num;int n,count;int operate=1;count=0;scanf("%d",&n);for(i=0;i<pow(3,8);i++){temp=i;sum=0;operate=1;num=str[0];for(j=1;j<9;j++){if(temp%3==0)num=num*10+str[j];if(temp%3==1){if(operate==1){sum+=num;num=str[j];}if(operate==2){sum-=num;num=str[j];}operate=1;}if(temp%3==2){if(operate==1){sum+=num;num=str[j];}if(operate==2){sum-=num;num=str[j];}operate=2;}temp/=3;}if(operate==1) sum=sum+num;if(operate==2) sum=sum-num; if(sum==n){count++;}
}printf("%d",count);return 0;
}
李白饮酒：话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱： 无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则babaabbabbabbbb 就是合理的次序。
像这样的答案一共有多少呢？请你计算出所有可能方案的个数。 为了使问题更加有趣，我们假设他遇到店s次，花f次，你的任务是计算此时的方案总数。输入 两个整数s和f，分别表示李白遇到的店和花的次数。（s+f<=20）
输出 一个整数，表示方案总数。
int main(){int s,f,i,j,t,flower,shop;int wine=2;int sum=0;scanf("%d%d",&s,&f);int n=s+f-1;for(i=0;i<pow(2,n);i++){wine=2;t=i;flower=shop=0;for(j=0;j<n;j++){if(t%2==1){wine=wine*2;shop++;} else if(t%2==0){wine--;flower++; }t=t/2; }if(shop==s&&flower==(f-1)&&wine==1)sum++;}printf("%d",sum);return 0;
}
全排列去重：素数就是不能再进行等分的数。比如：2、3、5、7、11 等。9 = 3 * 3 说明它可以3等分，因而不是素数。
我们国家在1949年建国。如果只给你 1、9、4和9 这4个数字卡片，可以随意摆放它们的先后顺序，那么，你能组成多少个4位的素数呢？
比如：1949，4919 都符合要求。 为了使问题更加有趣，我们输入n个数字，求这n个数字可以组成的数字中的素数。输入 第一行一个整数n。(n<=6) 第二行n个空格分隔的整数，仅包含1~9
输出 输出所有符合的素数。若没有可行解，则输出-1。
int n;
int index=-1;
int p[100000000];void Swap(int *a, int *b)
{int temp=*a;*a=*b;*b=temp;
}
int IsSwap(int* array,int start,int end)//若两个值相等则不交换，当前的两个值是array[i]与array[N],
{for(int i=start;i<end;i++){if(array[i]==array[end]){return 0;}}return 1;
}void FullPailie(int array[],int K,int N)//保证数组array前N个数不动，进行全排列
{if(K == N){index++;for(int i=0; i<=N; i++){p[index]+=array[i]*pow(10,n-1-i);}return;}for(int i=K; i<=N; i++){if(IsSwap(array,K,i)){Swap(&array[K],&array[i]);FullPailie(array,K+1,N);Swap(&array[K],&array[i]);}}
}int main(){int count=0;scanf("%d",&n);int a[n];for(int i=0;i<n;i++)scanf("%d",&a[i]);if(n==0)return 0;elseFullPailie(a,0,n-1);for(int i=0;i<=index;i++){printf("%d\n",p[i]);}printf("%d",index+1); }
支付宝扫一扫
微信扫一扫
.png)
.png)
.png)
