文档介绍:算法设计中的基本方法
人们希望计算机求解的问题是千差万别的,所设计的求解算法也千差万别,一般来说, 算法设计没有什么固定的方法可循。但是通过大量的实践,人们也总结出某些共性的规律, 其中包括递归方法、分治方法、贪心法、回溯法、动态3=15+60+=
5*7+3*13+80/3=35+39+=
5*11+3*6+83/3=55+18+=^100
显然,这三组解不满足数学方程,但由于我们在C语言中,进行int型除法时,77/3 的结果就是25 , 80/3 的结果就是26 , 83/3 的结果就是27,这也是计算机在处理整型数据 时的特点,在进行除法运算时,对于商的小数部分不再进行处理,直接截断。所以就造成 了在数学上本来不成立的方程,在计算机中成立了。
产生这个问题的根本原因就是我们在分析问题的过程中忽略了一个重要条件,变量z 要能够被3 整除。为了解决这个问题我们要在原来两个方程的基础上增加一个判断条件:
z%3==0
经过修改后,我们可以得到新的程序2:
程序 2:
#include >
main( )
{ int x, y, z, j=0;
for (x=0; x<=20; x++)
for (y=0; y<=33; y++)
for (z=0; z<=100; z++)
if ( z%3==0 && x+y+z==100 && 5*x+3*y+z/3==100 ) /* 增加了 z%3==0 */ printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, z ) ;
}
再次运行程序,可以得到正确的结果:
1: cock= 0
hen=25
chicken=75
2: cock= 4
hen=18
chicken=78
3: cock= 8
hen=11
chicken=81
4: cock=12
hen= 4
chicken=84
为了保证变量z能够整除3,我们还可以换一个思路,在与z有关的for循环上作文章。 程序2的循环中变量z每次+1,这样z就很可能不时3的倍数,我们可以对此进行优化, 让变量 z 每次循环不是加1,而是加 3,这样就可以保证变量 z 一定是 3 的倍数,因此我 们就可以省略判断z是否可以被3整除的过程。
按照这样的思路,我们可以得到程序3。
程序 3:
#include <>
main( )
{int x, y, z, j=0;
for (x=0; x<=100; x++) for (y=0; y<=100; y++)
/* j为计数器,记录解的数量*/
/*穷举变量x */
for (z=0; z<=100; z+=3)
/*穷举变量Z,每次增加的步长为3 */
/* 穷举变量 y */
if ( x+y+z==100 && 5*x+3*y+z/3==100 ) /* 判断是否满足两个方程 */
printf("%2d:cock=%2d hen=%2d chicken=%2d\n", ++j, x, y, Z); }
运行程序 3,也可以得到正确的结果。