【例10-10】有苹果、橘子、香蕉、菠萝、梨这5种水果,已知每个果盘中一定有3种水果,并且3种水果的种类各不相同。编程计算可以制作出多少种水果拼盘。
【分析】
本题最容易最直观的解法就是使用穷举法。如果用3种变量x、y、z表示每一种果盘中的3种水果,用常量1~5分别表示拼过、橘子、香蕉、菠萝、梨这5种水果,将1~5分别复制给变量x、y、z,每一种赋值表示一种装盘方法,那么不难想象共有5exp3(5的3次方)种装盘方案。这5exp3种装盘方案构成了本题的解空间。但是5exp3种方案并不全是答案,因为题目要求每个果盘中3种水果的种类各不相同,因此需要添加约束条件x!=y!=z。这样就很容易得到解决本题的算法。
fruitPlate()
{
int x,y,z,count=0;
for(x=1;x<=5;x++)
for(y=1;y<=5;y++)
for(z=1;z<=5;z++)
{
if(x!=y && y!=z && x!=z)
输出一种拼盘方案,并计数
}
}
通过上述算法fruitPlate()可以得到符合要求的片盘方案。在这里使用一个三重循环,使得变量x、、y、z在1~5之间有规律地改变,从而得到5exp3种不同的组合形式。当x!=y,y!=z,x!=z时符合题目要求的答案。
下面给出完整的测试程序,程序清单10-10
#include "stdio.h"
char fruit[][10]={"apple","orange","banana","pineapple","pear"};
int fruitPlate()
{
int x,y,z,count=0;
for(x=1;x<=5;x++)
for(y=1;y<=5;y++)
for(z=1;z<=5;z++)
{
if(x!=y && y!=z && x!=z)
{
count++; /*计数*/
printf("%9s,%9s,%9s\n",fruit[x-1],fruit[y-1],fruit[z-1]); /*输出每一种结果*/
}
}
return count; /*返回拼盘的种类数*/
}
main()
{
printf("There are %d kinds of motheds for arranging plate.\n",fruitPlate()) ;
getche();
}
本程序的运行结果如图所示
《妙趣横生的算法》第10章 算法设计与数据结构面试精粹之常见的算法设计题10-10(question?)