搜索
高级检索
高级搜索
书       名 :
著       者 :
出  版  社 :
I  S  B  N:
文献来源:
出版时间 :
程序员的数学
0.00    
图书来源: 浙江图书馆(由图书馆配书)
  • 配送范围:
    全国(除港澳台地区)
  • ISBN:
    9787115293688
  • 作      者:
    (日)结城浩著
  • 出 版 社 :
    人民邮电出版社
  • 出版日期:
    2012
收藏
编辑推荐

  

  如果数学不好,是否可以成为一名程序员呢?答案是肯定的。 《程序员的数学》适合:数学糟糕但又想学习编程的你
  没有晦涩的公式,只有好玩的数学题。
  帮你掌握编程所需的“数学思维”。
  日文版已重印14次!

展开
作者简介

  结城浩(Hiroshi Yuki),生于1963年,日本专业技术作家和程序员。在编程语言、设计模式、数学、加密技术等领域,编写了很多深受欢迎的入门书。代表作有《数学女孩》系列、《程序员的数学》等。


  管杰,毕业于复旦大学日语系。现为对日软件工程师,多年日语技术文档编写经验。爱好日汉翻译和日本文化史,译有《明解C语言:入门篇》等。

展开
内容介绍
  《图灵程序设计丛书:程序员的数学》面向程序员介绍了编程中常用的数学知识,借以培养初级程序员的数学思维。读者无需精通编程,也无需精通数学,只需具备四则运算和乘方等基础知识,就可以阅读《程序员的数学》。  书中讲解了二进制计数法、逻辑、余数、排列组合、递归、指数爆炸、不可解问题等许多与编程密切相关的数学方法,分析了哥尼斯堡七桥问题、高斯求和方法、汉诺塔、斐波那契数列等经典问题和算法。引导读者深入理解编程中的数学方法和思路。  《程序员的数学》适合程序设计人员以及编程和数学爱好者阅读。
展开
精彩书摘
  ◎课前对话
  老师:假设现在有一排多米诺骨牌。如何将它们全部推倒呢?
  学生:这个简单!只要将它们排列成其中1 个一倒就能顺次带倒下一个的形状就行了。
  老师:这样还不够喔!
  学生:啊?为什么呢?
  老师:因为还需要推倒第一个多米诺骨牌。
  学生:那不是理所当然的嘛!
  老师:正是!这样你就能理解数学归纳法的两个步骤了。
  本章学习内容
  本章我们要学习的是数学归纳法。数学归纳法是证明某断言对于0 以上的所有整数(0,1,2,3…)都成立的方法。整数0,1,2,3…有无穷个,但若使用数学归纳法,只需经过"2个步骤",就能证明有关无穷的命题。
  首先,我们以求出1 到100 之和为例介绍数学归纳法。接着会穿插几道思考题来看一下数学归纳法的具体实例。最后,我们会讨论数学归纳法和编程的关系,一起了解一下循环不变式。
  高斯求和
  思考题(存钱罐里的钱)
  思考题(存钱罐里的钱)
  在你面前有一个空存钱罐。
  第1 天,往存钱罐里投入1 元。存钱罐中总金额为1 元。
  第2 天,往存钱罐里投入2 元。存钱罐中总金额为1 + 2 = 3 元
  第3 天,往存钱罐里投入3 元。存钱罐中总金额为1 + 2 + 3 = 6 元
  第4 天,往存钱罐里投入4 元。存钱罐中总金额为1 + 2 + 3 + 4 = 10 元
  那么,每天都这样往存钱罐里投入硬币的话,第100 天时的总金额为多少呢?
  思考一下
  本题要求算出第100 天时存钱罐的总金额。要求出第100 天的金额,只要计算1 + 2 + 3+ … + 100 的值就行了。那么,具体应如何计算呢?
  一般来说,最先想到的肯定是机械地将它们逐个相加。1 加2,再加3,再加4,…再加99,再加100。只要这样加起来就能得出答案了吧。如果说笔算比较花时间的话,也可以使用计算器或编程来计算。
  不过,德国数学家高斯在9 岁时遇到了同样的问题,却马上得出了答案。当时他既没用计算器也没用电脑。那么,他究竟是如何做到的呢?
  小高斯的解答
  小高斯是这么考虑的。
  1 + 2 + 3 + …+ 100 顺次计算的结果和100 + 99 + 98 + …+ 1 逆向计算的结果应该是相等的。那么,就将这两串数字像下面那样纵向地相加。
  如此一来,就变成了101 + 101 + 101 + …+ 101 那样100 个101 相加的结果。这样的计算就非常简单了。只要将101 乘以100 即可,结果为10100。不过10100 是要求的数的2 倍,因此还得除以2,答案为5050。
  答案:5050 元。
  讨论一下小高斯的解答
  小高斯的方法可谓绝妙非凡!
  为了便于大家理解,我们将高斯的方法用图来表示。求1 + 2 + 3 + …+ 100 的结果,相当于计算图4-1 所示的排列成阶梯型的瓷砖块数。
  图4-1 将高斯的方法图形化
  高斯则又做了一个一模一样的阶梯,并将两者合二为一,组成了一个长方形。
  图4-2 将2个阶梯组合成1个长方形
  由2 个阶梯组合而成的长方形,纵向有101 块瓷砖,横向有100 块瓷砖。因此,该长方形由101×100 = 10100 块瓷砖构成。而所求的瓷砖块数就是10100 的一半,即5050。
  我们来说一说高斯的计算效率。使用他的方法不需要花费力气逐个相加。只要将两端的1 和100 相加,结果乘以100 再除以2 就行了。
  现在,假设我们不是从1 加到100,而是从1 加到10000000000(100 亿)。这次我们就不能采用逐一相加的方法了。因为即使计算器1 秒能完成1 次加法计算,加到100 亿也得花300 年以上的时间。
  不过,如果使用高斯的方法,那么从1 加到100 亿也只要1 次加法、1 次乘法、1 次除法运算即可完事。我们来实际计算一下。
  高斯(Karl Friedrich Gauss, 1777 - 1855)后来成为了历史上著名的数学家。
  归纳
  高斯运用了以下等式。
  这里,使用变量n,将"1 到100"归纳为"1 到n"。这样,上面的等式就变为如下形式
  那么,这个等式对于0 以上的任意整数n 都成立吗?即n 为100、200,或者100 万、100 亿时该等式也都成立吗?如果成立的话,又如何来证明呢?
  这种时候就要用到数学归纳法了。数学归纳法是证明"断言对于0 以上的所有整数n都成立"的方法。
  学生:"对于所有整数n",总觉得这种说法别扭。
  老师:别扭?
  学生:会感觉头脑中充满了整数。
  老师:那么,改为"对于任一整数n"怎么样?
  学生:啊!那样感觉稍微舒服些。
  老师:其实说的是一回事呢!
  数学归纳法-- 如何征服无穷数列
  本节,我们就来讨论一下数学归纳法的相关内容。首先,从"0 以上的整数的断言"开始学起,然后使用数学归纳法来证明高斯的断言 。
  0以上的整数的断言
  0 以上的整数n 的断言",就是能够判定0,1,2…等各个整数为"真"或"假"的断言。这样说明或许难以理解,下面就举几个例子。.
  ● 例1
  o 断言A (n ) :n ×2 为偶数。
  A(n),即"n×2 为偶数"的断言。由于n 为0 时,0×2 = 0 为偶数,所以A(0) 为真。
  A(1) 又怎么样呢?因为1×2 = 2 为偶数,所以A(1) 也为真。
  那是否可以说断言A(n),对于0 以上的所有整数n 都为真(对于0 以上的任意整数n都成立)呢?
  对!可以这么说。因为0 以上的任意整数乘以2 的结果都为偶数,所以对于0 以上的所有整数,断言A(n) 都为真。
  ● 例2
  o 断言B (n ) :n ×3 为奇数
  那么,断言B(n) 又将如何呢?该断言对于0 以上的所有整数n 都成立吗?
  例如,假设n 为1,则断言B(1) 就是"1×3 为奇数",这个结果为真。但不能说对于0以上的所有整数n,断言B(n) 都为真。因为假设n 为2,则n×3 的值为2×3 = 6。而6 是偶数,所以断言B(2) 不为真(为假)。
  n = 2 是推翻"断言B(n) 对于0 以上的所有整数n 都成立"的反例。
  ● 其他例子
  那么请思考一下,在下面4 个断言中,对于0 以上的所有整数n 都成立的有哪些。
  o 断言C (n ) :n +1 为 0 以上的整数。
  o 断言D (n ) :n -1 为 0 以上的整数。
  o 断言E (n ) :n ×2 为 0 以上的整数。
  o 断言F (n ) :n ÷2 为 0 以上的整数。
  断言C(n),对于0 以上的所有整数n 都成立。因为若n 为0 以上的整数,则n + 1 肯定是0 以上的整数。
  断言D(n),对于0 以上的所有整数n 不成立。例如,断言D(0) 为假。因为0 -1 = -1,不是0 以上的整数。n = 0 是唯一的反例。
  断言E(n),对于0 以上的所有整数n 都成立。
  断言F(n),对于0 以上的所有整数n 不成立。因为当n 为奇数时,n÷2 的结果不是整数。
  高斯的断言
  在讨论了" 0 以上的整数n 的断言"之后, 我们将话题转回高斯的断言。
  可以使用下述有关n 的断言形式来表现高斯的观点。
  o 断言G(n) :0 到n 的整数之和为 。
  接下来要证明的是,"G(n) 对于0 以上的所有整数n 都成立"。可以通过描画前面的阶梯状的图(图4-1)来证明,但是有人可能会有这样的疑问:0 以上的整数有0, 1, 2, 3,…等无穷个数字,而图中表现的只是其中一种情况。 当G(1000000) 时也成立吗?
  确实,0 以上的整数有无穷个。这就要通过引入"数学归纳法"来证明了。使用数学归纳法能够进行0 以上的所有整数的相关证明。
  什么是数学归纳法
  数学归纳法是证明有关整数的断言对于0 以上的所有整数(0、1、2、3…)是否成立时所用的方法。
  假设现在要用数学归纳法来证明"断言P(n)对于0 以上的所有整数n 都成立"。
  数学归纳法要经过以下两个步骤进行证明。这是本章的核心内容,请大家仔细阅读。
  o 步骤1 :
  证明"P (0) 成立"。
  o 步骤2 :
  证明不论k 为0 以上的哪个整数,"若P (k ) 成立,则P (k +1) 也成立"
  在步骤1 中,要证明当k 为0 时断言P(0) 成立。我们将步骤1 称作基底(base)。
  在步骤2 中,要证明无论k 为0 以上的哪个整数,"若P( k ) 成立,则P (k+1) 也成立"。
  我们将步骤2 称作归纳(induction)。该步骤证明断言若对于0 以上的某个整数成立,则对于下一个整数也成立。
  若步骤1 和步骤2 都能得到证明,就证明了"断言P (n) 对于0 以上的所有整数n 都成立"。
  以上就是数学归纳法的证明方法。
  试着征服无穷数列
  数学归纳法通过步骤1(基底)和步骤2(归纳)两个步骤,证明断言P(n) 对于0 以上的所有整数n 都成立。
  为什么只通过两个步骤的证明,就能证明无穷的n 呢?请作如下思考。
  o 断言P (0) 成立。
  理由:步骤1 中已经证明。
  o 断言P (1) 成立。
  理由:P (0) 已经成立,并且步骤2 中已证明若P (0) 成立,则P (1) 也成立。
  o 断言P (2) 成立。
  理由:P (1) 已经成立,并且步骤2 中已证明若P (1) 成立,则P (2) 也成立。
  o 断言P (3) 成立。
  理由:P (2) 已经成立,并且步骤2 中已证明若P (2) 成立,则P (3) 也成立。
  这样循环往复,可以说断言P(n) 对于任意数字n 都成立。无论n 为多大的数字都没关系。因为即使设n 为10000000000000000,经过机械式地反复执行步骤2,终究可以证明P(10000000000000000)成立。
  这种数学归纳法的思路可以比喻为"推倒多米诺骨牌"。
  假设现在有很多多米诺骨牌排成一列。只要保证以下两个步骤,那么无论多米诺骨牌排得有多长最终都能倒下。
  o 步骤1
  确保让第0 个多米诺骨牌(排头的多米诺骨牌)倒下。
  o 步骤2
  确保只要推倒第k 个多米诺骨牌,那么第k + 1 个多米诺骨牌也会倒下。推倒多米诺骨牌的两个步骤和数学归纳法的两个步骤一一对应。
  数学归纳法并不像"推倒多米诺骨牌"那样关注用时。数学归纳法和编程不同,往往使用的是忽略时间的方法。这就是数学和编程之间最大的差异。
  用数学归纳法证明高斯的断言
  下面我们就以证明高斯的断言G(n) 为例具体看看数学归纳法。首先讨论断言G(n)。
  o 断言G(n) :0 到n 的整数之和与 相等。
  使用数学归纳法就需要通过步骤1(基底)和步骤2(归纳)来证明。
  ● 步骤1 :基底的证明
  证明G(0) 成立。
  G(0) 就是"0 到0 的整数之和与 相等"。
  这可以通过直接计算证明。0 到0 的整数之和是0,
  至此,步骤1 证明完毕。
  ● 步骤2 :归纳的证明
  证明当k 为0 以上的任一整数时,"若G(k) 成立,则G(k + 1) 也成立"
  现假设G(k) 成立。即假设"0 到k 的整数之和与 相等"。这时,以下等式成立。
  假设成立的等式G(k)
  下面,我们来证明G(k + 1) 成立。
  要证明的等式G(k+1)
  G(k + 1) 的左边使用假设的等式G(k) 可以进行如下计算。
  而G(k + 1)的右边可以进行如下计算。
  G(k + 1) 的左边和右边的计算结果相同。
  由此,从G(k) 到G(k + 1) 推导成功,步骤2 得到了证明。
  至此,通过数学归纳法的步骤1 和步骤2 都证明了断言G(n)。也就是说通过数学归纳法证明了断言G(n) 对于0 以上的任意整数n 都成立。
  求出奇数的和--数学归纳法实例
  本节,我们使用数学归纳法来证明另一个断言。
  奇数的和
  请证明以下断言Q(n) 对于1 以上的所有整数n 都成立。
  o 断言Q (n ) :1 + 3 + 5 + 7 + … +(2 × n -1) = n2
  Q(n) 是比较有意思的断言。按从小到大的顺序将n 个奇数相加,得到n2,即平方数n ×n。
  这对吗?在证明之前,先通过较小的数n = 1、2、3、4、5 判断Q(n) 的真假。
  o 断言Q (1) :1 = 12
  o 断言Q (2) :1 + 3 = 22
  o 断言Q (3) :1 + 3 + 5 = 32
  o 断言Q (4) :1 + 3 + 5 + 7 = 42
  o 断言Q (5) :1 + 3 + 5 + 7 + 9 = 52
  通过以上计算发现断言确实是成立的。
  ……
展开
目录
第1章 0的故事——无即是有
本章学习内容
小学一年级的回忆
10进制计数法
什么是10进制计数法
分解2503
2进制计数法
什么是2进制计数法
分解1100
基数转换
计算机中为什么采用2进制计数法
按位计数法
什么是按位计数法
不使用按位计数法的罗马数字
指数法则
10的0次方是什么
10-1是什么
规则的扩展
对20进行思考
2-1是什么
0所起的作用
0的作用:占位
0的作用:统一标准,简化规则
日常生活中的0
人类的极限和构造的发现
重温历史进程
为了超越人类的极限
本章小结

第2章 逻辑——真与假的二元世界
本章学习内容
为何逻辑如此重要
逻辑是消除歧义的工具
致对逻辑持否定意见的读者
乘车费用问题——兼顾完整性和排他性
车费规则
命题及其真假
有没有“遗漏”
有没有“重复”
画一根数轴辅助思考
注意边界值
兼顾完整性和排他性
使用if语句分解问题
逻辑的基本是两个分支
建立复杂命题
逻辑非——不是A
逻辑与——A并且B
逻辑或——A或者B
异或——A或者B(但不都满足)
相等——A和B等
蕴涵——若A则B
囊括所有了吗
德·摩根定律
德·摩根定律是什么
对偶性
卡诺图
二灯游戏
首先借助逻辑表达式进行思考
学习使用卡诺图
三灯游戏
包含未定义的逻辑
带条件的逻辑与(&&)
带条件的逻辑或(||)
三值逻辑中的否定(!)
三值逻辑的德?摩根定律
囊括所有了吗
本章小结

第3章 余数——周期性和分组
本章学习内容
星期数的思考题(1)
思考题(100天以后是星期几)
思考题答案
运用余数思考
余数的力量——将较大的数字除一次就能分组
星期数的思考题(2)
思考题(10100天以后是星期几)
提示:可以直接计算吗
思考题答案
发现规律
直观地把握规律
乘方的思考题
思考题(1234567987654321)
提示:通过试算找出规律
思考题答案
回顾:规律和余数的关系
通过黑白棋通信
思考题
提示
思考题答案
奇偶校验
奇偶校验位将数字分为两个集合
寻找恋人的思考题
思考题(寻找恋人)
提示:先试算较小的数
思考题答案
回顾
铺设草席的思考题
思考题(在房间里铺设草席)
提示:先计算一下草席数
思考题答案
回顾
一笔画的思考题
思考题(哥尼斯堡七桥问题)
提示:试算一下
提示:考虑简化一下
提示:考虑入口和出口
思考题答案
奇偶校验
本章小结

第4章 数学归纳法——如何征服无穷数列
本章学习内容
高斯求和
思考题(存钱罐里的钱)
思考一下
小高斯的解答
讨论一下小高斯的解答
归纳
数学归纳法——如何征服无穷数列
0以上的整数的断言
高斯的断言
什么是数学归纳法
试着征服无穷数列
用数学归纳法证明高斯的断言
求出奇数的和——数学归纳法实例
奇数的和
通过数学归纳法证明
图形化说明
黑白棋思考题——错误的数学归纳法
思考题(黑白棋子的颜色)
提示:不要为图所惑
思考题答案
编程和数学归纳法
通过循环表示数学归纳法
循环不变式
本章小结

第5章 排列组合——解决计数问题的方法
本章学习内容
计数——与整数的对应关系
何谓计数
注意“遗漏”和“重复”
植树问题——不要忘记0
植树问题思考题
加法法则
加法法则
乘法法则
乘法法则
置换
置换
归纳一下
思考题(扑克牌的摆法)
排列
排列
归纳一下
树形图——能够认清本质吗
组合
组合
归纳一下
置换、排列、组合的关系
思考题练习
重复组合
也要善于运用逻辑
本章小结

第6章 递归——自己定义自己
本章学习内容
汉诺塔
思考题(汉诺塔)
提示:先从小汉诺塔着手
思考题答案
求出解析式
解出汉诺塔的程序
找出递归结构
再谈阶乘
阶乘的递归定义
思考题(和的定义)
递归和归纳
斐波那契数列
思考题(不断繁殖的动物)
斐波那契数列
帕斯卡三角形
什么是帕斯卡三角形
递归定义组合数
组合的数学理论解释
递归图形
以递归形式画树
实际作图
谢尔平斯基三角形
本章小结

第7章 指数爆炸——如何解决复杂问题
本章学习内容
什么是指数爆炸
思考题(折纸问题)
指数爆炸
倍数游戏——指数爆炸引发的难题
程序的设置选项
不能认为是“有限的”就不假思索
二分法查找——利用指数爆炸进行查找
寻找犯人的思考题
提示:先思考人数较少的情况
思考题答案
找出递归结构以及递推公式
二分法查找和指数爆炸
对数——掌握指数爆炸的工具
什么是对数
对数和乘方的关系
以2为底的对数
以2为底的对数练习
对数图表
指数法则和对数
对数和计算尺
密码——利用指数爆炸加密
暴力破解法
字长和安全性的关系
如何处理指数爆炸
理解问题空间的大小
四种处理方法
本章小结

第8章 不可解问题——不可解的数、无法编写的程序
本章学习内容
反证法
什么是反证法
质数思考题
反证法的注意事项
可数
什么是可数
可数集合的例子
有没有不可数的集合
对角论证法
所有整数数列的集合是不可数的
所有实数的集合是不可数的
所有函数的集合也是不可数的
不可解问题
什么是不可解问题
存在不可解问题
思考题
停机问题
停机
处理程序的程序
什么是停机问题
停机问题的证明
写给尚未理解的读者
不可解问题有很多
本章小结

第9章 什么是程序员的数学——总结篇
本章学习内容
何为解决问题
认清模式,进行抽象化
由不擅长催生出的智慧
幻想法则
程序员的数学
……
展开
加入书架成功!
收藏图书成功!
我知道了(3)
发表书评
读者登录

请选择您读者所在的图书馆

选择图书馆
浙江图书馆
点击获取验证码
登录
没有读者证?在线办证