程序员数学从零开始

作者简介

孙博，苏州工业园区高技能领军人才，擅长人工智能、机器学习、算法和软件结构设计等，曾在CSDN等多个知名博客网站发表多篇技术文章，深受读者的喜爱。

内容简介

第1章重新认识整数（整数分解） 整数的概念来源于计数，它带有很多朴素、自然的性质。本章从整数分解的角度重新看待整数，详解了整数的素因子分解及其应用，并通过欧几里得算式介绍了辗转相除法、更相减损术和Karastuba算法的原理。 整数的概念来源于计数，它带有很多朴素、自然的性质。结绳记事（图11）大概是整数最早的应用，它发生在语言产生以后、文字出现之前的漫长岁月里。《周易·系辞》云：“上古结绳而治”；《春秋左传集解》云：“古者无文字，其有约誓之事，事大大其绳，事小小其绳，结之多少，随扬众寡，各执以相考，亦足以相治也。” 再看汉字中的“数”，从娄从攴（图12）。攴是以手持杖，娄是打了很多绳结的木棍，合起来就是拿着手杖去数绳子上有多少个绳结。数者，结绳而记之也。 图11结绳记事图12古汉字中的“数” 可以毫不夸张地说，整数奠定了数学的基石。19世纪的数学家克罗内克（Kronecker）曾经说过：“上帝创造了整数，其余都是人做的工作。”整数的定义如此简单自然，以至于总是让人忘记它背后的复杂。本章将从分解的视角重新认识整数。 1.1学生的代码和老师的代码 编程总是充满趣味，在学习了判断和循环后就可以编写一些有趣的代码。记得我初学编程时，老师曾出过一个题目：找出两个数的最大公约数。当时我在黑板上写下了自己的实现方式。 代码11学生的代码01def gcd_stu(a, b):02if a < b:03a, b = b, a04result = \\[i for i in range(1, b + 1) if b %i == 0 and a %i == 0\\]05return result.pop()运行结果是正确的。回到座位上，我为此高兴了2分钟。 后来老师写出了另一个实现。 代码12老师的代码01def gcd_teacher(a, b):02if a < b:03a, b = b, a04return a if b == 0 else gcd_teacher(b, a %b)我的第一反应是：“嗯？” 遗憾的是，我当时并没有深究这段代码，只是简单地记住了这种方法，反正都是交给计算机计算，何必在乎快慢呢？ 后来学了数据结构，知道了用大O评估算法效率，我这才开始重新审视那段寻找最大公约数的代码——它实际上使用了传说中的“辗转相除”，要真正弄清楚其来龙去脉，还要从整数说起…… 1.2整除和余数 我们都曾经用笨拙的声音从1数到10，这大概是人生中第一次接触数学，稍大一点后懂得了零的概念，再后来知道了还有负数……这些美好的记忆都有整数相伴左右。随着年龄的增长和知识的扩充，我们知道了更多关于整数的知识，其中就包括整除和余数。 1.2.1欧几里得算式 数学中是以数轴分段的方式定义整除的，如果n是一个正整数，那么可以用n的倍数将数轴分成很多段，如图13所示。 图13用n的倍数将数轴分成很多段 如果将另一个整数m放在数轴上，那么m将正好位于qn和（q+1）n之间，其中q也是一个整数，如图14所示。 图14m位于qn和（q+1）n之间 如果m正好是n的整数倍，那么m=qn；否则可以写成m=qn+r的形式，其中qn是位于m左侧最近的n的整数倍，r是qn到m的整数距离。如果把两种情况合并，那么对于任意整数m和n，且n≠0，总是可以写成下面的形式： m=qn+r,0≤r