解决小猴吃枣问题

赵玉勇 
2001年 11期

    想必大家一定遇到过小猴吃枣问题：小猴第一天摘下若干枣子，当即吃掉了一半，不过瘾又多吃了一个；第二天吃了剩下的一半又多吃了一个；以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时，见到只剩下一个枣子了。问第一天这堆枣子有多少？
　　#1    一、循环解决方法
　　    刚遇到这个问题的时候，我们觉得它挺有趣的，罗列一下各种情况，不就是十天吗？后一天的数目是前一天的一半减一，也就是前一天是后一天加一的和再乘二，知道第十天是1，第九天就等于（1+1）*2=4，第八天等于（4+1）*2=10……以此类推，第一天总是能求出来的。于是我们想到了循环，设num为各天的数目，可以用以下的语句实现：
　　    num=1 ＇第十天时只剩1个枣子
　　    For i=9 To 1 Step -1
　　    Num=2*（num+1） ＇第九天到第一天规律是：后一天是前一天与1的和的两倍
　　    Next i
　　    Print num ＇TxtNum.Text=Str（num） ＇将结果输出
　　    上述方法有两个关键点：一是根据时间找出规律，并将循环变量和天数一致，第二点是对赋值运算（=）的正确理解，即num=2*（num+1）语句表示的不是=两边的相等关系，而是表达了题目中的条件：后一天是前一天与1的和的两倍，也就是说前一个num和后一个num所表示的数量和意义是不同的。
　　#1    二、递归解决方法
　　    递归究竟是什么东东呢？说白了它就像我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是……也就是在一个函数中调用了其自身。就像上面的故事那样，故事中包含了故事本身。下面就是对“老和尚讲故事”的定义：
　　    Private Function monkey（ByVal x As Integer） As Integer
　　    If x=10 Then ＇第十天时枣子为1个
　　    monkey=1
　　    Else ＇除第十天的其他九天规律是：后一天是前一天与1的和的两倍
　　    monkey=2*（monkey（x+1）+1）
　　    End If
　　    End Function
　　    我们可以通过Print monkey（1）或定义文本框控件TxtNum.Text=Str（monkey（1））来输出结果。
　　#1    三、一点补充
　　    大家不妨在自己的机器上试试，但要注意递归有时会出现栈溢出的问题，即递归的方法和老和尚讲故事的方法也是有区别的，只要老和尚知晓自己何时该不讲了，能收住声，递归也就成功了。以上程序在VB下运行成功。
　　
　　 
 