一道简单的组合硬币的编程题

今天我弟来问了我一个C语言的题目，他刚上大一，初学C语言。

题目是这样的，有一分，两分和五分的硬币若干枚，现在要用五十枚硬币来拼出一块钱，（不多不少，刚好五十枚）问有几种方法？

我跟他说，你可以先尝试用最笨的办法：

for(int i=0;i<=50;i++)
    for(int j=0;j<=50;j++)
        for(int k=0;k<=50;k++)
            if (i+j+k==50&&1*i+2*j+5*k==100)
		        printf("i=%dj=%dk=%d\n",i,j,k);

每个硬币最多用到五十枚，这样用for循环找出答案，他明白了我的意思了，

之后，我加入了一个c变量，打印循环次数。

/*int c=0;*/
for(int i=0;i<=50;i++)
    for(int j=0;j<=50;j++)
        for(int k=0;k<=50;k++)
        {
            /*c++;*/
            if (i+j+k==50&&1*i+2*j+5*k==100)
		        printf("i=%dj=%dk=%d\n",i,j,k);
        }
/*printf("count is %d",c);*/

132651次，我对他说，是不是用了很多次？现在我们去改它。

其实，不用三层，你仔细想，如果一分和两分的确定了，那么五分的硬币个数是确定的。而且，如果确定有i个一分的硬币，那么两分的硬币只能是<=50-i个

for(int i=0;i<=50;i++)
    for(int j=0;j<=50-i;j++)
        if (1*i+2*j+5*(50-i-j)==100)
	        printf("i=%dj=%dk=%d\n",i,j,50-i-j);

这次我们的程序变成了1326次

我又想了想，其实，还可以用更少的次数，因为我们是从一分硬币出发的，它最多有五十个，但是如果从五分硬币出发，那么五分的最多只能是二十枚，即<=20

所以这次我们反过来，用i表示五分硬币，j表示两分硬币，k表示一分硬币

for(int i=0;i<=20;i++)
    for(int j=0;j<=50-i;j++)
        if(i*5+j*2+(50-i-j)==100)
	        printf("i=%dj=%dk=%d\n",i,j,50-i-j);

这次是861次。。。。

不过，第二层循环貌似还是有许多不必要，比如已经确定i个五分硬币，那么两分硬币的范围应该不超过(100-5i)/2 也就是说第二层也通过钱来划定，这样又能少些，

for(int i=0;i<=20;i++)
    for(int j=0;j*2<=100-5*i;j++)
    	if(i*5+j*2+(50-i-j)==100)
            printf("i=%dj=%dk=%d\n",i,j,50-i-j);

这次的循环数是541次….
如果你有更好的办法，欢迎留言，一起讨论，我的这篇博客，就算抛砖引玉了。