编程小博士(27)
软件世界
问：小博士，我今天碰到了一个“猴子分食桃子”的难题：五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这个桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？
想了半天，也理不出头绪。感觉上应该有专门的解题方法吧，你能介绍一种专门解决这类问题的算法吗？
小博士：算法就是对某类特定问题的解题步骤。算法有许多种，最简单的无非是下面的六种：递推法、贪心法、列举法、递归法、分治法和模拟法。刚听名字挺吓人的，其实有些方法我们平常都见过。这些算法当中，最简单的莫过于递推算法了。而它刚好能解决你说的“猴子分食桃子”的问题。
什么是递推法
递推法这种解题方法其实在我们编程的过程中用得很多，只不过没有将它上升到理论的高度罢了。所谓递推法，就是找出和时间先后相联系或和数的大小相联系的步骤，上一步和下一步与数字的增大或减小有一定的联系。我们要么从前向后(或从小到大)推导，也可从后向前(或从大到小)推导。由此得出两种推导方法：顺推法和倒推法。再来看看你说的问题。
编程简析
怎样编程呢？先要找一下第N只猴子和它面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去破解，可得出下面的推导式：
第N只猴 第N只猴前桃子数目
5 s5=x
4 s4=s5*5/4+1
3 s3=s4*5/4+1
2 s2=s3*5/4+1
1 s1=s2*5/4+1
s1即为所求。上面的规律中只要将s1-s5的下标去掉：
s=x
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
所以可以用循环语句加以解决。
综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s1-s4四个数必须全部为整数，这个可作为条件。具体实现请参看源程序。
源程序下载地址：http://www.cpcw.com/27/taozi.txt
小结
上面应用的推导方法就是倒推法。生活中的更多问题采用顺推法就可得到，也即从1-N，但不论倒推还是顺推，能递推并解出问题是我们的本意。