@bintou
2017-06-29T10:21:02.000000Z
字数 16756
阅读 5260
导论 世间少有的扯蛋授课 笔记
如果你是第一次看到这个笔记，请直接跳到本页面底部去，从后往前看。
从这计算机科学的本质开讲。学“计算机科学”到底是学什么？其实，computer science不是学计算机，不是学计算机的使用也不是学计算机的制造。学的是“计算”－－computation。我理解，大家进入这个专业多数是因误解而来，从今天开始，也许需要换一下思维了。这也就是我为什么一直推荐How to Think like a Computer Scientist（HTCS）而不是其他比如C++ Primer之类的书为入门书的原因。关键不在于是否学会编程，而是要如何改变思维。
那到底什么是计算？这个问题很复杂，然后具体落实到计算机的实现上却又非常简单。这是两个问题。第一是，什么是计算！这个暂时还回答不了。第二是，怎么计算。这个可以有一个简单的初始到答案：二进制。
“世界上有10种人，一种懂二进制，一种不懂！”你们是其中的第一种。改变思维的第一步，就是认识二进制。
首先我们给出二进制数字的描述。
二进制：只有0和1两位数字，每一位我们称为一个bit（比特）。
计算规则：0+0 = 0，0+1 = 1，1+1 = 10，10+1 = 11
现在可以归纳一下规律了。
0，1，10，11，...，1111，...， 这样的数字有没有遍历完所有的我们之前认识的十进制正整数？答案是，yes。
十进制数无非就是偶数和奇数两种。请问，偶数在二进制中长什么样子？答：最后一个bit为0 。
于是我们有以下规则：
0结尾的二进制数是偶数；1结尾的二进制数是奇数。
例子：
2对应10，4，对应100，8对应1000，16对应10000
大家有没有看到10后面加个0等于是乘二？好像我们可以得出一个规律: 在一个二进制数后面补一个零等于乘二？（注：在此处回答问题的同学基本上答案都是No！）因为这里如果考虑奇数，那么，很可能不对！但是，乘二不是在后面补零？末尾为零不就是偶数？这......
例子：
十进制7 ＝＝ 二进制 111
7*2 == 14 == 二进制 1110
似乎是这么个理？再演算一下其他数字......得到规则如下：
二进制乘2运算等于在数字末尾补一个0.
思考一下，乘法是补0，除法呢？我们只考虑整除，即只取整数商。
例子：
十进制7的二进制为111，十进制7/2 == 十进制3 == 二进制 11
十进制11的二进制为1011，十进制11/2 == 十进制5 == 二进制101
规律：
二进制除2运算等于在砍掉数字末尾一个数位。
如何把任何的二进制数转换为十进制？第一次授课结束。
归纳一下之前的内容。首先，计算机科学是关于“计算”的科学，是关于“思维”的科学。然后，介绍了二进制，当然是非正式地介绍，为的是归纳出两个规则：在后补零等于乘2（扩展思考，除2怎么做？）；尾数为0的数是偶数（尾数为1的是奇数）。然后，我们需要思考的是如何在二进制数与十进制数之间进行转换。特别是，我们不要满足于怎么做，还要思考为什么。更重要的是，我们想得到一个“过程”，一个计算机可以读懂的过程。
当我们思考一个过程的时候，我们需要知道的是，输入什么，得到什么。比如，我们命名二进制转换为十进制的过程为B2D，这是一个名字。
例子：
function B2D(a)
输入：一个二进制数a
输出：a所代表的十进制数
在完成这个程序之前，我们拿些实例出来看看，比如：
例子：
输入0，立即输出0；输入1立即输出1！这太简单，但是请注意，这很重要！
考虑多比特输入。比如输入：1110；输出：1110代表的十进制。根据之前的规则，补零等于乘2，所以，这个数必然是111的十进制乘2。所以，如果我们的计算结果就是2*B2D(111)。但是，如果是奇数呢？比如，输入1111 。Ok，没关系，我们照样可以得到结果：2*B2D(111)+1 ，多加个1就好了。
所以，我们可以完成我们的程序为：
注意：＃代表注释！
function B2D(a)
＃输入：一个二进制数a
＃输出：a所代表的十进制数
if a < = 1: ＃递归的终止条件
return a; #即，当a小于等于1，原样输出。
else: ＃否则
return 2*B2D(a/2) + lsb(a)
请注意一点，我们现在只有二进制数操作的两个规则：乘2等于补零；0为偶数，1为奇数。上面这个程序违反规则了没？有啊，怎么能用除法“／”。其实，这里的除法就是把a的最后一个比特删除。而lsb(a)指的是a的最后一个比特。
这个程序中最古怪之处是：2*B2D(a/2) + lsb(a)。因为，这里B2D这个程序自己调用了自己！！！我们把这种自己调用自己的过程称为“递归”。
所有计算无非递归而已！所有的思维都是递归的！
现在反过来，如果要从十进制得到二进制应该如何？我们重新来，思维运动起来！
现在我们要写一个D2B的程序，输入：a，十进制数；输出：a的二进制数。首先，我们需要得到程序的终止条件。如果 a< = 1，怎么样？输出a！然后，计算无非递归，递归起来！比如，7这个数，我们能知道它最后一个比特是什么吗？奇数，当然是1 。如果是16呢？偶数，当然是0 。就是说，对任意输入，我们至少知道了部分答案，a的最后一个比特。剩下的比特who care？交给递归啊！我们得到D2B(a')＋lsb(a)，其中a'是a删除最后一比特之后的数.呃，忘记了，a是十进制数呢？没事，除法嘛，除2。
程序：
function D2B(a)
# Input, a decimal number a;
# Output, the binary number of a;
if a <= 1: ＃终止条件！
return a;
else:
return D2B(a/2)||lsb(a)
D2B(a) = D2B(a/2) || b ，这样的过程为什么会结束？也许很多同学立即会担心，递归怎么会结束呢？
为什么会终止？因为每一个递归程序都有一个终止条件。而且，每次自己调用自己的时候，参数都在减小（这很重要），这就确保了终止条件一定会到达。
递归效率低？我的回答是：思维，不在乎效率；其次，递归并不总是低效率。相信提这个问题的同学学过一些，但是，对递归对理解不能那么片面。以后继续深入。
接下来，做一个习题：
function fac(n)
输入：整数n
输出：n的阶乘
要求：必须使用递归
最后一个内容，这是世界上最有意思的问题之一。话说有两只兔子...斐波那契数列：1 1 2 3 5 8 13 21...... 请用C语言用递归的方法写出第n项斐波那契数。
function fib(n)
输入：整数n
输出：第n项斐波那契数
要求：必须使用递归
注：第二次授课结束。
计算机的核心是CPU，我们总是希望这些个核心设备做尽可能少的“操作”，但是借助它又似乎无所不能。这似乎矛盾，其实又不矛盾。昨天讲到二进制的加法和乘2。然后讲到用递归的方法去思考。
今天，先延续昨天的思路，出一道题，如果没人做，以后看来也不需要上课了。今天做“乘法”：
function multiply(a,b)
输入: a和b，两个任意长的二进制数；
输出：a*b 。
要求：请用递归的方法，并且只能用加法和乘2操作来完成，不要写程序，用我昨天的描述方法即可。
有会的同学，写了可以发我Q邮箱。我11点左右来看看。然后再看看有没有然后。。。建立、改变思维方式应该放第一位，请不要小看这些似乎没用的东西。
例子：
11*1 ＝11；11＊0 ＝＝0；
11 * 10 ＝＝110，实际就是11乘2，即11后面补个0；如果是11 * 11？当然应该是11*10 ＋11*1，即11*(10 + 01)。
推广到任意比特的乘法：x ＊ y ＝ 2*multipy(x,y/2) ＋ x 。这里看明白了吗？递归！
代码：
function multiply(a,b)
if b ＝＝ 0：
return 0;
if b == 1:
return a;
if iseven(b): # the last bit of b is 0;
return 2*multiply(a, b/2);
else: # b is odd
return 2*multiply(a, b/2) + a;
这个乘法算法展示，计算机只要乘2和加法就可以做任何乘法，对吗？但是，我们怎么不讲除法和减法呢？
练习：
既然整数a乘2是在a的后面补0，那么，整除的a除2运算应该是什么？
略，以后增加！
接下来讲一个世界上最古老的算法（并没有之一）！给定两个整数a和b，求a和b的最大公因子，记为GCD(a, b)。
算法：
function GCD(a, b)
#input: a, b, two integers with a >= b >= 0
#output: the greatest common divisor of a and b
if b == 0:
return a;
else:
return GCD(b, a mod b)
例子：
求8、4的gcd，8 mod 4 ＝＝ 0；所以，递归gcd(4,0),然后返回4。
求7和3的gcd，第一步递归gcd(3,1);第二步递归gcd(1,0).结果为1。
定义：
如果整数a和b的最大公因子为1，则称a与b互素。如果对于整数a，所有小于a且大于0的数都与a互素，则称a为素数。
为什么算法是正确的？要证明，我们需要一个简单的中间结论gcd(a,b) == gcd(a-b,b) 。
证明：
1、因为a和b的公因子肯定整除a－b，所以gcd(a,b) <= gcd(a-b,b);
2、同时能整除a－b和b的家伙一定可以整除a和b！所以，gcd(a－b,b) <= gcd(a,b)。
这里利用了一种证明方法，要证明 a == b，我们只需要证明：a <= b 且 b < = a。一种非常常规的证明方式。推广，如果a和b为集合，证明这两个集合相等，只需要证明a是b的子集且b是a的子集。
为什么gcd(a,b) == gcd(a-b,b)就得到结论？因为：
gcd(a,b) == gcd(a-b,b) ＝＝ gcd(((a-b)-b),b) == gcd((((a-b)-b)-b),b)== ... == gcd(a mod b, b)
不断对a进行减b，当然会得到a mod b。mod运算无非是a除b取余数。
GCD算法又称为欧几里德算法，是最古老的算法，然而也是目前使用最广泛的算法之一。GCD算法的一个简单扩展是目前互联网中使用最广泛的安全保密算法－－RSA算法－－的基础。
要理解递归也许我们需要更多的练习，或者阅读，不知道我以前的这份递归讲义是否可以帮助大家？
最后要说，在计算机的实现中，加法和乘法是最本质的运算。而计算机的加法和乘法都是mod加和mod乘。这是下一次课程的内容。（第三次授课结束。）
当我们学习某种理论体系的时候，我们往往从它的弱点开始。计算机的弱点是什么？
也许我们首先要知道，计算机所有的计算都是有限计算，这非常重要。什么是有限计算？我们现在只知道二进制是0/1比特串，可以进行加法和乘法（上次我们已经从乘二中得到了任意的乘法）。那么有限就体现在，计算机只能做有限比特的加法和乘法？这似乎有悖于我们对计算机对认识，计算机不是连围棋高手都打败了吗？是的，无论它表现得似乎无所不能，本质上，它只是做有限比特的加法与乘法。
好吧，那么有限到什么程度？也许有些计算机只能做8比特的运算，有些能做16比特或者32比特，而你们现在购买的64位机就是做64比特的运算而已。是不是有点为自己那几大千RMB感到遗憾？请大家要明白，你买32位机或者64位机，其实是说你的cpu在执行一次运算时候能做多少比特的运算。
几个概念：
8比特为一个byte（字节）。
C语言中的Byte类型就是8个比特的数据类型。
C语言中的char类型是8比特的字符类型。都是8比特，有什么区别吗？
C语言中的int类型是表示整数类型，32比特，即4个字节。
直观上，给定任意一个变量，我们可以把它看成能装n个比特的“盒子”，比如一个byte变量就是可以装8个比特的盒子。
那么，比如把37（16进制）装进盒子里，就得到：
0 0 1 1 0 1 1 1
请注意开头的3个0，这里必须写，因为我们需要把8个比特写出来。大家计算这个16进制数等于10进制的几？对它乘2等于在末尾补零，对这种形象化的说法，我们可以有更直观的认识，即把比特值向左移动一个比特位，得到：
0 1 1 0 1 1 1 0
除2等于向右移动一个比特位，在左边补零，得到：
0 0 0 1 1 0 1 1
这些规则都是在第一章中已经归纳出来的内容，这里只是在有限计算的框架下重信陈述。同样，我们还可以重新理解这里的加法与乘法。
我们怎么再认识计算机的有限计算呢？比如，对于加法，我们可以这样玩一下：
byte a = 255, b = 2;
a = a + b;
printf("a ＝＝ %d", a);
比如，对于乘法，我们这样编程尝试一下嘛：
int n = 16; #你们可以尝试不同的数值；
byte a = 1；#或者尝试一下int类型；我不会告诉你们什么unsigned的！
for(int i = 1; i < = n; i++){
a = a*2；
printf("我这里偷个懒，你们直接输出a的值嘛，%d", a)；
｝
当n为什么的时候a的值会出现异常？这种异常代表什么？如果a的初始值为任意的，比如3，或者5，又会如何？
通过尝试，也许我们会发现，其实，这里的所谓加法或者乘法，只是一种mod运算，mod什么？mod的是2的某个次方，比如int类型，mod 2^32（2的32次方）。byte类型mod什么？请一定要设置特定数值进行尝试一下。
这里也许需要解释一下，经典书籍当中所谓的“溢出”。这里没有什么溢出，只是mod运算。
好了，现在我们需要了解一下mod运算的好处了。运算规则如下，希望你们中学的时候学过(感谢15级的会智同学发现我书写的错误。我的错误一如既往地存在，请帮我改正。谢谢！)：
(a + b) mod n ＝＝( (a mod n) + (b mod n)) mod n
(a * b) mod n ＝＝( (a mod n) * (b mod n)) mod n
这个时候，你们之前写的代码就可以这样玩一下了。如果写了factorial，不妨看看，当n变得很大时候会怎么样？比如n＝100，1000，10000......可以看到，其实mod 2^n并不好玩！（非常可惜对于我提示的这些计算，很少有同学会自觉取编程玩一下！）怎么样才好玩？我们会回来的。不过，现在我们还是先停顿一下。
之前有不少同学已经迫不及待地问到八进制，16进制。其实，这并不是很特殊到东西。如果我们把比特三位为一组去认识，就得到八进制，四位为一组去认识就得到16进制。比如：
000 ，001，...，110， 111，这里有多少个数？2的3次方，8个。111 + 1 == ?，1000 ？对不起，我们只有3个比特，所以是0！即，逢八进一。
同样，0000到1111，有16个数，逢16进一，是16进制。呃，这里要注意，1010，1011，到1111，这几个数还没有名字，所以，起名为A，B，...，F。没有什么特别！对吧？
16进制的命名：
1000 为 8； 1001 为 9 #老名字，以下是新名字
1010 为 A； 1011 为 B
1100 为 C； 1101 为 D
1110 为 E； 1111 为 F
为什么我们需要8进制，16进制，而不是3进制，5进制？哪种进制的效率最高？
给定变量的长度我们就能立即知道这个变量所能表示数据的范围，反之，给定一个数字，我们能知道这个数值需要用多长的比特变量来表达。
例子：
8比特变量能表达的范围是：00 ~ FF，256个数值；
16比特能表达的范围是：0000 ~ FFFF，65536个数值；
例子：
表达234这个十进制值需要 8 个比特；
表达4294967295这个十进制值需要32个比特；
这里的一个观点是，长度n能表达的最大范围是2^n；而某个数x需要n比特进行表达，则是n ＝＝ log x （以2为底的对数）。这里的指数与对数的对应关系值得注意！
第四次结束！
以上内容我故意忽略了负数，只讲正数。很多同学迫不及待提出什么是补码。其实关于补码，我看了很多书，有些讲得很复杂。其实，并没有什么可说的。
比如，我们要表示8比特的数，无非就是00到FF这256个数。01+01=02，0F + 01 = 10 。这些我们都已经懂了。现在要在8比特中同时表示负数，仅仅多这么个要求而已。那么也就一半是正数，一半是负数，一样一半，127 ＋ 127 ＝ 254 。看上去有点怪，我们不是要表达256个数吗？这么问题，稍微放下。马马虎虎先生先定下来说，大致上如此：00，不正也不负。正数是01到7F，127个。于是，我们已经有了128个数。接着，我们要问，－1是什么？
我们懂加法，那么我们一定会得到：
01 + FF == 00
我们是不是可以很高兴地说，哦，FF是-1！因为，1 + (-1) == 0。别急，我们要得到-2，-3...
02 + FE == 00
03 + FD == 00
...
7E + 82 == 00
7F + 81 == 00
所以，我们得到了-1，-2，-3，...，-127，一共127个数字，对吧？用二进制表达分别是：
1111,1110 代表 -2
1111,1101 代表 -3
...
1000,0010 代表 -126
1000,0001 代表 -127
这里担心7F + F1会溢出地同学一定要放心下来，8比特运算无论如何不会得到9比特的数值，多出来的只能扔掉。
现在我们基本已经胜利了。只是如果敏感的同学一定会发现，我们现在得到了128+127个数，但是8比特数可以表达256个数值。我们忽略了什么？80我们遗漏了。即二进制的10000000没有得到任用，它应该是什么？
首先，我们注意到，所有到负数都有一个特点，排在最左边到比特都是1。所以，这个10000000看上去应该是个负数。应该是什么呢？还是用加法试一下：
10000000(16进制的80) + 01111111(16进制的7F，十进制的127) + 01（十进制的1） == 0
某个负数加正数128等于0，所以，这个负数是-128。也就是说，80代表负的128。
至此我们已经完全胜利，这种表示负数的方式就是所谓的二进制补码。可以推广应用到任意长到比特负数表达。我们又把负数称为带符号数。在宣称胜利之后，我们还需要把之前的规则归纳一下，这就变成了所有教科书中给出的规则了。（讨厌教科书，讨厌教条主义，讨厌背诵规则的同学可以忽略以下规则。前提是，最好你有我以上把规则理解为操作的能力。）
补码规则：
n比特数的第n-1位为符号位，0代表正数，1代表负数。正数的表达与二进制数表达相同。负数的表达只是对正数进行取反操作，然后加1。
比如，还是8比特数为例：
08代表正8，二进制表达为00001000，那么-8就是对之前对二进制进行取反再加1。即，11110111 + 1 == 11111000，16进制表达即为F8。
7F，二进制数为01111111，-7F为：10000000 + 1 == 10000001，16进制为81。
补码的好处？使用补码，计算机中定义的加法，无论是否使用符号位，都一样操作。也就是说，在补码这里讲负数，但是加法还是原来都加法。同样，C语言中虽然允许你们定义带符号数和非带符号数，其实用到的操作是一样的。所以，你同样的一个变量，把它看成带符号数或者不带符号都可以。这个，你们完全可以通过编程来加深体会。
其实补码没有任何新东西，考虑mod 2^n的加法，比如下面等式：
给定n比特长的整数x，求x + -x == 0，-x就是x的负数。
x + -x == 0其实就是 x + -x == 0 mod 2^n
所以，-x == (2^n - x) mod 2^n
例子：
8比特数-7的二进制补码：
2^8 - 7 == 249
00000111取反加1 == 11111001
不熟悉就拿笔比划一下。我认为这样教比之前那样要好！
“有意思”这件事情对不同的人有不同的含义，所以，我们只能走走看。比如，如果你们可以执行这样的代码：
给定任意一个整数n，比如让n＝11.
for i in range(1, n): #i循环从1到n-1
for j in range(1, n): #j循环从1到n-1
print ((i * j) % n), #输出 i*j mod n
print #只是控制换行
当然，你们可以用C语言来写写看。不断尝试，让n = 7，或者等于13，17 。当然，也可以尝试n等于10，20等等。
这个程序不断输出 i*j mod n ！不看懂这个程序你往下能看到啥啊？？
关键是，看懂后，你们能归纳出什么结论吗？我想，发现规律比学到知识要重要得多。
比如，在n等于11的时候，我得到这样的输出。
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 1 3 5 7 9
3 6 9 1 4 7 10 2 5 8
4 8 1 5 9 2 6 10 3 7
5 10 4 9 3 8 2 7 1 6
6 1 7 2 8 3 9 4 10 5
7 3 10 6 2 9 5 1 8 4
8 5 2 10 7 4 1 9 6 3
9 7 5 3 1 10 8 6 4 2
10 9 8 7 6 5 4 3 2 1
似乎很容易发现，每一行只是1到n-1的重排。这是偶然还是规律？如果n取13，我们还能得到同样规律的输出吗？我们会不会得到：
1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 1 3 5 7 9 11
3 6 9 12 2 5 8 11 1 4 7 10
4 8 12 3 7 11 2 6 10 1 5 9
5 10 2 7 12 4 9 1 6 11 3 8
6 12 5 11 4 10 3 9 2 8 1 7
7 1 8 2 9 3 10 4 11 5 12 6
8 3 11 6 1 9 4 12 7 2 10 5
9 5 1 10 6 2 11 7 3 12 8 4
10 7 4 1 11 8 5 2 12 9 6 3
11 9 7 5 3 1 12 10 8 6 4 2
12 11 10 9 8 7 6 5 4 3 2 1
如果n=12呢？得到了：
1 2 3 4 5 6 7 8 9 10 11
2 4 6 8 10 0 2 4 6 8 10
3 6 9 0 3 6 9 0 3 6 9
4 8 0 4 8 0 4 8 0 4 8
5 10 3 8 1 6 11 4 9 2 7
6 0 6 0 6 0 6 0 6 0 6
7 2 9 4 11 6 1 8 3 10 5
8 4 0 8 4 0 8 4 0 8 4
9 6 3 0 9 6 3 0 9 6 3
10 8 6 4 2 0 10 8 6 4 2
11 10 9 8 7 6 5 4 3 2 1
似乎是令人失望的结果！
如果你并没有总结出规律，我想你暂时还是不要看下去，多思考思考，多尝试。如果你找到了规律，那请看下面。
令n为素数：
任意取一个大于等于1且小于等于n-1的整数i，重复用所有大于等于1且小于等于n-1的整数j(n-1个数)对i进行mod n的乘法，即求 i*j mod n，所得的整数刚好是所有大于等于1且小于等于n-1的整数(n-1个数)的某个排列。
即，任取一个i之后，我们算这n-1个值：
i*1 mod n, i*2 mod n, ..., i*(n-1) mod n (1)
得到的数刚好是（经过排列之后）：
1，2，3，...，n-1 (2)
我们把第(1)行的数乘起来并mod n：
i^(n-1) * (n-1)! mod n (3)
把第二行的数乘起来并mod n：
(n-1)! mod n (4)
我们知道(3) == (4)：
i^(n-1) * (n-1)! ≡ (n-1)! mod n (5)
由(5)我们可以得到（当然，我们必须问为什么？）：
i^(n-1) ≡ 1 mod n (6)
这个(6)就是颇为有名的费尔马小定理！
这是我们需要的一个条件。有同学问这道题的答案，算了，作为习题给大家做一下。
if gcd(c,n)==1, and a*c ≡ b*c mod n, then a ≡ b mod n.
证明：略！想在“图灵班”混的同学请到“课堂派”交作业。
费尔马小定理：
对于素数n，取任意大于1小于n-1的整数（此条件并不必要，为什么？），我们有，i^(n-1) ≡ 1 mod n 。
对于以上的推导你懂(不懂)吗？懂不值得骄傲。不懂，不如问一下自己，在哪个环节让自己失去了逻辑关联？任何人都应该懂。
费尔马小定理有什么用？这个，敬请期待......
暂时回到这个小定理的条件开始，n为素数，这是一个较强的要求，如果n为任意整数呢？我们已经知道n=12的时候，得到的结果没有n为素数时那么有规律。但是，n为合数是不是就没有规律呢？这个.....嗯？怎么办？
第五次授课结束！
正如之前看到的，当n＝12，我们的程序输出：
1 2 3 4 5 6 7 8 9 10 11
2 4 6 8 10 0 2 4 6 8 10
3 6 9 0 3 6 9 0 3 6 9
4 8 0 4 8 0 4 8 0 4 8
5 10 3 8 1 6 11 4 9 2 7
6 0 6 0 6 0 6 0 6 0 6
7 2 9 4 11 6 1 8 3 10 5
8 4 0 8 4 0 8 4 0 8 4
9 6 3 0 9 6 3 0 9 6 3
10 8 6 4 2 0 10 8 6 4 2
11 10 9 8 7 6 5 4 3 2 1
是不是没有规律？呃，慢着，我看看......第1行怎么那么熟悉？慢着，似乎第5行的结果也很漂亮，因为结果就是1到11到一次重排。哦，原来第7行、第11行，结果都是1到11到一次重排。1、5、7、11都是什么数？不难看出，是与12互素的整数。似乎，规律出来了。我们是不是可以使用上一次课到方法得到：
如果i与n互素，那么i*1 mod n，i*2 mod n，i*3 mod n，...，i*(n-1) mod n是1到n－1这些数的重排。所以：
i^(n-1)*(n-1)! ≡ (n-1)! mod n
所以，i^(n-1) ≡ 1 mod n ？啊，一个新的“费尔马小定理”？！
慢着，有点不对......因为(n-1)!并不与n互素！！！所以，我们并不可以做两边的“消去”术。似乎有点失望。那为什么费尔马小定理可以那样做？因为n是素数，1到n-1之间到所有数都与n互素。
既然如此，那么，如果n为合数，1到n-1之间的那些数与n互素？它们的相乘是不是还是与n互素？
答案是，1到n-1之间的那些与n互素的数（不就是gcd(i,n)==1 ?）的相乘确实与n互素！
现在，如果我们只考虑与n互素的数会怎么样？计算机程序就是帮助我们找规律的利器。为何不尝试用C语言写个程序看看？（虽然我给出的是Python代码。）
for i in range(1, n): #1到n-1的循环
if gcd(i, n)==1: #如果i与n互素
for j in range(1, n): #1到n-1的循环
if gcd(j, n) == 1: #如果j与n互素
print ((i * j) % n), #输出(i * j) mod n
print #内循环结束，输出换行
令n=12，程序输出是：
1 5 7 11
5 1 11 7
7 11 1 5
11 7 5 1
这是什么意思？规律是什么？看多一些数据。令n＝21，输出为：
1 2 4 5 8 10 11 13 16 17 19 20
2 4 8 10 16 20 1 5 11 13 17 19
4 8 16 20 11 19 2 10 1 5 13 17
5 10 20 4 19 8 13 2 17 1 11 16
8 16 11 19 1 17 4 20 2 10 5 13
10 20 19 8 17 16 5 4 13 2 1 11
11 1 2 13 4 5 16 17 8 19 20 10
13 5 10 2 20 4 17 1 19 11 16 8
16 11 1 17 2 13 8 19 4 20 10 5
17 13 5 1 10 2 19 11 20 16 8 4
19 17 13 11 5 1 20 16 10 8 4 2
20 19 17 16 13 11 10 8 5 4 2 1
请注意每一行开始的那个数字与n的关系！可以考虑30分钟再往下看。
规律：
一个与n互素的整数i，它分别与所有大于等于1、小于n且与n互素的整数相乘（mod n），所得的整数是所有大于等于1、小于n且与n互素的整数的排列。
记大于等于1、小于n且与n互素的整数的个数为phi(n)。记大于等于1、小于n且与n互素的整数的相乘为Pi(n)。利用在求费尔马小定理时的技巧:
i^phi(n) * Pi(n) ≡ Pi(n) mod n
即：i^phi(n) ≡ 1 mod n
这个公式就是大名鼎鼎的欧拉定理！当n为素数，那么phi(n) == n-1。所以，费尔马小定理只是欧拉定理的一种特殊情形。
欧拉定理：
若n，a为正整数，且 gcd(a,n)==1}，则 a^phi(n) ≡ 1 mod n.
注：
phi(n) = phi(n1)*phi(n2), if n == n1 * n2。
如何证明？略！
注意，无论是费尔马小定理还是欧拉定理，这里都没有严格证明。请有兴趣的同学自己完成。
给出i，j和n，求i的j次方，记住我们任何运算都必须mod n。i的j次方mod n，记为 i^j mod n，或者 i**j mod n。求i^j mod n应该怎么做？
似乎有点难？这个是图灵班先修班作业！
在思考这个问题的时候，还是要找规律。比如，从最简单的思路开始，求i^j mod n，无非就是i*i mod n做j次。一个循环就做完了。然后，你也许会想到（必须要想到），比如，i的8次方并不需要做8次乘法，因为只要知道了i^4，对i^4做一次平方就得到了i^8。至此，你至少知道求i的j次方并不需要做j次乘法，因为有中间结果可以利用。
再考虑几个例子，如果求i^10 mod n 如何？只需要对i^5 mod n求平方。如果是求i^11 mod n呢？只需要对i^5 mod n求平方再乘一个i。讲到这里，联想之前的乘法，我们是否可以得到些什么？能写出递归式吗？
exp(i, j, n)
#Input: three integers,
#Output: i^j mod n
#递归初始步
if j == 0:
return 1;
if j == 1:
return i % n;
#否则，展开递归步
tmp = exp(i, j/2, n)
if j is even:
return tmp*tmp % n
else:
return (tmp*tmp % n) * i mod n
我们从i^2开始列这样一个表，统计计算i^j的所需的乘法次数。
i^2 1次乘法
i^3 2次乘法
i^4 2次乘法
i^5 3次乘法
i^6 3次乘法
i^7 4次乘法
i^8 3次乘法
......
i^1024 ??次乘法
由这个表，我们可以得到求i^j mod所需乘法数与i，j，n这三个参数的哪一个相关，且关系是什么？
使用指数运算来继续寻找规律。这次我们练习使用一下指数运算。你们能把以下代码写成C语言的程序吗？
for i in range(1, n):
for j in range(1, n):
print i**j % n, ＃调用自己编写的exp(i, j, n)
print
这段代码的含义是什么？请自己C语言编程实现。
先看mod素数的情况，令n = 7，得到输出为：
1 1 1 1 1 1
2 4 1 2 4 1
3 2 6 4 5 1
4 2 1 4 2 1
5 4 6 2 3 1
6 1 6 1 6 1
能看出什么吗？再取大一点的数字，令n = 11，得到输出如下：
1 1 1 1 1 1 1 1 1 1
2 4 8 5 10 9 7 3 6 1
3 9 5 4 1 3 9 5 4 1
4 5 9 3 1 4 5 9 3 1
5 3 4 9 1 5 3 4 9 1
6 3 7 9 10 5 8 4 2 1
7 5 2 3 10 4 6 9 8 1
8 9 6 4 10 3 2 5 7 1
9 4 3 5 1 9 4 3 5 1
10 1 10 1 10 1 10 1 10 1
能看出什么？既然我们之前都在看1到n-1的排列，你们能先找出是1到n-1的排列的哪几行吗？
至少我们可以知道：
存在某些数i，i^1, i^2, i^3, ... , i^(n-1), 在mod n运算下，刚好是1到n-1的排列。
慢着，这是n为素数的情形。为什么不尝试一下n为合数的情况呢？比如，令n=8。得到：
1 1 1 1 1 1 1
2 4 0 0 0 0 0
3 1 3 1 3 1 3
4 0 0 0 0 0 0
5 1 5 1 5 1 5
6 4 0 0 0 0 0
7 1 7 1 7 1 7
我们并没有发现有一个i可以通过指数运算刚好恢复出所有的1，2，...，n-1。mod素数情况下存在这样的i，mod合数的情况下不一定存在。因此，我们只能把刚才的结论修订为：
在mod n运算下（n为素数），存在某些数, 刚好是1到n-1的排列。此时，把满足这个属性的 称为mod n的原根。或者称这些i为群的生成元。
在没有涉及群的概念时，我们大概只需要知道通过指数运算，i 生成 了n-1个数。换个角度，如果我们给定生成元i，然后选任意一个大于1小于n的数j，我们如何能求出x，使得 i^x ≡ j mod n ? 注意，n为素数。我们把这种求x的过程称为求离散对数。其实并不难理解，回想一下中学所学到的对数：
求, 即求，使得.
离散对数的区别无非是多了一个mod n。编个程序求离散对数问题将是你们的作业。
我总认为，如果你是计算机新手，首先要问的是计算机不能做什么，而不是现在大家普遍问的，“如何成为计算机高手”，“学计算机如何就业”。当然，这个问题非常难回答。其次，你应该问计算机最擅长做什么，而不要把计算机想象得无所不能，干什么事情都一副吃苦耐劳轻而易举的模样。
这样问的意思是，我们之前学过的算法，计算机是否都可以同样的效率来完成。讲到效率，我们当然是指计算机完成任务所需的时间。但是，为了陈述一种普遍的通用的结论，实际上我们通常用计算机完成某项任务所需执行的（主意）步骤来衡量计算效率。因为，针对特定计算机去计算执行任务的时间往往无法说明问题。例如，我们说求整数a、b的最大公因子需要1秒钟的时间，那么我们到底是指什么型号的计算机呢？而且输入数据到底有多大呢？大家总不能指望超级计算机与个人电脑使用相同的时间吧？也总不会任务无论多大的数据用时都相同。
因此，我们衡量算法效率的方法是要给出以下两大因数的关系：输入数据的大小n，还通常是输入数据的比特长度；在数据大小为n下，完成任务所需要执行的计算步骤。我们还通常称算法的效率为“算法复杂性”。
例子：
求n!的算法factorial，输入大小为n，要计算n!，我们反复迭代进行乘法，n*(n-1)*(n-2)* ...* 2，需要n-2个乘法。所以我们任务这个算法的效率是O(n)。
记号O：大O表示法(可读为Big O)。
O可以理解为一个函数，O(f(n))表示是函数f(n)的上界。
所以，O(n)表示执行算法最多用n步（这是不准确的表示，暂时如此）。
习题：
GCD算法的算法复杂性可用大O表示法表示为什么？
exp算法的算法复杂性可用大O表示法表示为什么？
O的括号里面的函数可以分别是：常数、对数、线性、多项式、指数等，常数复杂性通常表示为O(1)，其他函数可以是：
$log(N)$，$sqrt(N)$，$N$，$N^2$，$2^N$ ，$N!$
大家可以看到，以n为参数的这些函数的“大小”是不一样的，从左到右逐步增大。当我们说某个算法的计算复杂性是O(f(n))，我们是指，目前所能找到最好的算法所需要的计算复杂性是以f(n)为上界。
输入一个整数n，如果它是素数则输出为True，否则输出为False。最简单的方法就是不断用小于根号n的整数去除n，如果可以整除，则非素数。具体的做法当然是循环迭代，代码如下：
＃输入一个比3大大整数
def is_prime(n):
＃不断用大于等于2，小于根号n的整数去除n
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False #可以被整除
return True
这个算法很普通，然而我们要考察其复杂性。因为输入是n，所以，for循环中执行的除法与判断是sqrt(n)步。我们的结论是素性判定算法的复杂性是？
结论似乎没问题。换一个角度看，通常我们对某个特定的整数n并没多大兴趣，我们反而是对某个特点长度的数字比较感兴趣。比如，我们不关心354224848179261915075是否素数，而通常关心一个有1000比特那么长的数，我们能否判定它是否素数。这里是说，我们关注n的比特长度。n的长度为l，n与l的关系是什么？n是小于的一个数，注意，这里是一个指数！所以，复杂性是，即当l增加，判断步骤指数式增加。我们把is_prime的复杂性称为伪多项式的。
问题来了，我们能否有一个“真”多项式的算法判定某个数是否素数呢？
算法是计算机科学的核心，这个说法只能追溯到20世纪80年代，Knuth的TAOCP诞生之后。
我个人认为，算法导论（CLRS）是计算机新手必须尽快学习的一门课程。在过去的若干年我重复呼吁大家学习CLRS，在发现只有呼吁不够之后，我在14级展开了读书指导活动，尤其以15级的开展最为热烈。这份CLRS授课笔记记录了当时的进展与问题。
加入图灵班的第一个重要任务就是与一群热血青年共同研读CLRS。希望这个任务可以在16级更好地完成。
大部分同学不缺乏对成功的渴望，缺乏的是潜心静气对基础知识的研读。请相信我的指导是正确的，你们只需要在这条道路上迈开坚实的步伐。
找规律远比知道一个规律要重要。学会编程，计算机可以帮助我们找到一些规律。请大家尝试编程做以下练习。
给定一个素数p，它可能是4n+1或者4n+3的形式，n是一个小于p的整数。比如，7 ＝ 4*1+3，13 ＝ 4*3+1。给定一个范围，比如100，1000，10000，请分别统计在范围内的这两种类型的素数的个数。也许你会得到一个结论。但是，这个结论是真的吗？为什么？能证明(证伪)吗？
给定一个素数p，对1到p-1之间的数i做平方再mod p。统计平方数中到底出现了多少个不同的数字？多试几个素数，也许你会得出一个结论。这个结论是对的吗？为什么？能证明？
总结一下新生的几个毛病：
第一，自学能力差。
第二，主动学习能力差。
第三，都着急想出成绩，有理想，可是比较虚。
第四，听到很多的意见，分辨不出好坏。
第五，参加过多的社团活动，让自己忙得要命，分身乏术。
斌头老师这2014级《计算机科学导论》课上的一份博客，里面的文章也许有些帮助。大家有空可以看看。其中关于数学、关于英语的阅读的一些建议，还是希望你们可以听听。CS毕业生应具备的特质。CS2013第6章节选－计算机科学的数学要求
新手入门从我的建议开始。
推荐电子书：《计算机科学基础》。
课堂派中“2016图灵班先修班”课程网站，邀请码：E2YJNK。什么是图灵班？
大家好。说一下自己的看法。这两天可能给大家带来了一点困扰。我明白，可能很多同学看不懂。声明一下，不懂都是我的错，不怪你们。这些知识以后将对你们非常简单。只是我迫不及待地想看一下大家是否可以接受。所以，有不明白，不是你们的错。我讲解有跳跃，你们没看课本，加上Q群上教学也不方便，交流有困难等等因素，都带来了理解上的困难。一定一定要记住：没关系！千万不要想多了，什么完全不懂啊，自己不适合啦，其他同学懂得好多啦。没这些事情。我要是能有所帮助，我很高兴。要是没帮助，直接忽略我。我可能没做错的就是让你们看书。总结一句：多阅读，为即将来袭的大学生活做更充分的准备。如果能做到这一点，我将非常高兴。
不是就太可惜了！如果你们的语文是我教出来的，那一定很棒！希望以后你们可以骄傲地宣称：我地语文是斌头老师教滴～
胡诗娴已经乐呵呵地宣传：斌头老师开始讲形容词了......主要是还太不了解我！
写作文，首先要客观！客观，就是要忘我，不要以个人感情来替代准确的表达、严格的论证。
其次，写作文一定要少用形容词，不要用成语和名人名言！
第三，写作文不要用套路！什么“随着社会的发展”或者“with the development of” 都是要给不及格的。
第四，写作文要禁止喊口号！
第五，现在懒得写！
经过一个星期所谓的QQ授课，也该停止折腾了。一个星期来，提问的同学凤毛麟角，这是颇在意料之中，但是也是非常不愿意看到的局面。看来，老师求大家学的局面将持续保持，而主动求学的同学实在是少。也许有同学看了不服气。不服就不服，走着瞧。
这里的内容持续更新。课堂派的作业持续增加。想学的就看，有问题就Email见吧。
我说过，我在CS一呆就是20多年。现在所做的都不是什么心血来潮的事情，现在所见的学生无论有多优秀或者多糟糕都不会令人惊喜或令人失望或者......其实我是想说，无论你们怎么样，我都这个样！我懂你们，尽管你们不懂我。
不要跟我说你是小白，我反正不会同情。不要跟我说你不懂，我对“不懂”无能为力。不要跟我说你不想努力，你肯定做不了不努力的第一人。不要跟我说你很努力很有理想，talk is cheap，说的用处不大，拿出行动才是正道。
1、电脑随便买一台，虽然你们都不是随便的人。最好买Mac book！
2、重点是要装Linux（Macbook就免了，只是千万别Macbook上装个Windows！），Ubuntu是新手的不错选择。上网下载安装。为什么要完全工作在Linux下？
3、是否可以虚拟机？是否一定要双系统？这不是关键，看着办。建议不要用虚拟机。
4、gcc编程，结合Think like a computer seientist，边看边动手。随便一个编辑软件：Atom、Emacs、Vim。
5、git＋hexo，搭建一个博客，这是指南。
6、自己练习一下Python，有Think like a computer scientist版本的电子书，网上一大把。第二版很不错。
7、Sage！CSers的好朋友。
同学们，你们还记得在幼儿园的时候自己背出了26个英文字母之后沾沾自喜向妈妈炫耀的情形吗？离你能背26个英文字母的那一刻到现在估计有个10-15年了吧？
这个月也许我听得最多的是，“我是小白”，“我英语好烂”。这种主观陈述意义不大。奇怪的是，每年我们的大一新生也最喜欢说这两句，我都听腻了。于是我就问，你们高考不是考了？你们应该学了啊。回答：都用来应付考试。我怎么知道不是应付考试，但是现在考完了，该用了啊。回答：没学好。学啊！
好吧，其实以上是可以忽略的废话。
正确的观点是：你们必须学习英语，并熟练地运用英语。其潜台词是，你们的英语都还不足以应付未来的需要。所以，最正确的建议就是，抛开高中英语学习模式，进入实战模式，即，在实际工作学习中使用英语、学习英语。我坚持大家需要英语课本的原因：
1、你们继续需要学习英语、考英语。
2、你们需要在未来的学习工作中使用英语。
3、目前有非常优秀的英语资料；未来最前沿的科技文献也将以英文的形式出现。
4、中文的教材往往缺陷较多。
关于英语阅读我写过一篇小文章，希望有所帮助。
有兴趣的来Email联系！