百钱买百鸡问题

来自计算思维百科
跳转至: 导航搜索

穷举法还可以用于解决中国古代著名趣题、进行逻辑推理判定,求解百钱百鸡、五家共井、谁做的好事、四大湖等问题。排序中的冒泡排序、选择排序也是穷举法。

公元5世纪末,中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?意思是公鸡每只5元、母鸡每只3元、小鸡3只1元,用100元钱买100只鸡,求公鸡、母鸡、小鸡的只数。

百钱百鸡问题在很多书籍中都作为穷举法的一个典型案例。设鸡翁、鸡母、鸡雏的个数分别为x、y、z,根据题意,可得如下方程:

5x+3y+z/3 = 100                                               

x+y+z = 100                                                  

1≤x<20, 1≤y<33, 3≤z<100, z mod 3 = 0                               

用穷举法求解,即在有限集合:1≤x<20, 1≤y<33,3≤z<100中,对每组x、y、z的值,计算x+y+z=100,5x+3y+z/3=100,z mod 3=0三个条件是否成立,从而找出百鸡问题的解。