【项目：穷举法解决组合问题】（自选两题完成，其他的想一想即可。当然，全做完收效更好）

先阅读例题，领会穷举法（意为“穷尽式列举”，也称枚举）的思想，然后自行选题进行解决，掌握这种程序设计的一般方法。

例题：小明有五本新书，要借给A，B，C三位小朋友，若每人每次只能借一本，则可以有多少种不同的借法？

问题分析与算法设计：本问题实际上是一个排列问题，即求从5个中取3个进行排列的方法的总数。首先对五本书从1至5进行编号，然后使用穷举的方法。假设三个人分别借这五本书中的一本，当三个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。

下面是程序及其注释，要注意利用三重循环“穷举”：

#include <iostream> 
using namespace std;
int main()
{
	int a,b,c,count=0;
	cout<<"小明借书给三位小朋友书的方案有："<<endl;
	for(a=1;a<=5;a++)			//穷举a借5本书中的1本的全部情况
		for(b=1;b<=5;b++)		//穷举b借5本书中的一本的全部情况
			for(c=1;c<=5;c++)	//穷举c借5本书中的1本的全部情况
				if(a!=b&&c!=a&&c!=b) //判断三个人借的书是否不同，(a-b)*(b-c)*(c-a)!=0更好
				{
					++count;
					cout<<count<<": "<<a<<", "<<b<<", "<<c<<endl;//输出方案
				}
	return 0;
}

任务：利用穷举的方法解决下面的问题（选做一道即算完成任务，其他可以抽时间***安排，多做会使你更聪明。）

（1）百钱百鸡问题：中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？

提示：设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程：

5x+3y+z/3=100

x+y+z=100

所以此问题可归结为求这个不定方程的整数解。

由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。

引申：这类求解不定方程的实现，各层循环的控制变量直接与方程未知数有关，且采用对未知数的取值范围上穷举和组合的方法来复盖可能得到的全部各组解。如果要采取技巧，往往是根据题意，更合理地设置循环控制条件来减少这种穷举和组合的次数，提高程序的执行效率，需要具体问题具体分析。

参考解答：

#include <iostream>
using namespace std;
int main()
{
	int x,y,z;       //定义数据类型为整型，买鸡和买烤鸡不是一个概念
	for(x=0;x<=20;++x)
		for(y=0;y<=33;++y)  //穷举中。。。。
			for(z=0;z<=300;++z)
				if(5*x+3*y+z/3==100 && x+y+z==100 && z%3==0)
				{
					cout<<"鸡翁"<<x<<"只，鸡母"<<y<<"只，鸡雏"<<z<<"只。"<<endl;
				}
	return 0;
}

运行结果：

改进一：

#include <iostream>
using namespace std;
int main()
{
	int x,y,z;       //定义数据类型为整型，防止出现买烤鸡情况的出现
	for(x=0;x<=20;++x)
		for(y=0;y<=33;++y)  
			for(z=0;z<=300;z+=3)  //既然z要整除3，每次自加3去保证，少了循环，也少了判断
				if(5*x+3*y+z/3==100 && x+y+z==100)
				{
					cout<<"鸡翁"<<x<<"只，鸡母"<<y<<"只，鸡雏"<<z<<"只。"<<endl;
				}
	return 0;
}

改进二：

#include <iostream>
using namespace std;
int main()
{
	int x,y,z;       
	for(x=0;x<=20;++x)
		for(y=0;y<=33;++y)  
		{
			z=100-x-y;   //鸡雏数就此确定，何须再去试探——穷举只是笨办法，人可以让计算机轻松些
			if(5*x+3*y+z/3==100&&z%3==0)
					cout<<"鸡翁"<<x<<"只，鸡母"<<y<<"只，鸡雏"<<z<<"只。"<<endl;
		}
	return 0;
}

（2）换分币：用一元人民币兑换成1分、2分和5分硬币，有多少种不同的兑换方法？请输出所有可能的方案。

提示：根据题意设i,j,k分别为兑换的1分、2分、5分硬币的枚数，则i,j,k的值应满足：i+j*2+k*5=100，根据取值范围构造循环解题即可。

参考解答：

提示：根据题意设i,j,k分别为兑换的1分、2分、5分硬币的枚数，则i,j,k的值应满足：i+j*2+k*5=100，根据取值范围构造循环解题即可。

#include<iostream>
using namespace std;
int main()
{
	int i,j,k,count=0;
	for(i=0;i<=100;i++)
		for(j=0;j<=50;j++)
			for(k=0;k<=20;k++)
			{
				if(i+j*2+k*5==100)
				{
					++count;
					cout<<"第"<<count<<"种";
					cout<<" "<<"1分钱:"<<i;
					cout<<" "<<"2分钱:"<<j;
					cout<<" "<<"5分钱:"<<k<<endl;
					if(count%50==0)   //每输出50个方案暂停一次
					{
						cout<<"按任意键继续输出（找不到任意键打客服电话问询）……"<<endl;
						getchar();
					}
				}
			}
	return 0;
}

运行结果：

（3）年龄几何：张三、李四、王五、刘六的年龄成一等差数列，他们四人的年龄相加是26，相乘是880，求以他们的年龄为前4项的等差数列的前20项。

提示：设数列的首项为n，项差为a，则前4项之和为n+(n+a)+(n+a+a)+(n+a+a+a)=4*n+6*a"，前4 项之积为n*(n+a)*(n+a+a)*(n+a+a+a)。同时有1<=a<=4和1<=n<=6。可采用穷举法求出此数列。

参考解答：

#include<iostream>  
using namespace std;  
int main()  
{  
    int a,n,i,s;  
    for(a=1;a<=4;a++)  //枚举
        for(n=1;n<=6;n++)  
			if(n*4+a*6==26 && n*(n+a)*(n+a+a)*(n+a+a+a)==880)  
			{
				cout<<n;  //输出第1个
				for(i=1;i<20;i++)  
				{  
					s=n+a*i;  
					cout<<","<<s;  //后面的19个都和前一个用逗号分隔输出
				}  
				cout<<endl;  
			}
	return 0;  
}  

运行结果：

（4）三色球问题：若一个口袋中放有12个球，其中有3个红的。3个白的和6个黒的，问从中任取8个共有多少种不同的颜色搭配？

提示：设任取的红球个数为i，白球个数为j，则黒球个数为8-i-j，根据题意红球和白球个数的取值范围是0~3，在红球和白球个数确定的条件下，黒球个数取值应为8-i-j<=6。

参考解答：

#include<iostream>
using namespace std;
int main ()
{
	int red,white,black;
	cout<<"不同的颜色搭配有:"<<endl;
	for(red=0;red<=3;red++)
		for(white=0;white<=3;white++)
		{
			black=8-red-white;
			if(black<=6)
			{
				cout<<"红球:"<<red<<","<<"白球:"<<white<<","<<"黑球:"<<black<<endl;
			}
		}
	return 0;
}

运行结果：

（5）委派任务：某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：

l A和B两人中至少去一人；

l A和D不能一起去；

l A、E和F三人中要派两人去；

l B和C都去或都不去；

l C和D两人中去一个；

l 若D不去，则E也不去。

问应当让哪几个人去？

提示：用a、b、c、d、e、f六个变量表示六个人是否去执行任务的状态，变量的值为1，则表示该人去；变量的值为0，则表示该人不参加执行任务，根据题意可写出表达式：

l a+b>1     //A和B两人中至少去一人；

l (a+d)!=2      //A和D不能一起去；

l a+e+f==2     // A、E、F三人中要派两人去；

l b+c==0或b+c==2     // B和C都去或都不去；

l c+d==1      //C和D两人中去一个；

l d+e==0或d==1       //若D不去，则E也不去(都不去；或D去E随便)。

上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。

参考解答：

#include<iostream>  
using namespace std;  
int main()
{
	int a,b,c,d,e,f;
	for(a=1;a>=0;a--) //穷举每个人是否去的所有情况
		for(b=1;b>=0;b--) //1:去 0:不去
			for(c=1;c>=0;c--)
				for(d=1;d>=0;d--)
					for(e=1;e>=0;e--)
						for(f=1;f>=0;f--)
							if(a+b>=1&&a+d!=2&&a+e+f==2&&(b+c==0||b+c==2)&&c+d==1&&(d+e==0||d==1))
							{
								cout<<"A "<<(a?"":"不")<<"去。"<<endl;
								cout<<"B "<<(b?"":"不")<<"去。"<<endl;
								cout<<"C "<<(c?"":"不")<<"去。"<<endl;
								cout<<"D "<<(d?"":"不")<<"去。"<<endl;
								cout<<"E "<<(e?"":"不")<<"去。"<<endl;
								cout<<"F "<<(f?"":"不")<<"去。"<<endl;
							}
	return 0;
}

运行结果：

（6）在下面的加法算式中，不同的符号代表不同的数字，相同的符号代表相同的数字。请设计程序求出"都、要、学、C"4个符号分别代表的数字。

提示：让计算机解奥数题。穷举"都、要、学、C"4个符号分别代表的数字（从0到9），然后进行组合，如果组合起来符合规则（不同的符号代表不同的数字，相同的符号代表相同的数字，且使等式成立），则为正解。

参考解答：未优化前的代码 

#include <iostream>  
using namespace std;  
int main()  
{ 
	int dou,yao,xue,c,s;//变量这样取，比用i,j,p,q之类的要清晰得多
	for(dou=1;dou<3;dou++)
		for(yao=0;yao<10;yao++)
			for(xue=0;xue<10;xue++)
				for(c=0;c<10;c++)
					if((dou-yao)*(dou-xue)*(dou-c)*(yao-xue)*(yao-c)*(xue-c)!=0)//一个技巧：表示两两不同可以这样做
					{
						s=4*c+3*xue*10+2*yao*100+dou*1000;
						if(2008==s) 
							cout<<"都："<<dou<<" 要："<<yao<<" 学："<<xue<<" C："<<c<<endl;
					}
	return 0;
}  

运行结果

效率更高的解法 

#include <iostream>  
using namespace std;  
int main()  
{ 
	int dou,yao,xue,c,s;
	for(dou=1;dou<3;dou++)
		for(yao=0;yao<10;yao++)
		{
			if(dou==yao) continue;//“都”和“要”的取值如果相同了，将不再考虑另外两字的取值，效果可观
			for(xue=0;xue<10;xue++)
			{
				if(xue==yao||xue==dou) continue;  //理由同上
				for(c=0;c<10;c++)
					if((dou-c)*(yao-c)*(xue-c)!=0)
					{
						s=4*c+3*xue*10+2*yao*100+dou*1000;
						if(2008==s) 
							cout<<"都："<<dou<<" 要："<<yao<<" 学："<<xue<<" C："<<c<<endl;
					}
			}
		}
	return 0;
}

视频讲解：http://www.tudou.com/programs/view/InJLdkTDKSQ/

（7）警察局抓住了A、B、C、D四名盗窃嫌疑犯，其中只有一人是小偷。在审问时，A说：“我不是小偷”；B说：“C是小偷”；C说：“小偷肯定是D”；D说：“C在冤枉好人”。现在已经知道这四人中有三人说的是真话，一人说的是假话。请问到底谁是小偷？

提示：设4个变量a,b,c,d，为0时表示不是小偷，为1时表示是小偷，用四重循环穷举a,b,c,d可能的取值的组合，对每一种组合判断其是否符合题目中给出的约束。最后结论：C是小偷。

参考解答：

#include<iostream>  
using namespace std;  
int main()
{
	int a,b,c,d;
	for(a=1;a>=0;a--) //穷举每个人是否是小偷的所有情况
		for(b=1;b>=0;b--) //1:是小偷 0:不是
			for(c=1;c>=0;c--)
				for(d=1;d>=0;d--)
					if((a==0)+(c==1)+(d==1)+(d==0)==3&&a+b+c+d==1) //4人的说法中有3个真的，且只有一个小偷 
					{
						cout<<"A "<<(a?"":"不")<<"是。"<<endl;
						cout<<"B "<<(b?"":"不")<<"是。"<<endl;
						cout<<"C "<<(c?"":"不")<<"是。"<<endl;
						cout<<"D "<<(d?"":"不")<<"是。"<<endl;
					}
	return 0;
}

下面一个程序的写法中，注意“4人的说法中有3个真的”(即if语句部分)的写法，理解了，就又是一个提高！要点，例：

当a为0时!a为1,a为1时!a为0，等同于a==0及a!=1的值，即　　　

a	!a	a==0	a!=1
0	1	1	1
1	0	0	0

#include<iostream>  
using namespace std;  
int main()
{
	int a,b,c,d;
	for(a=1;a>=0;a--) //穷举每个人是否是小偷的所有情况
		for(b=1;b>=0;b--) //1:是小偷 0:不是
			for(c=1;c>=0;c--)
				for(d=1;d>=0;d--)
					if((!a)+(c)+(d)+(!d)==3&&a+b+c+d==1) //!a与a==0或a!=1完全等价，其他同 
					{
						cout<<"A "<<(a?"":"不")<<"是。"<<endl;
						cout<<"B "<<(b?"":"不")<<"是。"<<endl;
						cout<<"C "<<(c?"":"不")<<"是。"<<endl;
						cout<<"D "<<(d?"":"不")<<"是。"<<endl;
					}
	return 0;
}

（8）有等式[※×(※3+※)]2=8※※9，其中※处为1个数字，滴上了墨水无法辨认。请编程找出※表示哪个数字。

拓展：有等式[※×(※3○※)]2=8※※9，其中※处为1个数字，○处为+、-、×、÷四个运算符之一，现滴上了墨水无法辨认。请编程找出※表示哪个数字，○表示哪个运算符。

参考解答：用a,b,c,d,e分别代表※处的数字，有

#include<iostream>  
using namespace std;  
int main()
{  
    int a,b,c,d,e,s;  
    for(a=0;a<=9;a++)  
    {  
        for(b=0;b<=9;b++)  
        {  
            for(c=0;c<=9;c++)  
            {  
                for(d=0;d<=9;d++)  
                {  
                    for(e=0;e<=9;e++)  
                    {  
                        s=a*(b*10+3+c);  
                        if (s*s==8000+d*100+e*10+9)  
                        {  
                            cout<<"等式为：["<<a<<"×("<<b<<"3+"<<c<<")]^2=8"<<d<<e<<"9)"<<endl;  
                        }  
						
                    }  
                }  
            }  
        }  
    } 
	return 0;
}   

运行结果

拓展：有等式[※×(※3○※)]^2=8※※9，其中※处为1个数字，○处为+、-、×、÷四个运算符之一，现滴上了墨水无法辨认。请编程找出※表示哪个数字，○表示哪个运算符。

参考解答：

#include<iostream>  
using namespace std;  
int main()
{  
    int i,a,b,c,d,e,s;  
    for(a=0;a<=9;a++)  
    {  
        for(b=0;b<=9;b++)  
        {  
            for(c=0;c<=9;c++)  
            {  
                for(d=0;d<=9;d++)  
                {  
                    for(e=0;e<=9;e++)  
                    {  
                        s=a*(b*10+3+c);  
                        if (s*s==8000+d*100+e*10+9)  
                        {  
                            cout<<"等式为：["<<a<<"×("<<b<<"3+"<<c<<")]^2=8"<<d<<e<<"9)"<<endl;  
                        } 
						s=a*(b*10+3-c);  
                        if (s*s==8000+d*100+e*10+9)  
                        {  
                            cout<<"等式为：["<<a<<"×("<<b<<"3-"<<c<<")]^2=8"<<d<<e<<"9)"<<endl;  
                        } 
						s=a*((b*10+3)*c);  
                        if (s*s==8000+d*100+e*10+9)  
                        {  
                            cout<<"等式为：["<<a<<"×("<<b<<"3*"<<c<<")]^2=8"<<d<<e<<"9)"<<endl;  
                        } 
						if(c!=0)
						{
							s=a*((b*10+3)/c);  
							if (s*s==8000+d*100+e*10+9)  
							{  
								cout<<"等式为：["<<a<<"×("<<b<<"3÷"<<c<<")]^2=8"<<d<<e<<"9)"<<endl;  
							}
						}
                    }  
                }  
            }  
        }  
    } 
    return 0; 
}  

运行结果