趣学算法 - (EPUB全文下载)

文件大小：0.36 mb。
文件格式：epub 格式。
书籍内容：

趣学算法
Chapter 1 算法之美
Chapter 2 贪心算法
Chapter 3 分治法
Chapter 4 动态规划
Chapter 5 回溯法
Chapter 6 分支限界法
Chapter 7 线性规划网络流
附录A 特征方程和通项公式
附录B sort函数
附录C 优先队列
附录D 邻接表
附录E 并查集
附录F 四边不等式
附录G 排列树
附录H 贝尔曼规则
附录I 增广路中称为关键边的次数
附录J 最大流最小割定理
欢迎来到异步社区！
Chapter 1　算法之美
1.1　打开算法之门
1.2　妙不可言——算法复杂性
1.3　美不胜收——魔鬼序列
1.4　灵魂之交——马克思手稿中的数学题
1.5　算法学习瓶颈
1.6　你怕什么
如果说数学是皇冠上的一颗明珠，那么算法就是这颗明珠上的光芒，算法让这颗明珠更加熠熠生辉，为科技进步和社会发展照亮了前进的路。数学是美学，算法是艺术。走进算法的人，才能体会它的魅力。
多年来，我有一个梦想，希望每一位提到算法的人，不再立即紧皱眉头，脑海闪现枯燥的公式、冗长的代码；希望每一位阅读和使用算法的人，体会到算法之美，像躺在法国普罗旺斯小镇的长椅上，呷一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香……
1.1　打开算法之门
瑞士著名的科学家N.Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
在我们的生活中，算法无处不在。我们每天早上起来，刷牙、洗脸、吃早餐，都在算着时间，以免上班或上课迟到；去超市购物，在资金有限的情况下，考虑先买什么、后买什么，算算是否超额；在家中做饭，用什么食材、调料，做法、步骤，还要品尝一下咸淡，看看是否做熟。所以，不要说你不懂算法，其实你每天都在用！
但是对计算机专业算法，很多人都有困惑：“I can understand, but I can’tuse！”，我能看懂，但不会用！就像参观莫高窟的壁画，看到它、感受它，却无法走进。我们正需要一把打开算法之门的钥匙，就如陶渊明《桃花源记》中的“初极狭，才通人。复行数十步，豁然开朗。”
1.2　妙不可言——算法复杂性
我们首先看一道某跨国公司的招聘试题。
写一个算法，求下面序列之和：
−1，1，−1，1，…，(−1)n
当你看到这个题目时，你会怎么想？for语句？while循环？
先看算法1-1：
//算法1-1
sum=0;
for(i=1; i<=n; i++) { sum=sum+(-1)^n; } 这段代码可以实现求和运算，但是为什么不这样算?！ 再看算法1-2： //算法1-2 if(n%2==0) //判断n是不是偶数，%表示求余数 sum =0; else sum=-1; 有的人看到这个代码后恍然大悟，原来可以这样啊？这不就是数学家高斯使用的算法吗？ 一共50对数，每对之和均为101，那么总和为： （1+100）×50=5050 1787年，10岁的高斯用了很短的时间算出了结果，而其他孩子却要算很长时间。 可以看出，算法1-1需要运行n+1次，如果n=100 00，就要运行100 01次，而算法1-2仅仅需要运行1次！是不是有很大差别？ 高斯的方法我也知道，但遇到类似的题还是……我用的笨办法也是算法吗？ 答：是算法。 算法是指对特定问题求解步骤的一种描述。 算法只是对问题求解方法的一种描述，它不依赖于任何一种语言，既可以用自然语言、程序设计语言（C、C++、Java、Python等）描述，也可以用流程图、框图来表示。一般为了更清楚地说明算法的本质，我们去除了计算机语言的语法规则和细节，采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间，它更符合人们的表达方式，容易理解，但不是严格的程序设计语言，如果要上机调试，需要转换成标准的计算机程序设计语言才能运行。 算法具有以下特性。 （1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。 （2）确定性：每条语句有确定的含义，无歧义。 （3）可行性：算法在当前环境条件下可以通过有限次运算实现。 （4）输入输出：有零个或多个输入，一个或多个输出。 算法1-2的确算得挺快的，但如何知道我写的算法好不好呢？ “好”算法的标准如下。 （1）正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。 （2）易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。 （3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，系统应该提示出错。 （4）高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次，因此不能用秒来具体计算算法消耗的时间，由于相同配置的计算机进行一次基本运算的时间是一定的，我们可以用算法基本运算的执行次数来衡量算法的效率。因此，将算法基本运算的执行次数作为时间复杂度的衡量标准。 （5）低存储性：低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小称为空间复杂度。 除了（1）～（3）中的基本标准外，我们对好的算法的评判标准就是高效率、低存储。 （1）～（3）中的标准都好办，但时间复杂度怎么算呢？ 时间复杂度：算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准。 看算法1-3，并分析算法的时间复杂度。 //算法1-3 sum=0; //运行1次 total=0; //运行1次 for(i=1; i<=n; i++) //运行n次 { sum=sum+i; ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。