【C语言入门】由“换硬币”题目引发的思考

【Pt.I】问题概述：

小明手中有硬币，小红手中有若干张10元的纸币。已知 1 角硬币厚 1.8mm，5 角硬币厚 1.5mm，1 元硬币厚 2.0mm 。小红拿出若干张10元的纸币，小明要将 1 角的硬币放成一摞，将 5 角的硬币放成一摞，将 1 元的硬币放成一摞，如果 3 摞硬币一样高，且三摞硬币的金额之和正好等于小红要求的面值，则双方交换，否则没有办法交换。

输入： 
小红希望交换几张10元的纸币

输出：
1 角的数量,5 角的数量,1元的数量

<错误程序>

1. #include<stdio.h> 
2. int main() 
3. { 
4.    int n,one,five,ten; 
5.    int count=0; 
6.    scanf("%d",&n); 
7.      
8.    for(one=1;one<100;one++) 
9.     { 
10.       for(five=1;five<100;five++) 
11.       { 
12.           for(ten=1;ten<100;ten++) 
13.             { 
14.               if(one*1+five*5+ten*10==n*100 && 1.8*one==1.5*five && 1.5*five==2.0*ten) 
15.                { 
16.                   printf("%d,%d,%d\n",one,five,ten); 
17.                  count++; 
18.                } 
19.             } 
20.       } 
21.     } 
22.   if(count==0) 
23.    { 
24.       printf("No change.\n"); 
25.     } 
26. }

这看似是一个十分整洁完美的三重for循环，在Dev-C++编译器里也跑出了正确的结果。

然而，在OJ上却出现了两个用例输出错误，两个用例超时的情况。

【Pt.II】寻找问题

（一）两个输出错误

明明在Dev-C++编译器里可以得到正确输出，进了OJ却全部输出“No change.\n”。

很显然，问题只有可能出在循环的判断条件上。而最后得到“No change.\n”的结果，说明count变量不论如何始终为零。可以看出问题是使count++的判断条件始终不成立，即“one*1+five*5+ten*10==n*100 && 1.8*one==1.5*five && 1.5*five==2.0*ten”始终为0。

在“1.8*one==1.5*five”中，我们相当于将one和five两个int型变量转化成了浮点类型，其后运用了“浮点数==浮点数”的判断。而根据浮点数在内存中的表示形式可知，两个在现实中相等的浮点数却会存在微小的误差，也就是说，在计算机中是不相等的。

诚然根据这个规律，我们可以用“ if (某个极小数(浮点数A-浮点数B) < 0.000001) ”来代替 “ if (浮点数A == 浮点数B) ”，但在本题中，我们只需将 “ == “ 两边的常数乘以10，即可转化为int类型变量的相等判断，问题迎刃而解。

（二）两个超时错误

在这个阶段，超时错误多源于循环次数过多，所以应当优化循环结构，减少循环次数。

for循环次数的减少主要有两种途径：

（1）扩大i变量单次累加量

（2）改变i变量的初始值和终止值（即缩小可以进入循环的区间）

在本题中，硬币的单次累加量就可以扩大。取三种硬币厚度的最小公倍数，再除以每个硬币的厚度，得到该硬币的单次累加个数。

再根据硬币的厚度关系可以改变循环的终止条件。

【Pt.III】正解

最终得到正解：

<正确代码1>

 1 #include<stdio.h>
 2 int main()
 3 {
 4    int n,one,five,ten;
 5    int count=0;
 6    scanf("%d",&n);
 7
 8    for(one=0;one<100*n;one+=10)
 9  {
10       for(five=0;five<20*n;five+=12)
11         {
12           for(ten=0;ten*<10*n;ten+=9)
13             {
14               if(one*1+five*5+ten*10==n*100 && 18*one==15*five && 15*five==20*ten)
15                {
16                   printf("%d,%d,%d\n",one,five,ten);
17                  count++;
18                }
19           }
20       }
21   }
22   if(count==0)
23    {
24       printf("No change.\n");
25     }
26 }

（当然也可以在里面加一个gcd函数，我直接算出来了。）

【Pt.IV】总结

（1）两个在现实中相等的浮点数却会存在微小的误差，在计算机中是不相等的。

根据这个规律，我们可以用“ if (某个极小数(浮点数A-浮点数B) < 0.000001) ”来代替 “ if (浮点数A == 浮点数B) ”。

（尽可能不要作浮点数类型变量是否相等的判断）

（2）超时错误多源于循环次数过多，所以应当优化循环结构，减少循环次数。

for循环次数的减少主要有两种途径：

（1）扩大i变量单次累加量

（2）改变i变量的初始值和终止值（即缩小可以进入循环的区间）

第一篇博文！啦啦啦(～￣▽￣)～