有域名后如何建网站,静态商城网页模板,平面设计的软件都有什么,世界上有几个空间站猴子第一天摘下若干个桃子#xff0c;当即吃了一半#xff0c;还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半#xff0c;还是不过瘾又多吃了一个。以后每天都吃前一天剩下的一半再加一个。到第 10 天刚好剩一个。问猴子第一天摘了多少个桃子#xff1f; 分析: 这…猴子第一天摘下若干个桃子当即吃了一半还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半还是不过瘾又多吃了一个。以后每天都吃前一天剩下的一半再加一个。到第 10 天刚好剩一个。问猴子第一天摘了多少个桃子 分析: 这是一套非常经典的算法题这个题目体现了算法思想中的递推思想递归有两种形式顺推和逆推针对递推只要我们找到递推公式问题就迎刃而解了。 令S101容易看出 S92(S101) 简化一下 S92S102 S82S92 … Sn2Sn12 用递归试一下 class Program{static void Main(string[] args){int sum SumPeach(1);Console.WriteLine(第一天摘得桃子有:{0}, sum);Console.Read();}//递归static int SumPeach(int day){if (day 10)return 1;return 2 * SumPeach(day 1) 2;}}当我们玩转递归的时候老师说线性递归会将“变量参数返回值”在“递”的过程中压栈如果迟迟“递”不到头的话栈就会越积越多最后就爆掉了window 中系统默认的堆栈空间是 1M。 那么解决方法是什么 尾递归下面我们继续上代码 class Program{static void Main(string[] args){int sum SumPeachTail(1, 1);Console.WriteLine(第一天摘得桃子有:{0}, sum);Console.Read();}//尾递归static int SumPeachTail(int day, int total){if (day 10)return total;//将当前的值计算出传递给下一层return SumPeachTail(day 1, 2 * total 2);}}那么两种递归有什么区别呢 从图中我们可以清晰的看到“线性递归”和“尾递归”的区别那到底有什么本质区别呢尾递归中在每次向下递归的过程中都会将当前层的结果计算出来后向下一层传递从理论上说传到下一层后上一层的参数值已经没有存在的必要了可以清除上一层中的变量占用的栈空间那么最终达到的效果就是永远不会出现 StackOverflowException 了但实际上是否真有这个效果得要看编译程序是否真的给你优化了。 下面我们将 day10 改成 dayint.MaxValue跑一下程序看看 很可惜有图有真相抛出异常了。 下一步我们就要计算一下这个递归的时间复杂度是多少关于求“递归”的时间复杂度主要有三种
代换法。递归树法。主定理。
这一篇我就说下代换法作法如下 ①猜一下递归式复杂度的上界或者下界。 ②用数学归纳法证明你的复杂度是正确的。 为了具有通用性我们将“猴子吃桃”的问题反过来写也就是已知 S1求 S10当然原理是一样的通用公式就有如下形式 Tn2Tn-12 ① 假使 TnO(n) ② 则必定存在一个 c0 的自然数使 TncO(n)cn ③ ③ 代入 ① 知 Tn2c(n-1)22cn-2c2 cn-c1 cn-(c-1) 当 c1 时则必有 Tncn 最后得出递归式的时间复杂度为 O(N)。
