这是一个C语言 for 循环嵌套的示例:过年了,外婆给了桐桐 100 元压岁钱,桐桐想把它兑换成 50 元、20 元、10 元的小钞票。请你编写程序,帮桐桐算算共有多少种兑换方案,并输出每一种兑换方案。
对于这个问题,我们可以使用枚举法来解决。枚举法就是将问题的所有可能答案全部列举出来,然后根据条件判断每个答案是否合适,合适的保留,不合适的就丢弃。
假设兑换方案中 50 元、20 元、10 元的钞票张数分别是 a、b、c,则:
50a+20b+10c=100
分析可知,a 的取值范围是 0~2,b 的取值范围是 0~5,c 的取值范围是 0~10,用 for 循环的嵌套枚举 a、b、c 所有的可能组合,对于每一种可能组合,判断上面的等式是否成立,如果等式成立,这一种组合就是一种兑换方案。
1) 定义 50 元、20 元、10 元钞票的可能张数 a、b、c;
2) 定义兑换方案数 Count,并初始化赋值 0;
3) 枚举 50 元钞票张数 a(0~2),枚举 20 元钞票张数 b(0~5),枚举 10 元钞票张数 c(0~10)。如果 50*a+20*b+10*c=100 成立,则
①Count = Count + 1;
②输出 a、b、c;
4) 输出 Count;
5) 结束。
代码清单 2:用枚举法找出 100 元钱所有可能的 50、20、10 元面额钞票的兑换组合
#include <stdio.h>
#include <stdlib.h>
int main( )
{
int a,b,c,Count=0;
for(a=0;a<=2;a++) //枚举50元钞票的可能张数
for(b=0;b<=5;b++) //枚举20元钞票的可能张数
for(c=0;c<=10;c++) //枚举10元钞票的可能张数
if(50*a+20*b+10*c==100) //判断是否是有效兑换组合
{
Count++;
printf("50:%d 20:%d 10:%d\n",a,b,c);
}
printf("100元钱共有以上%d种兑换方案!\n",Count);
system("pause");
return 0;
}
运行结果为:
50:0 20:0 10:10
50:0 20:1 10:8
50:0 20:2 10:6
50:0 20:3 10:4
50:0 20:4 10:2
50:0 20:5 10:0
50:1 20:0 10:5
50:1 20:1 10:3
50:1 20:2 10:1
50:2 20:0 10:0
100元钱共有以上10种兑换方案!
上面程序代码用了三层 for 循环,第三层 for 循环语句的循环体 if 语句总共执行了 3×6×11=198 次。事实上,知道了 a 和 b,就可以通过公式计算出 c:
c=(100-50×a-20×b)/10(c≥0)
因而,第三层 for 循环就不需要了,这样用来判断是否为有效兑换组合的 if 语句就只需执行 3×6=18 次,这样大大提高了程序的运行效率。
代码清单 3:用枚举法找出 100 元钱所有可能的 50、20、10 元面额钞票的兑换组合
#include <stdio.h>
#include <stdlib.h>
int main( )
{
int a,b,c,Count=0;
for(a=0;a<=2;a++) //枚举50元钞票的可能张数
for(b=0;b<=5;b++) //枚举20元钞票的可能张数
{
c=(100-50*a-20*b)/10; //对于每一组a、b组合,计算c
if(c>=0) //判断是否是有效的兑换组合
{
Count++;
printf("50:%d 20:%d 10:%d\n",a,b,c);
}
}
printf("100元钱共有以上%d种兑换方案!\n",Count);
system("pause");
return 0;
}
运行结果为:
50:0 20:0 10:10
50:0 20:1 10:8
50:0 20:2 10:6
50:0 20:3 10:4
50:0 20:4 10:2
50:0 20:5 10:0
50:1 20:0 10:5
50:1 20:1 10:3
50:1 20:2 10:1
50:2 20:0 10:0
100元钱共有以上10种兑换方案!