= 图灵程序
设计丛书
【司结城浩著
管杰译
心~
:I,
人民邮电出版杜
北京
图书在版编目 (CIP) 数据
程序员的数学/(日)结城浩著;管杰译.一北京:
人民邮电出版社, 2012.11 (2012.12 重印)
(图灵程序设计丛书)
ISBN 978-7-115-29368-8
I. CD程… IL CD结…@管…皿@电子计算机一
数学基础 N. (D TP301.6
中国版本图书馆 CIP 数据核字 (2012) 第 220660 号
内容提要
本书面向程序员介绍了编程中常用的数学知识,借以培养初级程序员的数学思维。读者无
需精通编程,也无需精通数学,只需具备四则运算和乘方等基础知识,就可以阅读本书。
书中讲解了二进制计数法、逻辑、余数、排列组合、递归、指数爆炸、不可解问题等许多
与编程密切相关的数学方法,分析了哥尼斯堡七桥问题、高斯求和方法、汉诺塔、斐波那契数
列等经典问题和算法。引导读者深入理解编程中的数学方法和思路。
本书适合程序设计人员以及编程和数学爱好者阅读。
图灵程序设计丛书
程序员的数学
• 著译
责任编辑
执行编辑
[日]结城浩
管杰
傅志红
乐馨张靖
♦ 人民邮电出版社出版发行 北京市崇文区夕照寺街 14 号
邮编 100061 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
三河市海波印务有限公司印刷
♦ 开本, 800X 1000 1/16
印张: 15.5
字数 I 264 千字
印数 I 4001-6()()0 册
2012 年 11 月第 1 版
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.
本书中文简体字版由 SOFTBANK Creative 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
小学一年级的回忆…………………………………………………………………………… ·2
10 进制计数法·….........………………………......... …….................. ………...... ….... 3
什么是 10 进制计数法……………………………………………………………….. 3
分解 2503 ....... ………..... …...... ………...... …….. ………………………….... ……··3
2 进制计数法.........…...... ….. ………............ ……….. ….... ….. …................ ……….. 4
什么是 2 进制计数法…………………………………………………………………·4
分解 1100 ......... ……………………· …………….... …... …... …........ …........ ……··5
基数转换…………................: …….... ……..... ….... …..... ………•.••·········· …...... 6
计算机中为什么采用 2 进制计数法……………………………·……………… 8
按位计数法……………..……………………………………………………………………… 10
什么是按位计数法…………………………………………………………………… 10
不使用按位计数法的罗马数字…………………………………………………·11
指数法则........…........ ………………· …………………· ……... …………………...... …···12
10 的 0 次方是什么…….…………………………………………………………····12
1 矿是什么...........….... …………………..... …....... …….................... ………··13
规则的扩展……………………………………………………………………………… 14
对少进行思考…………………………………………………………………………·14
2一1 是什么.:... ………... …...... ……………..... …..... ….......... …............... ……···15
0 所起的作用…………………………………………………………………………………··16
0 的作用:占位…………………………………………….....; ………:…………….. 16
viii I 程序员的数学
0 的作用:统一标准,简化规则……………………………………………….. 16
日常生活中的 0 ………………………………………………………………………·17
人类的极限和构造的发现……………………………………………………………….. 18
重温历史进程………………………………………………·……·…………………"·18
为了超越人类的极限……………………………………………………………….. 19
本章小结..................…..... …·…....... …….... ……….......................... …..... …...... 20
第 2 章
逻辑
—真与假的二元世界
本章学习内容……………..……….. ………………………………………………………, .. 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