有10元，5元，2元，1元四种面值的人民币，问组成100元钱有多少种组合？
问题分析： 为了表达清楚，用 TEN , FIVE, TWO , ONE , 表示 10元，5元，2元，1元的人民币。
可知： 0 <= TEN <= 10 0 <= FIVE<= 10 0 <=TWO <= 10 0 <=ONE <= 10 TEN * 10 + FIVE * 5 + TWO * 2 + ONE = 100 有了这些表达式，可以利用穷举法编程，如下：
#include <stdio.h>
int main() { int i; int one; int two; int five; int ten; int count = 0; int cou = 0;
for(ten = 0; ten <= 10; ten++) { for(five = 0; five <= 20; five++) { for(two = 0; two <= 50; two++) { for(one = 0; one <= 100; one++) { cou++; if(ten * 10 + five * 5+ two * 2 + one == 100) { count++; } } } } } printf("一共循环了%d次\n",cou); printf("共有%d组合\n",count); }
运行结果：
这种算法需要的循环次数为 11 * 21 * 51 * 101 = 1189887 。 因为当 10元，5元，2元的张数确定后，一元的个数也就能确定了， ONE = 100 - 10 * TEN - 5 * FIVE - 2 * TWO; 这样可以省去最里面的循环，减少计算机运算次数。
优化程序如下：
#include <stdio.h>
int main() { int i; int one; int two; int five; int ten; int count = 0; int cou = 0;
for(ten = 0; ten <= 10; ten++) { for(five = 0; five <= 20; five++) { for(two = 0; two <= 50; two++) {
cou++; one = 100 - (ten * 10 + five * 5 + two * 2); if((one >= 0) && (ten * 10 + five * 5+ two * 2 + one == 100)) { count++; } } } } printf("一共循环了%d次\n",cou); printf("共有%d组合\n",count); }
运行结果：
这样循环次数就减少为 11781 次了。
