热门文档
- 2022-09-18 20:22:00 中国人为什么看不起中国人 张鸣
- 2023-04-19 15:04:26 《千家妙方 上册 1982年》(李文亮等编)
- 2023-10-13 17:09:40 楚辞 中华传统诗词经典 可复制-李山-9787101097528
- 2022-09-18 20:22:00 中国兵法之起源 编委会
- 2022-11-24 16:17:09 《性体验与性爱心理》尤里-谢尔巴特赫
- 2022-11-24 16:17:09 《性爱健康指南》石四维编著
- 2023-10-13 17:09:40 超速学习：我这样做，一个月学会素描，一年学会四种语言，完成MIT四年课程-斯科特·扬著，林慈敏译-9789861755533
- 2022-09-18 19:48:57 心理催眠术 迈克尔.赫普,温迪.德雷顿著
- 2023-10-13 17:09:40 初中诗词格律读本 可复制-周建忠 徐乃为 王业强编著-9787101121704
- 2023-10-13 17:09:40 曾国藩家书 中华经典藏书(升级版)可复制-檀作文译注-9787101115482
- 2023-01-11 15:23:39 孔子学院传播研究_刘程 安然著_9787516112922
- 2023-10-13 17:09:40 菜根谭 中华经典藏书(升级版)可复制-杨春俏译注-9787101115611
1、本文档共计 408 页，下载后文档不带www.pdfdz.com水印，支持完整阅读内容。
2、古籍基本都为PDF扫描版，所以文档不支持编辑功能，即不支持文档内文字的复制粘贴。
3、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
4、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
5、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。
2、古籍基本都为PDF扫描版，所以文档不支持编辑功能，即不支持文档内文字的复制粘贴。
3、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
4、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
5、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。
第1章当k=一1时，后一个公式不成立。此时我们需要下面的公式，这个公式在计算机科学中的使用要远比在数学其他科目中使用得多。数H、叫做调和数，其和叫做调和和。下面近似式中的误差趋向于y≈0.57721566，称为欧拉常数(Euler's constant)。2以下两个公式只不过是一般的代数运算：1.2.4模运算如果N整除A-B,那么就说A与B模N同余，记为A=B(odN)。直观地看，这意味着无论是A还是B被N去除，所得余数都是相同的。于是，81三61=1(md10)。如同等号的情形一样，若A=B(modN),则A+C=B+C(modN)以及AD=BD(modN)。有许多定理适用模运算，其中有些特别需要用到数论来证明。我们将尽量少使用模运算，这样，前面的一些定理也就足够了。1.2.5证明的方法证明数据结构分析中的结论的两种最常用的方法是归纳法证明和反证法证明（偶尔也被迫用到只有教授们才使用的证明)。证明一个定理不成立的最好的方法是举出一个反例。归纳法证明由归纳法进行的证明有两个标准的部分。第一步是证明基准情形(base case),就是确定定理对于某个（某些）小的（通常是退化的）值的正确性：这一步几乎总是很简单的。接着，进行归纳假设(inductive hypothesis)。一般说来，它指的是假设定理对直到某个有限数k的所有的情况都是成立的。然后使用这个假设证明定理对下一个值（通常是k+1)也是成立的。至此定理得证（在k是有限的情形下)。作为一个例子，我们证明斐波那契数，Fo=1,F,=1,F2=2,F3=3,F4=5,…,F:=F:-1+F:-2,满足对≥1，有F<(53)‘(有些定义规定F。=0,这只不过将该级数做了一次平移)。为了证明这个不等式，我们首先验证定理对简单的情形成立。容易验证F1=1<53及F2=2<25/9,这就证明了基准情形。假设定理对于i=1,2,·,k成立，这就是归纳假设。为了证明定理，我们需要证明F+1<(53)+'。根据定义得到F+1=F+F-1将归纳假设用于等号右边，得到F+1<(5/3)+(53)-1<(3/5)(5/3)*+1+(3/5)2(53)+1=(3/5)(53)+1+(925)(53)+1化简后为F+1<(3/5+9/25)(53)+1<(53)+1这就证明了这个定理。作为第二个例子，我们建立下面的定理。引论5定理1.36证明：用数学归纳法证明。对于基准情形，容易看到，当N=1时定理成立。对于归纳假设，设定理对1≤k≤N成立。我们将在该假设下证明定理对于N+1也是成立的。我们有应用归纳假设得到6=(N+1)22+7N+666因此6定理得证。通过反例证明公式F≤k2不成立。证明这个结论的最容易的方法就是计算F,=144>112。反证法证明反证法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而原假设是错误的。一个经典的例子是证明存在无穷多个素数。为了证明这个结论，我们假设定理不成立。于是，存在某个最大的素数P。令P1,P2,…,P,是依序排列的所有素数并考虑显然，N是比P大的数，根据假设N不是素数。可是，P,P2,…,P4都不能整除N,因为除得的结果总有余数1。这就产生一个矛盾，因为每一个整数或者是素数，或者是素数的乘积。因此，P是最大素数的原假设是不成立的，这正意味者定理成立。1.3递归简论我们熟悉的大多数数学函数都是由一个简单公式来描述的。例如，我们可以利用公式C=5(F-32)9将华氏温度转换成摄氏温度。有了这个公式，写一个Jv阳方法就太简单了。除去程序中的说明和大括号外，这一行的公式正好翻译成一行Java程序。有时候数学函数以不太标准的形式来定义。例如，我们可以在非负整数集上定义一个函数f,它满足f(0)=0且f(x)=2f(x-1)+x2。从这个定义我们看到f(1)=1,f(2)=6,f(3)=21,以及f(4)=58。当一个函数用它自己来定义时就称为是递归(recursive)的。Java允许函数是○对于数值计算使用递归通常不是个好主意。我们在解释基本概念时已经说过。
