计算机引论chap5-2讲

1、赵志燕(讲师)计算机科学与技术14级本科、软件工程14级本科信息工程学院计算机系 020213017020213017 第五章第五章 计算学科中的数学方法计算学科中的数学方法第第2 2讲讲数学的基本特征、数学方法的作用数学的基本特征、数学方法的作用数学概念和术语数学概念和术语集合：集合：函数和关系：函数和关系：等价关系等价关系：证明方法证明方法直接证明法和间接证明法直接证明法和间接证明法反证法反证法归纳法归纳法构造性证明构造性证明递归和迭代递归和迭代集合的乘积运算集合的乘积运算具有自反性、对称性、传递性具有自反性、对称性、传递性n2 2、间接证明法间接证明法证明证明ABAB，寻找的等价式进行证

2、明，通常用，寻找的等价式进行证明，通常用ABAB的逆的逆否命题（否命题（ ）。）。例例5.18 用间接证明法证明用间接证明法证明“若若p2是偶数，则是偶数，则p是偶数是偶数”。证明：假定此蕴含式后件为假，即假定证明：假定此蕴含式后件为假，即假定p是奇数。则对某个整数是奇数。则对某个整数k来说有来说有p=2k+1。由此可得。由此可得p2=4k2+4k+1=2（2k2+2k）+1，因此，因此，p2是奇数（它是一个整数的是奇数（它是一个整数的2倍加倍加1）。因为对这个蕴含式后件）。因为对这个蕴含式后件的否定蕴含着前件为假，因此该蕴含式为真。的否定蕴含着前件为假，因此该蕴含式为真。BA毕达哥拉斯学派的

3、无理；毕达哥拉斯学派的无理； 是无理数的证明是无理数的证明2 首先假定一个与原命题相反的命题成立，然后通过正确的推理得出与已知（或假设）条件、公理、已证过的定理等相互矛盾或自相矛盾的结果，用来证明原命题的正确。这种证明方法就是反证法，也称归谬法。希帕索斯（Hippasus） x22222q( 2)( )p两边同时平方则有：两边同时平方则有：22q2p-（1）因为因为q2为偶数，故为偶数，故q一定为偶数。一定为偶数。对某个整数对某个整数m来说，则有来说，则有: q = 2m - 将将 式代入式代入 式，可得：式，可得：(2m)2=2p2则有：则有： p2=2m2 由上可得：由上可得：p p和和q

4、 q均为偶数，均为偶数，与原假设与原假设p p和和q q互质相矛盾，互质相矛盾， 是无理数为真。是无理数为真。2归纳基础归纳基础:归纳步骤：归纳步骤： 证明证明P(1)为真；为真； 为真；为真；证明对任意的证明对任意的i1i1，若，若P(iP(i) )为真为真, ,则：则：P(i+1) P(i+1) 也为真。也为真。) 1 (p)( n)1()(npnp)(nnpn 1p(n)|证明：、归纳基础：、归纳基础：当当n= 1n= 1时，等式成立，即时，等式成立，即1=11=12 2 ；、归纳步骤：、归纳步骤：设对任意设对任意 k 1，P(k) 成立，即，成立，即， 1+3+5+(2k-1)= k2

5、，而而 1+3+5+(2K-1)+2(K+1)-1= K2+2K+1则当则当P(k) 成立时，成立时，P(K+1)也成立。也成立。根据数学归纳法，该命题得证。根据数学归纳法，该命题得证。= (K+1)2 )(xxp)(xxp例如：当求前例如：当求前n个自然数的和时：个自然数的和时： S(n)1+2+3+(n-1)+n= S(n-1)+n我们给出其形式表达式（通项公式）：我们给出其形式表达式（通项公式）： S(1)=1 当当n=1； S(n)S(n-1)+n 当当n1;递归的基本思想：递归的基本思想：利用利用前面已有的计算结果前面已有的计算结果和和相同的计算公式。相同的计算公式。这个例子还可以用

6、更一般的这个例子还可以用更一般的递归关系递归关系表示：表示： an=Can-1+g(n) , n = 2,3,4, 即：an=an-1+6 a1=6归纳步骤归纳基础nn-1解：解：a1=2 递归基础递归基础nn-1 解：解：F(0)=1 递归基础递归基础 F(n)=nF(n-1)，n =1,2,3, 递归步骤递归步骤思考：请写出斐波那契数列的递归定义。0,),1,(, 1(0),1 , 1(0, 1),(nmnmAmAnmAmnnmA递归基础递归基础递归递归步骤步骤Begin if m=0 thenelse else A(m-1,A(m,n-1) /自身调用的递归过程自身调用的递归过程 End

7、 n+1 /递归基础递归基础if n=0 thenA(m-1,1)例例5.25 计算计算A(1,2)解解: A(1,2)= A( , ) =A(0, ) =A(0, A(0, ) =A(0, A(0, ) ) =A(0, ) =4 0,),1,(, 1(0),1 , 1(0, 1),(nmnmAmAnmAmnnmA0A(1,1)A(0, A(1,0)A(0,1)23 逆向思维逆向思维设吃完后剩下设吃完后剩下x1x1个桃子，前一天未吃前的个桃子，前一天未吃前的桃子数目是桃子数目是x2x2，则：，则：x1=x2-(0.5x1=x2-(0.5x2+1),x2+1),即即 x2=2(x1+1)x2=2(x1+1)第十天第十天1第九天4第八天10第七天22第六天46第一天？x1x2=2(x1+1)x1x2=2(x1+1)x1x2=2(x1+1)递归定义：a1=1 n=1 an=2(an-1+1) n1a1a2a3a4a5a10函数形式：a(1)=1 n=1 a(n)=2(a(n-1)+1) n1Begin /a(n) 递归伪代码,本题n应取10 if