解决小猴吃枣问题

Author: 赵玉勇 Date: 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下运行成功。