本文為非常規(guī)的《計(jì)算機(jī)科學(xué)導(dǎo)論》課程講義孔飒，適用于大一新生。初學(xué)者可能會(huì)覺得有點(diǎn)難艰争。最好是不要畏難坏瞄，跟上思路。相信沒有那么難甩卓。--斌頭老師
計(jì)算機(jī)專業(yè)學(xué)什么鸠匀？
從計(jì)算機(jī)科學(xué)的本質(zhì)開講。學(xué)“計(jì)算機(jī)科學(xué)”到底是學(xué)什么逾柿？本質(zhì)上缀棍，Computer Science不是學(xué)計(jì)算機(jī)，不是學(xué)計(jì)算機(jī)的使用也不是學(xué)計(jì)算機(jī)的制造机错。學(xué)的是“計(jì)算”-- Computation爬范。
通常，大家進(jìn)入這個(gè)專業(yè)多數(shù)是因誤解而來弱匪，從今天開始青瀑，也許需要換一下思維了。這也就是我為什么一直推薦How to Think like a Computer Scientist（HTCS）而不是其他比如C++ Primer之類的書為入門書的原因萧诫。關(guān)鍵不在于是否學(xué)會(huì)編程斥难，而是要如何改變思維。
那到底什么是計(jì)算帘饶？這個(gè)問題很復(fù)雜哑诊，然后具體落實(shí)到計(jì)算機(jī)的實(shí)現(xiàn)上卻又非常簡(jiǎn)單。這是兩個(gè)問題及刻。第一搭儒，什么是計(jì)算？這個(gè)暫時(shí)還回答不了提茁。第二是淹禾，怎么計(jì)算。這個(gè)可以有一個(gè)簡(jiǎn)單的初始到答案：二進(jìn)制茴扁。
“世界上有10種人铃岔，一種懂二進(jìn)制，一種不懂！”你們是其中的第一種毁习。改變思維的第一步智嚷，就是認(rèn)識(shí)二進(jìn)制。
二進(jìn)制的定義及運(yùn)算規(guī)則
注：本章內(nèi)容并不涉及負(fù)數(shù)纺且，即統(tǒng)統(tǒng)考慮無符號(hào)數(shù)盏道。
首先我們給出二進(jìn)制數(shù)字的描述。
二進(jìn)制：只有0和1兩位數(shù)字载碌，每一位我們稱為一個(gè)bit（比特）猜嘱。
計(jì)算規(guī)則：0+0 = 0，0+1 = 1嫁艇，1+1 = 10朗伶，10+1 = 11
現(xiàn)在可以歸納一下規(guī)律了。
0步咪，1论皆，10，11猾漫，...点晴，1111，...悯周， 這樣的數(shù)字有沒有遍歷完所有的我們之前認(rèn)識(shí)的十進(jìn)制正整數(shù)觉鼻？答案是，yes队橙！然后坠陈，我們還知道，二進(jìn)制加法無非就是“逢二進(jìn)一”捐康。
十進(jìn)制數(shù)無非就是偶數(shù)和奇數(shù)兩種仇矾。請(qǐng)問，偶數(shù)在二進(jìn)制中長(zhǎng)什么樣子解总？答：最后一個(gè)bit為0 贮匕。
于是我們有以下規(guī)則：
0結(jié)尾的二進(jìn)制數(shù)是偶數(shù)；1結(jié)尾的二進(jìn)制數(shù)是奇數(shù)花枫。
例子：
2對(duì)應(yīng)10刻盐，4，對(duì)應(yīng)100劳翰，8對(duì)應(yīng)1000敦锌，16對(duì)應(yīng)10000
大家有沒有看到10后面加個(gè)0等于是乘二？好像我們可以得出一個(gè)規(guī)律: 在一個(gè)二進(jìn)制數(shù)后面補(bǔ)一個(gè)零等于乘二佳簸？
一般來說乙墙，沒接觸過二進(jìn)制的同學(xué)在回答上面這個(gè)問題的的時(shí)候基本都是說：“No！”因?yàn)檫@里如果考慮奇數(shù)，那么听想，很可能不對(duì)腥刹！但是，乘二不是在后面補(bǔ)零汉买？末尾為零不就是偶數(shù)衔峰？這......有什么不對(duì)呢？
例子：
十進(jìn)制7 ＝＝ 二進(jìn)制 111
7*2 == 14 == 二進(jìn)制 1110
似乎是這么個(gè)理蛙粘？再演算一下其他數(shù)字......得到乘法規(guī)則如下：
二進(jìn)制乘2運(yùn)算等于在數(shù)字末尾補(bǔ)一個(gè)0.
思考一下垫卤，乘法是補(bǔ)0，除法呢组题？我們只考慮整除葫男，即只取整數(shù)商抱冷。
例子：
十進(jìn)制7的二進(jìn)制為111崔列，十進(jìn)制7/2 == 十進(jìn)制3 == 二進(jìn)制 11
十進(jìn)制11的二進(jìn)制為1011，十進(jìn)制11/2 == 十進(jìn)制5 == 二進(jìn)制101
除法規(guī)律：
二進(jìn)制除2運(yùn)算等于在砍掉數(shù)字末尾一個(gè)數(shù)位旺遮。
如何把任何的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制赵讯？這是下一節(jié)的內(nèi)容。
補(bǔ)充練習(xí)：
給定一個(gè)整數(shù)v耿眉，如何判斷v是否2的某次方（Power of 2）边翼？
比如，v = 4 = 2^2鸣剪，返回True组底；v = 9 并非2的次方，返回False筐骇。
請(qǐng)寫一個(gè)C語(yǔ)言的函數(shù)來實(shí)現(xiàn)债鸡。
二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)
歸納一下之前的內(nèi)容。首先铛纬，計(jì)算機(jī)科學(xué)是關(guān)于“計(jì)算”的科學(xué)厌均，是關(guān)于“思維”的科學(xué)。然后告唆，介紹了二進(jìn)制棺弊，當(dāng)然是非正式地介紹，為的是歸納出兩個(gè)規(guī)則：在后補(bǔ)零等于乘2（擴(kuò)展思考擒悬，除2怎么做模她？）；尾數(shù)為0的數(shù)是偶數(shù)（尾數(shù)為1的是奇數(shù)）《粒現(xiàn)在缝驳，我們需要思考的是如何在二進(jìn)制數(shù)與十進(jìn)制數(shù)之間進(jìn)行轉(zhuǎn)換。特別是，我們不要滿足于怎么做用狱，還要思考為什么运怖。更重要的是，我們想得到一個(gè)“過程”：一個(gè)計(jì)算機(jī)可以讀懂的過程夏伊。
當(dāng)我們思考一個(gè)過程的時(shí)候摇展，首要必須確定的是：輸入什么，輸出什么溺忧。比如咏连，我們命名將二進(jìn)制轉(zhuǎn)換為十進(jìn)制的過程為B2D，這只是一個(gè)名字鲁森。
例子：
function B2D(a)
輸入：一個(gè)二進(jìn)制數(shù)a
輸出：a所代表的十進(jìn)制數(shù)
在完全描述出這個(gè)程序之前祟滴，我們先計(jì)算一些實(shí)例出來，比如：
例子：
輸入0歌溉，立即輸出0垄懂；輸入1立即輸出1！這太簡(jiǎn)單痛垛，但是請(qǐng)注意草慧，這很重要！
考慮多比特輸入匙头。比如：
輸入：1110漫谷；輸出：1110代表的十進(jìn)制（記為Res）。根據(jù)之前的規(guī)則蹂析，補(bǔ)零等于乘2舔示，所以，這個(gè)數(shù)必然是
111表示的十進(jìn)制數(shù)乘2５绺АＬ璧尽！所以喻频，我們的計(jì)算結(jié)果就是2*B2D(111)缩宜。
但是，如果是奇數(shù)呢甥温？比如锻煌，輸入1111 。Ok姻蚓，沒關(guān)系宋梧，我們照樣可以得到結(jié)果：2*B2D(111) + 1 ，多加個(gè)1就好了狰挡。
所以捂龄，我們可以完成我們的程序描述了：
注意：＃代表注釋释涛！
function B2D(a)
#輸入：一個(gè)二進(jìn)制數(shù)a
#輸出：a所代表的十進(jìn)制數(shù)
if a < = 1: #程序的終止條件
return a; #即，當(dāng)a小于等于1倦沧，原樣輸出.
else: #否則
return 2*B2D(a/2) + lsb(a) #lsb(x)指的返回x的最后一個(gè)比特.
請(qǐng)注意一點(diǎn)唇撬，我們現(xiàn)在只有二進(jìn)制數(shù)操作的兩個(gè)規(guī)則：乘2等于補(bǔ)零；0為偶數(shù)展融，1為奇數(shù)窖认。上面這個(gè)程序違反規(guī)則了沒？有啊告希，怎么能用除法“/”扑浸？其實(shí)，這里的除法就是把a(bǔ)的最后一個(gè)比特刪除燕偶。而lsb(a)指的是a的最后一個(gè)比特喝噪。
這個(gè)程序中最古怪之處是：2*B2D(a/2) + lsb(a)。因?yàn)橹该矗@里B2D這個(gè)程序自己調(diào)用了自己Ｔ途濉！涧尿！我們把這種自己調(diào)用自己的過程稱為“遞歸”系奉。
所有計(jì)算無非遞歸而已檬贰！所有的思維都是遞歸的姑廉！
作業(yè)：用C語(yǔ)言實(shí)現(xiàn)以上程序中的“除2”運(yùn)算及l(fā)sb過程。
十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)
現(xiàn)在反過來翁涤，如果要從十進(jìn)制得到二進(jìn)制應(yīng)該如何桥言？通常，我們的課程會(huì)像這樣教葵礼，如下圖：
我們當(dāng)然不能滿足于知道這個(gè)方法号阿，要多問一句，為什么鸳粉？好扔涧，重新來，思維運(yùn)動(dòng)起來届谈！現(xiàn)在我們要寫一個(gè)名字為“D2B”的程序枯夜，輸入一個(gè)十進(jìn)制數(shù)，輸出一個(gè)二進(jìn)制數(shù)艰山。
function D2B(a)
輸入：一個(gè)十進(jìn)制數(shù)a
輸出：a所代表的二進(jìn)制數(shù)
思路如下：
首先湖雹，我們需要得到程序的終止條件。如果 a< = 1曙搬，怎么樣摔吏？輸出a鸽嫂！然后，計(jì)算無非遞歸征讲，遞歸起來据某！比如，7這個(gè)數(shù)诗箍，我們能知道它最后一個(gè)比特是什么嗎哗脖？奇數(shù)，當(dāng)然是1 扳还。如果是16呢才避？偶數(shù)，當(dāng)然是0 氨距。就是說桑逝，對(duì)任意輸入，我們至少知道了部分答案俏让，a的最后一個(gè)比特楞遏。剩下的比特who care？交給遞歸笆孜簟寡喝！我們得到D2B(a')＋lsb(a)，其中a'是a刪除最后一比特之后的數(shù)勒奇。呃预鬓，忘記了，a是十進(jìn)制數(shù)呢赊颠？沒事格二，除法嘛瞭恰，除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 粤剧，這樣的過程為什么會(huì)結(jié)束痘括？也許很多同學(xué)立即會(huì)擔(dān)心长窄，遞歸怎么會(huì)結(jié)束呢？
為什么遞歸會(huì)終止纲菌？因?yàn)槊恳粋€(gè)遞歸程序都有一個(gè)終止條件挠日。而且，每次自己調(diào)用自己的時(shí)候驰后，參數(shù)都在減兴磷省（這很重要），這就確保了終止條件一定會(huì)到達(dá)灶芝。
遞歸效率低郑原？我的回答是：思維唉韭，不在乎效率；其次犯犁，遞歸并不總是低效率属愤。相信提這個(gè)問題的同學(xué)學(xué)過一些，但是酸役，對(duì)遞歸的理解不能那么片面住诸。以后繼續(xù)深入。
作業(yè)題：用C語(yǔ)言編程實(shí)現(xiàn)以下過程涣澡。
function fac(n)
輸入：整數(shù)n
輸出：n的階乘
要求：必須使用遞歸
最后一個(gè)內(nèi)容贱呐，這是世界上最有意思的問題之一。話說有兩只兔子......
作業(yè)：斐波那契數(shù)列：1 1 2 3 5 8 13 21...... 請(qǐng)用C語(yǔ)言用遞歸的方法寫出第n項(xiàng)斐波那契數(shù)入桂。
function fib(n)
輸入：整數(shù)n
輸出：第n項(xiàng)斐波那契數(shù)
要求：必須使用遞歸
計(jì)算即遞歸
計(jì)算機(jī)的核心是CPU奄薇，我們總是希望這些個(gè)核心設(shè)備做盡可能少的“操作”，但是借助它又似乎無所不能抗愁。這似乎矛盾馁蒂，其實(shí)又不矛盾。上面講到二進(jìn)制的加法和乘2蜘腌。然后講到用遞歸的方法去思考沫屡。
接下來，先延續(xù)上面的思路撮珠，出一道題沮脖，實(shí)現(xiàn)二進(jìn)制數(shù)的乘法：
function multiply(a,b)
輸入: a和b，兩個(gè)任意長(zhǎng)的二進(jìn)制數(shù)劫瞳；
輸出：a*b 倘潜。
要求：請(qǐng)用遞歸的方法绷柒，并且只能用加法和乘2操作來完成，不要寫程序废睦，用我昨天的描述方法即可伺绽。
建立、改變思維方式應(yīng)該放第一位嗜湃，請(qǐng)不要小看這些似乎沒用的東西奈应。
例子：
11*1 ＝11；11＊0 ＝＝0购披；
11 * 10 ＝＝110杖挣，實(shí)際就是11乘2，即11后面補(bǔ)個(gè)0刚陡；
如果是11 * 11惩妇？當(dāng)然應(yīng)該是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 is_even(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;
這個(gè)乘法算法展示氓皱，計(jì)算機(jī)只要乘2和加法就可以做任何乘法路召，對(duì)嗎？但是波材，我們?cè)趺床恢v除法和減法呢股淡？下回分解。
練習(xí)：
用C語(yǔ)言編程實(shí)現(xiàn)is_even()和is_odd() 函數(shù)廷区。
is_even()揣非，如果輸入為偶數(shù)，返回True躲因，否則返回False早敬。
is_odd判斷輸入是否奇數(shù)。
作業(yè): 用C語(yǔ)言編程實(shí)現(xiàn)兩個(gè)整數(shù)的乘法大脉。
要求搞监，不能用遞歸！
2017-06-29晚整理
