程序员的数学1.pdf

=图灵程序设计丛书【司结城浩著管杰译人民邮电出版杜北京心-:I,图书在版编目(CIP)数据程序员的数学（日）结城浩著；管杰译一北京：人民邮电出版社，2012.11(2012.12重印）（图灵程序设计丛书）ISBN 978-7-115-29368-8 I.CD程ILCD结管皿电子计算机一数学基础N.(D TP301.6 中国版本图书馆CIP数据核字(2012)第220660号内容提要本书面向程序员介绍了编程中常用的数学知识，借以培养初级程序员的数学思维。读者无需精通编程，也无需精通数学，只需具备四则运算和乘方等基础知识，就可以阅读本书。书中讲解了二进制计数法、逻辑、余数、排列组合、递归、指数爆炸、不可解问题等许多与编程密切相关的数学方法，分析了哥尼斯堡七桥问题、高斯求和方法、汉诺塔、斐波那契数列等经典问题和算法。引导读者深入理解编程中的数学方法和思路。本书适合程序设计人员以及编程和数学爱好者阅读。著译责任编辑执行编辑图灵程序设计丛书程序员的数学日结城浩管杰傅志红乐馨张靖 人民邮电出版社出版发行北京市崇文区夕照寺街14号邮编100061 电子邮件 网址http:/ 三河市海波印务有限公司印刷 开本,800X 1000 1/16 印张：15.5 字数I264千字2012年11月第1版印数I4001-6()()0册2012年12月河北第2次印刷著作权合同登记号图字：01-2012-3526号ISBN 978-7-115-29368-8 定价：49.00元读者服务热线：(010)51095186转604印装质量热线：(010)67129223 反盗版热线：(010)67171154 PROGRAMMER NO SUGAK.U 2005 Hiroshi Yuki All rights reserved.版权声明Original Japanese edition published in 2005 by SOFTBANK Creative Corp.Simplified Chinese Character translation rights arranged with SOFTBANK Creative Corp.through Owls Agency Inc.,Tokyo.本书中文简体字版由SOFTBANKCreative Corp.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。版权所有，侵权必究。iv I前言大家好！我是结城浩。欢迎阅读程序员的数学。本书是为程序员朋友们写的数学书。编程的基础是计算机科学，而计算机科学的基础是数学。因此，学习数学有助千巩固编程的基础，写出健壮的程序。有的读者可能会说“但我数学不好啊“。特别是很多读者”一碰到算式就跳过不读”。坦率而言，我自己遇到书中的算式也想跳过不看。本书尽可能减少了“大家不想看的算式”，也没有过多的定义、定理和证明。这是为帮助程序员更容易理解编程而写的书。希望你能通过本书学到有助千编程的“数学思维”。I数学思维示例学习“数学思维”说起来太抽象了，我们来举些具体的例子。【条件分支和逻辑】在编程时，我们按照条件将处理方法分为多个“分支“。C语言和Java语言中使用的是if语句。处理方法为：当满足条件时执行这条语句，不满足条件时执行另一语句。这时，我们就使用了数学领域的“逻辑”来控制程序。因此，编程时必须熟练掌握“与/或“、“非“、“蕴涵”等逻辑构成元素。【循环和数学归纳法】我们在处理大量的信息时，使用程序进行“循环”操作。比如使用for语句可以循环处理大量数据。循环中使用的就是“数学归纳法”。【分类和计数方法】在将许多条件和数据“分类”时，程序员必须注意不能有遗漏。这时加法法则、乘法法则、排列、组合等“计数方法”将助你一臂之力。这是程序员应该熟记于心的数学工具。通过本书，也可以学到递归、指数、对数、余数等重要的基础思维方式。v I人类和计算机的共同战线我们写程序是为了解决人类解决不了的问题。程序员理解问题，编写程序；计算机运行程序，解决问题。人类不擅长重复劳动，很容易厌倦，有时还会出错，但人类擅长解决问题。与此相对，计算机擅长重复劳动，但不能自行解决问题。千是，人机合力，如虎添翼。遇到难题，光靠人类不能解决，光靠计算机也不能解决。而人机合力就能解决问题。这也是本书要传达的主旨之一。不过，编写程序也非易事，无论人类和计算机如何齐心合力，总有解决不了的问题。本书也对人类和计算机的极限进行了分析。希望你在读完本书后能对以程序为媒介的人机合作有更深刻的理解。I本书面向的读者本书主要面向的读者是程序员。不过若你对编程或数学感兴趣，读起来也会一样有意思。你不需要精通数学。书中不会出现区和l等很难的算式，因此自认为数学不太好的读者也完全可以阅读。阅读本书只需具备四则运算+-x+)和乘方(23=2X2X2)等基础知识。除此以外的知识在书中皆有说明。如果你对数字和逻辑感兴趣，可能会更喜欢本书。你也不需要精通编程。不过如果稍有一些编程经验，可能会更容易理解本书内容。书中有个别例子是用C语言写的程序，不过即使不懂C语言也不妨碍理解。l本书结构本书各章内容可以按任意顺序阅读，但笔者推荐从第1章开始按顺序阅读。第1章对0进行讨论。以按位计数法为核心，学习如何用0来简化规则，并对“无即是有的意义进行了思考。vi 第2章学习使用逻辑来整理繁琐的内容。介绍逻辑表达式、真值表、德摩根定律、三值逻辑、卡诺图等。第3章讨论余数。我们要记住“余数就是分组”的观点。对千一些难题，有时只要找到周期性规律就能解决。第4章学习数学归纳法。数学归纳法只需要两个步骤就能证明无穷的断言。本章还会举例介绍使用循环不变式写出正确的循环。第5章学习排列组合等计数方法。计数的关键在于“认清对象的性质”。第6章学习自己定义自己的递归。通过汉诺塔、斐波那契数列、分形图形等，练习从复杂事物中发现递归结构。第7章学习指数爆炸。计算机也很难解决含有指数爆炸的问题。我们将在这里思考研究如何将指数爆炸为我所用，解决大型问题。另外本章还将以二分法检索为例，学习将问题空间一分为二的意义。第8章以停机问题为例，来说明许多程序上的问题是计算机如何发展都解决不了的。本章也会学到反证法和对角论证法。第9章回顾本书学习内容，思考人类全面把握结构的能力对解决问题有多大帮助，以及人机协作具有何种意义。I致谢首先要感谢马丁伽德纳。小时候我痴迷于阅读您所著的数学游戏，至今仍记忆犹新。此外，还要感谢支持我的广大读者和为我祈祷的基督教朋友们。以下各位为本书提出了宝贵建议并给予了极大帮助，在此深表谢意（按日语五十音图顺序）：天野胜、石井胜、岩泽正树、上原隆平、佐藤勇纪、武笠夏子、前原正英、三宅喜义。特别感谢在本书编写过程中给予我极大关怀和支持的SoftBank出版有限公司的野泽喜美男主编。感谢一直鼓励我的爱妻和两个儿子。本书献给在餐桌上教我方程式乃至微积分的父亲。父亲，谢谢您！2005年2月结城浩第1章目录0的故事无即是有本章学习内容2小学一年级的回忆210进制计数法.3 什么是10进制计数法.3 分解2503.3 2进制计数法.4 什么是2进制计数法4分解1100.5 基数转换.:.6 计算机中为什么采用2进制计数法8按位计数法.10 什么是按位计数法10不使用按位计数法的罗马数字11指数法则.12 10的0次方是什么121矿是什么.13 规则的扩展14对少进行思考142一1是什么.:.15 0所起的作用160的作用：占位.;:.16 viii I程序员的数学第2章0的作用：统一标准，简化规则.16 日常生活中的017人类的极限和构造的发现.18 重温历史进程18为了超越人类的极限.19 本章小结.20 逻辑真与假的二元世界本章学习内容.,.22 为何逻辑如此重要.,22 逻辑是消除歧义的工具22致对逻辑持否定意见的读者.23 乘车费用问题兼顾完整性和排他性23车费规则.:.23 命题及其真假.24 有没有遗漏“.24 有没有“重复“.25 画一根数轴辅助思考.26 注意边界值.28 兼顾完整性和排他性.28 使用if语句分解问题28逻辑的基本是两个分支29建立复杂命题30逻辑非一不是A.30 逻辑与一-A并且B.32 逻辑或一A或者B.34 异或一A或者B(但不都满足）.37 第3章目录Iix 相等-A和B相等.39 蕴涵一一若A则B40囊括所有了吗心45德摩根定律46德摩根定律是什么46对偶性.47 卡诺图.4g 二灯游戏.48 首先借助逻辑表达式进行思考49学习使用卡诺图50三灯游戏.52 包含未定义的逻辑54带条件的逻辑与(&55 带条件的逻辑或(II)57三值逻辑中的否定(!)58三值逻辑的德摩根定律58囊括所有了吗59本章小结.60 余数周期性和分组本章学习内容64星期数的思考题(1)64思考题(100天以后是星期几）.64 思考题答案.,64 运用余数思考.65 余数的力量一将较大的数字除一次就能分组65星期数的思考轰(2).66 XI程序员的数学思考题(10100天以后是星期几）.66 提示：可以直接计算吗.67 思考题答案.67 发现规律.68 直观地把握规律68乘方的思考题.70 思考题(1234567987654321).-70 提示：通过试算找出规律.70.70 思考题答案回顾：规律和余数的关系71通过黑白棋通信.71 思考题.71 提示.73 思考题答案.73 奇偶校验.73 奇偶校验位将数字分为两个集合.74 寻找恋人的思考题.74 思考题（寻找恋人）:.74 提示：先试算较小的数.74 思考题答案.75 回顾.75 铺设草席的思考题.77 思考题（在房间里铺设草席）.77 一.77 提示：先计算下草席数思考题答案.7g 回顾.7g 一笔画的思考题.79 思考题（哥尼斯堡七桥问题）.79 提示：试算一下.80 第4章目录Ixi 提示：考虑简化一下81提示：考虑入口和出口.82 思考题答案.82 奇偶校验.85 本章小结.86 数学归纳法如何征服无穷数列本章学习内容.88 高斯求和.88 思考题（存钱罐里的钱）88思考下一.89 小高斯的解答89讨论一下小高斯的解答.89 归纳.91 数学归纳法一如何征服无穷数列.91 0以上的整数的断言.92 高斯的断言.93 什么是数学归纳法93试着征服无穷数列94用数学归纳法证明高斯的断言95求出奇数的和一一数学归纳法实例96奇数的和96通过数学归纳法证明.97 图形化说明.98 黑白棋思考题-错误的数学归纳法99思考题（黑白棋子的颜色）99提示：不要为图所惑.100 xii I程序员的数学第5章思考题答案100编程和数学归纳法.101 通过循环表示数学归纳法101循环不变式103本章小结.107 排列组合解决计数问题的方法本章学习内容.110 计数一一与整数的对应关系.110 何谓计数.110 注意”遗漏”和“重复.111 植树问题一一不要忘记0.111 植树问题思考题.111 加法法则.115 加法法则.115 乘法法则.;.117 乘法法则.117 置换.,121 置换.121 归纳一下.122 思考题（扑克牌的摆法）.123 排列.125 排列.-125 归纳一下.126 树形图一能够认清本质吗128组合.,;.130 组合.130 第6章目录Ixiii 归纳一下.131 置换、排列、组合的关系132思考题练习.134 重复组合.134 也要善千运用逻辑136本章小结.39 递归自己定义自己本章学习内容142汉诺塔.142 思考题（汉诺塔）142提示：先从小汉诺塔着手143思考题答案146求出解析式148解出汉诺塔的程序149找出递归结构150再谈阶乘.151 阶乘的递归定义152思考题（和的定义）.153 递归和归纳.:153 斐波那契数列154思考题（不断繁殖的动物）.154 斐波那契数列157帕斯卡三角形159什么是帕斯卡三角形159递归定义组合数162组合的数学理论解释163xiv I程序员的数学第7章递归图形.165 以递归形式画树165实际作图.166