大发快三_快三最新网址_大发快三最新网址 - 由大发快三,快三最新网址,大发快三最新网址社主办的《大发快三,快三最新网址,大发快三最新网址》是我国消费领域中一张全国性、全方位、大容量的综合性日报。其立足消费网投领域,依托轻工行业,面向城乡市场,最先发布相关的专业权威资讯。

纸上谈兵: 数学归纳法, 递归, 栈

  • 时间:
  • 浏览:0

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 

数学归纳法

数学归纳法(mathematical induction)是四种 数学证明最好的办法,常用于证明命题(命题是对某个什么的问题的描述)在自然数范围内成立。随着现代数学的发展,自然数范围内的证明实际上构成了这种 这种 领域(比如数学分析)的基础,好多好多 有数学归纳法对于整个数学体系至关重要。

数学归纳法四种 非常简单。可能性亲戚亲戚朋友儿想要证明某个命题对于自然数n都成立,那末:

第一步 证明命题对于n = 1成立。

第二步 假设命题对于n成立,n为任意自然数,证明在此假设下,命题对于n+1成立。

命题得证

想一下上方的三个白步骤。它们实际上愿因 ,命题对于n = 1成立 -> 命题对于n = 2成立 -> 命题对于n = 3成立……直到无穷。后来,命题对于任意自然数都成立。这就好像多米诺骨牌,亲戚亲戚朋友儿选着n的倒下会愿因 n + 1的倒下,后来推倒第一块骨牌,就能保证任意骨牌的倒下。

亲戚亲戚朋友儿来看一下使用数学归纳法来证明高斯求和公式:

n为任意自然数。

(这种 公式据说是高斯小学时想出来的。老师惩罚全班同学,需要算出1到80的累加,不让 回家。于是高斯想出了上方的最好的办法。天才需要被逼出来的么?)

亲戚亲戚朋友儿的命题是: 高斯求和公式对于任意自然数n都成立。

下面为数学归纳法的证明步骤:

第一步 n = 1,等式左边(1的累加)为1,右边(右边公式代入n=1)也为1,等式两边相等,等式成立,后来命题对于 n = 1 成立。

第二步 假设上述公式对于任意n成立, 即1到n的累加为n*(n+1)/2

    那末,对于n+1,等式的左边(从1到n+1的累加)等于n*(n+1)/2 + (n+1),即(n+1)*(n+2)/2

                  等式的右边的n用n+1代替,成为(n+1)*(n+2)/2

    等式两边相等,等式成立。后来,当假设命题对于n成立时,命题对于n+1成立。

后来,命题得证。

递归

递归(recursion)是计算机中的重要概念,它是指三个白计算机多多线程 运行调用其自身。为了保证计算机不陷入死循环,递归要求多多线程 运行有三个白不让 达到的终止条件(base case)。比如下面的多多线程 运行,是用于计算高斯求和公式:

/*
 * Gauss summation
 */

int f(n)
{
    if (n == 1) { 
        return 1;  // base case
    }
    else {
        return f(n-1) + n;  // induction
    }
}

在多多线程 运行中规定了f(1)的值,以及f(n)和f(n-1)的关系。这正是数学归纳法思想的体现。想要得到f(n),需要计算f(n-1);想要f(n-1),需要计算f(n-2)……直到f(1)。可能性亲戚亲戚朋友儿可能性知道了f(1)的值,亲戚亲戚朋友儿就不让 填补前面所有的空缺,最终返回f(n)的值。

递归是数学归纳法在计算机中的多多线程 运行实现。使用递归设计多多线程 运行的后来,亲戚亲戚朋友儿设置base case,并假设亲戚亲戚朋友儿会获得n-1的结果,并实现n的结果。这就好像数学归纳法,亲戚亲戚朋友儿只关注初始和衔接,而需要关注具体的每一步。

递归是用栈(stack)数据特性实现的。正如亲戚亲戚朋友儿上方所说的,计算f(n),需要f(n-1);计算f(n-1),需要f(n-2)……。亲戚亲戚朋友儿在寻找到f(1)后来,会有这种 空缺: f(n-1)的值这种 ? f(n-2)的值是这种 ? …… f(2)的值是这种 ?f(1)的值是这种 ? 亲戚亲戚朋友儿的第三个白什么的问题是f(n)是这种 ,结果,这种 什么的问题引出下三个白什么的问题,再下三个白什么的问题…… 每个什么的问题的解答都依赖于下三个白什么的问题,直到亲戚亲戚朋友儿找到第三个白不让 回答的什么的问题: f(1)的值是这种 ?

亲戚亲戚朋友儿用栈来保存亲戚亲戚朋友儿在探索过程中的什么的问题。C语言中,函数的调用可能性是用栈记录离场情境和返回地址。递归是函数对自身的调用,好多好多 有很自然的,递归用栈来保存亲戚亲戚朋友儿的“什么的问题” 。

亲戚亲戚朋友儿假设栈向下增长。首先,亲戚亲戚朋友儿调用f(80),那末当执行到

return f(n-1) + n; 

f(80)暂停执行,并记录当前的情形,比如n的值,当前执行到的位置。后来调用f(99),栈增加三个白frame,直到调用f(98) ... 栈不断增长,直到f(1)。f(1)得到结果1,并返回给f(2)。f(1)栈frame删除,转移到f(2)frame情境中继续执行

return f(n-1) + n; 

后来返回给f(3) ... 直到f(99)返回给f(80),并执行

return f(n-1) + n; 

返回f(80)的值,得到结果。

上述过程是C编译器自动完成的。在实现递归算法时,不让 能自行手动实现栈。另三个白不让 得到更好的运行速度。

总结

数学归纳法

递归

欢迎继续阅读“纸上谈兵: 算法与数据特性”系列。