A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 柏森仁 中级黑马   /  2012-8-8 13:02  /  1819 人查看  /  2 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半,还是不过瘾又多
吃了一个。以后每天都吃前一天剩下的一半再加一个。到第10天刚好剩一个。问猴子第一天摘了多少个桃子?

分析: 这是一套非常经典的算法题,这个题目体现了算法思想中的递推思想,递归有两种形式,顺推和逆推,针对递推,只要
        我们找到递推公式,问题就迎刃而解了。
               令S10=1,容易看出 S9=2(S10+1), 简化一下
                 S9=2S10+2
                 S8=2S9+2
                     .....
                 Sn=2Sn+1+2

遥想公瑾当年,老师说递归是最简洁,最容易理解的,好,就用递归试一下:
  1. class Program
  2.      {
  3.          static void Main(string[] args)
  4.          {
  5.              int sum = SumPeach(1);

  6.              Console.WriteLine("第一天摘得桃子有:{0}", sum);

  7.              Console.Read();
  8.          }

  9.          //递归
  10.          static int SumPeach(int day)
  11.          {
  12.              if (day == 10)
  13.                  return 1;

  14.              return 2 * SumPeach(day + 1) + 2;
  15.          }
  16.      }
复制代码
当我们玩转递归的时候,老师说线性递归会将“变量,参数,返回值”在“递”的过程中压栈,如果迟迟“递”不到头的话,栈就会越积越多,
最后就爆掉了,window中系统默认的堆栈空间是1M。
那么解决方法是什么? 尾递归,下面我们继续上代码:
  1. class Program
  2.      {
  3.          static void Main(string[] args)
  4.          {
  5.              int sum = SumPeachTail(1, 1);

  6.              Console.WriteLine("第一天摘得桃子有:{0}", sum);

  7.              Console.Read();
  8.          }

  9.          //尾递归
  10.          static int SumPeachTail(int day, int total)
  11.          {
  12.              if (day == 10)
  13.                  return total;

  14.              //将当前的值计算出传递给下一层
  15.              return SumPeachTail(day + 1, 2 * total + 2);
  16.          }
  17.      }
复制代码


那么两种递归有什么区别呢?上图说话。



从图中我们可以清晰的看到“线性递归”和“尾递归”的区别,那到底有什么本质区别呢?尾递归中在每次向下递归的过程中,都会将当前
层的结果计算出来后向下一层传递,从理论上说,传到下一层后,上一层的参数值已经没有存在的必要了,可以清除上一层中的变量占
用的栈空间,那么最终达到的效果就是永远不会出现StackOverflowException了,但实际上是否真有这个效果,得要看编译程序是否
真的给你优化了。
下面我们将day=10改成day=int.MaxValue,跑一下程序看看:



很可惜,有图有真相,抛出异常了,当然我是菜鸟,早已看不懂汇编了,大家也可以讨论讨论,目前我个人认为C#编译器没有给
我做这个优化:-D。

下一步我们就要计算一下这个递归的时间复杂度是多少,关于求“递归”的时间复杂度主要有三种:
1.  代换法。
2.  递归树法。
3.  主定理。

这一篇我就说下代换法,作法如下
①:猜一下递归式复杂度的上界或者下界。
②:用数学归纳法证明你的复杂度是正确的。

为了具有通用性,我们将“猴子吃桃”的问题反过来写,也就是已知S1,求S10,当然原理是一样的,通用公式就有如下形式:
                 Tn=2Tn-1+2             ①  
假使           Tn=O(n)                   ②
则必定存在一个 c>0的自然数使
                Tn<=cO(n)=cn           ③
③代入①知
                Tn<=2c(n-1)+2=2cn-2c+2
                                      =cn-c+1
                                      =cn-(c-1)
当c>=1时,则必有 Tn<=cn  

最后得出递归式的时间复杂度为O(N)。

评分

参与人数 1技术分 +1 收起 理由
宋天琪 + 1

查看全部评分

2 个回复

倒序浏览
该算法采用递归思想解决,而且还进行了该算法的时间复杂度详细分析,值得学习!
回复 使用道具 举报
在游戏编程中,尾递归用的比较多,效率比较高些!这个帖子很好,值得学习!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马