原本想把每周的課程內(nèi)容放在一篇文檔中，無(wú)奈Martin的信息密度太大，所以把每周內(nèi)容按照自然發(fā)生的狀況拆解為兩篇--optional lecture & lecture舌界。由于邏輯層級(jí)比較多综芥，所以標(biāo)題使用paper的標(biāo)題方法，X + X.X + X.XX ...反砌，方便檢索雾鬼。

1.Pre-reading

1.1 Introduction to Unix

1.1.1 Unix Commands (with/without options/arguments)

（1）cal: 進(jìn)入calendar，只有一個(gè)option "cal"
（2）cal 2017：進(jìn)入2017年歷宴树，在option "cal" 后加入一個(gè)argument "2017"
（3）cal 3 2017：進(jìn)入2017年3月月歷策菜，在option "cal" 后加入2個(gè)argument "3"和"2017"
（4）date：顯示當(dāng)前日期時(shí)間，只有一個(gè)option "date"
（5）清空顯示--control + L
（6）./source + "文件名"--在terminal中運(yùn)行“文件名”酒贬，例如 . test或者source test
（7）sudo + "命令"--以系統(tǒng)管理員身份運(yùn)行"命令"又憨，sudo是superuser do，例如sudo pip3 install bs4锭吨，用系統(tǒng)管理員身份運(yùn)行pip3安裝bs4包
（8）tar xf + "文件名"--解壓“文件名”蠢莺，tar是tape archive，xf是extract file零如，文件應(yīng)該是壓縮文件
（9）esc + b--命令行向后回退浪秘，b是backward
（10）ese + f--命令行向前前進(jìn)，f是forward

課程review：
（1）cd代表change directory
（2）ls代表list
（3）cat代表concatenate
（4）python默認(rèn)進(jìn)入python2
（5）python3進(jìn)入python3
（6）退出python的快捷鍵是control + D
（7）echo用來(lái)顯示內(nèi)容
（8）echo “alias python = python3” > .profile
改變Terminal中環(huán)境變量埠况，python代表python3

1.1.2 Syntax for paths

（1）pwd--print working directory耸携，顯示當(dāng)前路徑
（2）mkdir--make directory，可以簡(jiǎn)單理解為windows下創(chuàng)建文件夾辕翰，例如mkdir test夺衍。還可以同時(shí)創(chuàng)建多個(gè)同級(jí)路徑，例如mkdir test1 test2 test3
（3）control + A--回到輸入命令的最前面
（4）esc + del--刪除前面輸入的命令喜命，esc和del都是鍵盤(pán)上的按鍵
（5）TAB--自動(dòng)補(bǔ)全命令沟沙，比如輸入路徑時(shí)，路徑名為/Users/lecture_1/壁榕，那么可以輸入/U + TAB矛紫。TAB + TAB顯示所有符合已經(jīng)輸入前綴的文件
（6）路徑中"~"（引號(hào)中內(nèi)容代表命令）代表home directory，由環(huán)境變量設(shè)定的位置牌里，默認(rèn)是盤(pán)符颊咬，課上Martin設(shè)置在COMP9021的路徑上
（7）cd ..--返回路徑上一級(jí)
（8）mkdir -p XXX/XXX--創(chuàng)建多級(jí)路徑务甥，-p是path的縮寫(xiě)，后面的XXX/XXX是目錄下的目錄喳篇，例如mkdir -p home/test
（9）ls "路徑名"--顯示”路徑名“下文件敞临，例如ls home。ls -a顯示所有文件麸澜，包括隱藏文件挺尿。ls -l顯示文件詳細(xì)信息，包括權(quán)限等炊邦。
（10）absolute path絕對(duì)路徑编矾，指目錄下的絕對(duì)位置，直接到達(dá)目標(biāo)位置馁害，通常是從盤(pán)符開(kāi)始的路徑窄俏，例如 /Users/desktop/XXX
（11）>/touch + "文件名"--創(chuàng)建"文件名"，>或者touch都可以作為option蜗细，后面加一個(gè)文件名即可裆操，例如> file_1或者touch file_1
（12）rm + "文件名"--刪除"文件名"，例如rm file_1
（13）mv + "文件名" + "路徑"--把"文件名"移動(dòng)到"路徑"炉媒，例如mv file_1 ../test踪区，含義是把file_1移動(dòng)到當(dāng)前目錄上一級(jí)再轉(zhuǎn)移到上級(jí)目錄的test路徑下
（14）chmod--change mode設(shè)置文件權(quán)限的命令，后面的數(shù)字表示不同用戶(hù)或用戶(hù)組的權(quán)限吊骤，r是read缎岗，w是write段标，x是execute捉貌，詳見(jiàn)https://en.wikipedia.org/wiki/Chmod，中文見(jiàn)https://zh.wikipedia.org/wiki/Chmod
（15）echo $PATH--顯示echo執(zhí)行路徑遵岩，注意PATH要大寫(xiě)
（16）cp -r + "路徑1" +"路徑2"--把"路徑1"復(fù)制到"路徑2"鸭巴，cp是copy眷细，-r是recursive，例如cp -r ../test1 ../test2鹃祖，含義是把當(dāng)前目錄上一級(jí)的test1路徑拷貝到上一級(jí)目錄的test2
（17）man + "option"--查看"option"的manual溪椎，例如man cp，查看copy的manual恬口，查看時(shí)"空格"是向下操作校读，"U"是向上操作，"Q"是退出manual
（18）*--wild card通配符祖能，例如歉秫，test_*代表所有以test_開(kāi)頭的文件

1.2 Software Installation and Jupyter

1.2.1 安裝Jupyter

pip3 install jupyter
（1）pip3 install XXX--使用pip3安裝XXX养铸，比如安裝課上用到的bs4，pip3 install bs4
（2）pip3 list--顯示所有pip3安裝的內(nèi)容
（3）pip3 list --outdated--顯示需要更新的安裝包
（4）pip3 -U "安裝包名"--更新"安裝包名"筛圆，-U是update太援，例如pip3 -U jupiter

如何解決安裝后無(wú)法運(yùn)行Jupyter的問(wèn)題仙蛉？
1.確定安裝了jupiter
2.輸入find / -name "jupiter"
3.輸入2后看到對(duì)應(yīng)的路徑 例如:/Library/Frameworks/Python.framework/Versions/3.6/bin/jupyter
4.export PATH=$PATH:/Library/Frameworks/Python.framework/Versions/3.6/bin/ #注意$PATH后邊是你自己查找得結(jié)果 不一樣的人可能不一樣 不要丟掉冒號(hào) 最后只輸入到文件夾 把jupiter去掉
5.再運(yùn)行jupiter試試
——muyang

1.2.2 運(yùn)行Jupyter

jupyter notebook
（1）在jupyter中運(yùn)行文件代碼的快捷鍵是control + enter
（2）清除運(yùn)行的結(jié)果—在jupyter頁(yè)面選擇cell-all output-clear
（3）在Terminal中終止jupyte的快捷鍵是control + C

1.3 Running Python code

（1）在terminal中運(yùn)行python文件，輸入python3 + ”文件名“，例如篮绰，python3 test.py吠各，注意勉抓，文件名一定要以.py結(jié)尾，以.py結(jié)尾的文件也叫做module
（2）在terminal中運(yùn)行python纵散，輸入python3困食，會(huì)出現(xiàn)”>>>“的prompt硕盹，之后像python軟件中一樣操作啊胶，比如輸入2 ** 3，terminal輸出8
（3）在terminal中輸入python3運(yùn)行后某饰，可以用import + "文件名"的形式導(dǎo)入module
（4）文件名不要有空格出現(xiàn)，否則terminal中處理項(xiàng)目會(huì)出現(xiàn)錯(cuò)誤炬守，養(yǎng)成把空格用_替代的習(xí)慣
（5）vim中减途，w命令是move forward by one word鳍置，b命令是move backward by one word墓捻，X命令是delete previous character坊夫，r命令是replace character，:wq命令是保存退出vim

2.Lecture

考試形式是機(jī)考

2.1 Jupyter Notebook Sheets

可以從課程材料中下載环凿，建議用jupter notebook運(yùn)行，自行學(xué)習(xí)智听。學(xué)習(xí)中羽杰，先判斷運(yùn)行結(jié)果到推，再運(yùn)行核對(duì)莉测，有問(wèn)題及時(shí)google查詢(xún)或者在python tutorial中查看忍抽。

2.2 Turing machine

傳說(shuō)中的圖靈機(jī)干跛，可以理解為數(shù)學(xué)邏輯機(jī)，可以看作等價(jià)于任何有限邏輯數(shù)學(xué)過(guò)程的終極強(qiáng)大邏輯機(jī)器祟绊。圖靈機(jī)用機(jī)器來(lái)模擬人們的數(shù)學(xué)運(yùn)算楼入，機(jī)器只有兩種操作：1.書(shū)寫(xiě)或者擦除某個(gè)符號(hào)；2.移動(dòng)位置久免。圖靈機(jī)是一種無(wú)限長(zhǎng)的紙帶（tape）浅辙，開(kāi)始的位置是head扭弧，有一套控制規(guī)則table阎姥，以及一個(gè)狀態(tài)寄存器（用來(lái)記錄當(dāng)前狀態(tài)）。
A Turing machine is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a table of rules. (https://en.wikipedia.org/wiki/Turing_machine)
課程材料中有一個(gè)文件是turing_machine_simulator.py鸽捻，使用上文提到的運(yùn)行python的方式運(yùn)行它以啟動(dòng)圖靈機(jī)呼巴。關(guān)于該圖靈機(jī)的使用方法，在圖形操作界面的最上方有一個(gè)Turing Machine Stimulor Help御蒲，查看具體的使用方法衣赶。（核心內(nèi)容已經(jīng)加粗）

Tape:
Control clicking to the right or to the left of the current rightmost or leftmost cell, respectively, adds a new cell.
Control clicking on the current rightmost or leftmost added cell removes it.
Clicking on any cell flips the bit it contains from 1 to 0 or from 0 to 1.
Program:
A program is a set of instructions of the form (state1, bit1, state2, bit2, dir) where state1 and state2 have to be alphanumeric words with at most 8 characters, bit1 and bit2 have to be 0 or 1, and dir has to be L or R.
When the TM machine is in state state1 with its head pointing to a cell containing bit1, then it changes bit1 to bit2 in that cell, modifies its state to state2, and moves its head one cell to the right or to the left as determined by dir.
The TM machine is supposed to be deterministic, hence the program should not contain two instructions starting with the same pair (state1, bit1).
The program can contain comments, namely, lines starting with #.
Execution:
When the leftmost button displays Start, the status indicator is red, the tape can be modified, the program can be edited, the Step and Continue buttons are disabled, and no State or Iteration is displayed.
Once this button has been pressed, it displays Stop, the status indicator is green, the tape cannot be modified, the program cannot be edited, and the current State and Iteration are displayed.
When execution stops, either because no instruction can be executed or because Stop has been pressed, the Step and Continue buttons are disabled and the leftmost button displays Reset; it has to be pressed to restore the tape to its initial configuration, with only the "origin" cell containing 1.
Pressing the Start button prompts the user for an initial state, which has to be an alphanumeric word with at most 8 characters, and commences execution provided at least one cell contains 1, in which case the head initially points to the leftmost cell containing 1.
The Step button executes one instruction, if possible; otherwise execution stops.
The Continue buttom executes up to 1,000 instructions, if possible; otherwise execution stops.
The Stop button allows one to start a new excution in case it is either not desirable or not possible to terminate execution with a sequence of clicks on the Step or Continue buttons.

二進(jìn)制中，1是1碘箍，2是10遵馆，3是11；圖靈機(jī)中丰榴，只用位置表達(dá)數(shù)字四濒，1是1换况，2是11，3是111喳资。

2.2.1 無(wú)限改變數(shù)字

從左向右保留現(xiàn)有狀態(tài)所有的1觉吭，把0全都變成1，無(wú)限操作

stupid 1 stupid 1 R
如果stupid狀態(tài)遇見(jiàn)1骨饿，那么保留該狀態(tài)和數(shù)字1亏栈，向右移動(dòng)1位
stupid 0 stupid 1 R
如果stupid狀態(tài)遇見(jiàn)0台腥，那么保留該狀態(tài)，將數(shù)字0改成1绒北，向右移動(dòng)1位

由于所有的情況都有定義黎侈，所以程序會(huì)無(wú)限進(jìn)行下去，直到溢出闷游。

2.2.2 有限改變數(shù)字

從左向右把從開(kāi)始連續(xù)的1全都變成0峻汉，保留所有的0，所有1都改變成0時(shí)停止

stupid 1 stupid 0 R
如果stupid狀態(tài)遇見(jiàn)1脐往，那么保留該狀態(tài)休吠，將數(shù)字1改成0，向右移動(dòng)1位

由于stupid狀態(tài)沒(méi)有定義遇見(jiàn)0业簿，所以遇見(jiàn)0時(shí)程序結(jié)束

2.2.3 數(shù)字加1運(yùn)算

（1）最直接想到的解決方式是從左向右運(yùn)行程序瘤礁，把右邊遇到的第一個(gè)0改成1

work 1 work 1 R
work 0 end 1 R/L
如果work狀態(tài)遇見(jiàn)0，那么改變狀態(tài)到end梅尤，將數(shù)字0改成1柜思，向左/右移動(dòng)1位，這里移動(dòng)方向不重要

程序結(jié)束的原因是改變到end狀態(tài)后巷燥，程序中沒(méi)有定義任何關(guān)于遇到end狀態(tài)下的0或者1該如何處理赡盘，所以停止運(yùn)行。
當(dāng)數(shù)字很小的時(shí)候缰揪，這個(gè)程序運(yùn)行沒(méi)什么問(wèn)題陨享，但是當(dāng)數(shù)字非常大，比如1億钝腺，這個(gè)時(shí)候從左到右不斷check是不是1的過(guò)程會(huì)變得非常緩慢抛姑，所以要優(yōu)化程序。
（2）優(yōu)化程序的辦法就是不去尋找最右邊的第一個(gè)0拍屑，而是思考我們核心要完成什么任務(wù)途戒？應(yīng)該是在一堆連續(xù)的1上增加一個(gè)1，這個(gè)1增加在右邊還是左邊都沒(méi)有根本影響僵驰。所以想到可以直接在左側(cè)增加一個(gè)1來(lái)完成任務(wù)喷斋。

work 1 work 1 L
work 0 end 1 L/R

2.2.4 兩個(gè)數(shù)的加法

如何存儲(chǔ)兩個(gè)數(shù)字？用一個(gè)0間隔開(kāi)兩個(gè)數(shù)蒜茴，比如存儲(chǔ)3和5星爪，那么表達(dá)是：1110111111，左邊3個(gè)1代表3粉私，然后1個(gè)0代表separation顽腾，之后5個(gè)1代表5.
基于上述方法的加法解決方式：由于是兩個(gè)數(shù)相加得到一個(gè)數(shù)，所以必須把separation的0改成1，這樣在原基礎(chǔ)上就會(huì)得到比正確結(jié)果大1的數(shù)抄肖，所以要?jiǎng)h除最開(kāi)始的一個(gè)1久信。例如3+5，最開(kāi)始的存儲(chǔ)是1110111111漓摩，如果把separation的0改成1裙士，那么變成1111111111，代表數(shù)字9管毙，比答案8大1腿椎，所以要再刪除最開(kāi)始的一個(gè)1。為什么是最開(kāi)始的1夭咬？根據(jù)上面數(shù)字加1運(yùn)算的實(shí)例啃炸，刪除左側(cè)的1是速度最快的。

del 1 mov 0 R
mov 1 mov 1 R
mov 0 end 1 R

2.2.5 一個(gè)數(shù)除以2

如果一個(gè)數(shù)是偶數(shù)卓舵，那么除以2意味著把原來(lái)2n個(gè)1變成n個(gè)1南用，例如8/2=4，就是11111111變成1111边器；
如果一個(gè)數(shù)是奇數(shù)训枢，那么除以2意味著把原來(lái)2n+1個(gè)1變成n個(gè)1，例如7/2=3忘巧，就是1111111變成111。
所以睦刃，程序應(yīng)該是先從最開(kāi)始刪除遇見(jiàn)的2個(gè)1砚嘴，然后一路向右到原來(lái)數(shù)字的結(jié)尾，找到一個(gè)separation0涩拙，在其后一位增加一個(gè)1际长。然后一路向左返回到數(shù)字開(kāi)始的地方，重復(fù)之前的操作兴泥。終止結(jié)果是separation0左側(cè)再也沒(méi)有兩個(gè)1（一個(gè)1是奇數(shù)的情況工育，直接去尾即可）

del1 1 del2 0 R
刪除遇見(jiàn)的第一個(gè)1，狀態(tài)從’刪除1‘改成’刪除2‘搓彻，因?yàn)楣惨獎(jiǎng)h除兩個(gè)1如绸，用狀態(tài)的刪除X來(lái)記錄刪除的個(gè)數(shù)
del2 1 movR1 0 R
刪除遇見(jiàn)的第二個(gè)1，狀態(tài)從’刪除2‘改成’右移1‘旭贬，因?yàn)閯h除2個(gè)1后要一路右移直到創(chuàng)建結(jié)果怔接，用狀態(tài)’右移1‘的數(shù)字1代表在第一個(gè)數(shù)中
movR1 1 movR1 1 R
如果在第一個(gè)數(shù)中，狀態(tài)和數(shù)字都不變稀轨，一路向右直到間隔符0
movR1 0 movR2 0 R
第一個(gè)數(shù)字結(jié)束時(shí)扼脐，遇見(jiàn)數(shù)字0，把它當(dāng)做間隔符奋刽，數(shù)字不變瓦侮，狀態(tài)改為’右移2‘艰赞，用狀態(tài)’右移2‘的數(shù)字2代表進(jìn)入第二個(gè)數(shù)（即結(jié)果的數(shù)字）
movR2 1 movR2 1 R
如果在第二個(gè)數(shù)字中右移遇見(jiàn)數(shù)字1，則一路繼續(xù)向右直到第二個(gè)數(shù)字結(jié)尾
movR2 0 movL2 1 L
如果在第二個(gè)數(shù)字中遇見(jiàn)第一個(gè)數(shù)字0肚吏，則把它變成數(shù)字1猖毫，完成除以2的任務(wù)，然后狀態(tài)變成’左移2‘须喂，用狀態(tài)’左移2‘的數(shù)字2代表在第二個(gè)數(shù)中
movL2 1 movL2 1 L
如果在第二個(gè)數(shù)字中左移遇見(jiàn)數(shù)字1吁断，則一路繼續(xù)向左直到間隔符0
movL2 0 movL1 0 L
第二個(gè)數(shù)字結(jié)束時(shí)，遇見(jiàn)間隔符0坞生，數(shù)字不變仔役，狀態(tài)改為’左移1‘，用狀態(tài)’左移1‘的數(shù)字1代表進(jìn)入第一個(gè)數(shù)
movL1 1 movL1 1 L
如果在第一個(gè)數(shù)字中左移遇見(jiàn)數(shù)字1是己，則一路繼續(xù)向左直到第一個(gè)數(shù)字結(jié)束
movL1 0 del1 0 R
第一個(gè)數(shù)字結(jié)束后遇見(jiàn)數(shù)字0又兵，數(shù)字不變，狀態(tài)從’左移1‘轉(zhuǎn)變到’刪除1‘卒废，繼續(xù)前面的步驟沛厨，直到運(yùn)算結(jié)束

程序終止的原因是：如果數(shù)字是偶數(shù)，那么會(huì)在del1狀態(tài)遇見(jiàn)0摔认，該指令未定義逆皮，程序結(jié)束；如果數(shù)字是奇數(shù)参袱，那么會(huì)在del2狀態(tài)遇見(jiàn)0电谣，該指令未定義，程序結(jié)束.

2.3 Python3-Introduction to operators, lists, dictionaries, strings and control structures

使用課程提供的jupyter notebook sheet輔助學(xué)習(xí)抹蚀。

2.3.1 python模擬圖靈機(jī)

f = open('division_by_2.txt')  
for line in f:
    print(line)
f.close()
>>>
del1 1 del2 0 R

del2 1 mov1R 0 R

mov1R 1 mov1R 1 R

mov1R 0 mov2R 0 R

mov2R 1 mov2R 1 R

mov2R 0 mov1L 1 L

mov1L 1 mov1L 1 L

mov1L 0 mov2L 0 L

mov2L 1 mov2L 1 L

mov2L 0 del1 0 R

打開(kāi)division_by_2.txt剿牺，逐行讀取并輸出。這個(gè)代碼的問(wèn)題有兩個(gè)环壤。一個(gè)是寫(xiě)起來(lái)麻煩晒来，一旦忘記close文件會(huì)出問(wèn)題，有隱患郑现；另一個(gè)是輸出難看湃崩，中間有空行，是因?yàn)閜rint默認(rèn)的end = '\n'懂酱。修改如下：

with open('division_by_2.txt') as f:
    for line in f:
        print(line, end = '')

>>>
del1 1 del2 0 R
del2 1 mov1R 0 R
mov1R 1 mov1R 1 R
mov1R 0 mov2R 0 R
mov2R 1 mov2R 1 R
mov2R 0 mov1L 1 L
mov1L 1 mov1L 1 L
mov1L 0 mov2L 0 L
mov2L 1 mov2L 1 L
mov2L 0 del1 0 R

with ... as ...的文件操作容易編寫(xiě)且不易出錯(cuò)竹习。接下來(lái)進(jìn)一步對(duì)每行讀取的信息進(jìn)行處理，首先要分隔開(kāi)讀到的信息列牺，這樣才有意義整陌，使用split()內(nèi)置函數(shù)。

with open('division_by_2.txt') as f:
    for line in f:
        print(line.split())
>>>
['del1', '1', 'del2', '0', 'R']
['del2', '1', 'mov1R', '0', 'R']
['mov1R', '1', 'mov1R', '1', 'R']
['mov1R', '0', 'mov2R', '0', 'R']
['mov2R', '1', 'mov2R', '1', 'R']
['mov2R', '0', 'mov1L', '1', 'L']
['mov1L', '1', 'mov1L', '1', 'L']
['mov1L', '0', 'mov2L', '0', 'L']
['mov2L', '1', 'mov2L', '1', 'L']
['mov2L', '0', 'del1', '0', 'R']

split(X)是python的內(nèi)置函數(shù)，基本含義是根據(jù)X分割內(nèi)容并輸出到一個(gè)list中泌辫，如果()為空随夸，default是以空格分割內(nèi)容。
然后Martin講了很多基礎(chǔ)的dictionary, assignment, list, tuple的基礎(chǔ)知識(shí)震放，容易查詢(xún)宾毒，在此不贅述。
這樣的輸出結(jié)果不好看殿遂，所以接著把每行中寫(xiě)入list的信息assign給相應(yīng)的變量诈铛，方便處理：

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        print(state_1, state_2)
>>>
del1 del2
del2 mov1R
mov1R mov1R
mov1R mov2R
mov2R mov2R
mov2R mov1L
mov1L mov1L
mov1L mov2L
mov2L mov2L
mov2L del1

然后用dictionary的映射來(lái)表征狀態(tài)和數(shù)字的改變，建立一個(gè)圖靈機(jī)的運(yùn)行機(jī)制：

instructions = {}

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, bit_1] = state_2, bit_2, direction
instructions
>>>
{('del1', '1'): ('del2', '0', 'R'),
 ('del2', '1'): ('mov1R', '0', 'R'),
 ('mov1L', '0'): ('mov2L', '0', 'L'),
 ('mov1L', '1'): ('mov1L', '1', 'L'),
 ('mov1R', '0'): ('mov2R', '0', 'R'),
 ('mov1R', '1'): ('mov1R', '1', 'R'),
 ('mov2L', '0'): ('del1', '0', 'R'),
 ('mov2L', '1'): ('mov2L', '1', 'L'),
 ('mov2R', '0'): ('mov1L', '1', 'L'),
 ('mov2R', '1'): ('mov2R', '1', 'R')}

字典的輸出不好看墨礁，用箭頭來(lái)優(yōu)化輸出內(nèi)容：

instructions = {}

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, bit_1] = state_2, bit_2, direction
    for key in instructions:
        print(key, "-->", instructions[key])
>>>
('del1', '1') --> ('del2', '0', 'R')
('del2', '1') --> ('mov1R', '0', 'R')
('mov1R', '1') --> ('mov1R', '1', 'R')
('mov1R', '0') --> ('mov2R', '0', 'R')
('mov2R', '1') --> ('mov2R', '1', 'R')
('mov2R', '0') --> ('mov1L', '1', 'L')
('mov1L', '1') --> ('mov1L', '1', 'L')
('mov1L', '0') --> ('mov2L', '0', 'L')
('mov2L', '1') --> ('mov2L', '1', 'L')
('mov2L', '0') --> ('del1', '0', 'R')

完成圖靈機(jī)的基本操作規(guī)范后幢竹，嘗試模擬圖靈機(jī)的”01“圖形界面：

instructions = {}

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, bit_1] = state_2, bit_2, direction

tape = [0] * 3 + [1] * 7 + [0] * 6

current_state = 'del1'
current_position = 3
current_bit = tape[current_position]

while (current_state, current_bit) in instructions:
    next_state, new_bit, direction = instructions[current_state, current_bit]
    print(next_state, new_bit, direction)

建立一個(gè)叫tape的list來(lái)模擬”01“圖形界面，并初始化當(dāng)前狀態(tài)是del1恩静，位置是3焕毫，這個(gè)位置上的數(shù)字是1。
然后根據(jù)前文建立的instruction字典的圖靈機(jī)基本操作規(guī)范驶乾，找到并assign三個(gè)變量next_state, new_bit, direction的值邑飒。
接下來(lái)要完成的是同步在模擬”01“圖形界面顯示0和1的變化，也就是在tape的list中改變數(shù)字0和1级乐。為了達(dá)到這個(gè)目的疙咸，先要把dictionary中bit_1和bit_2的type從str改成int，這樣方便運(yùn)算：

instructions = {}

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, int(bit_1)] = state_2, int(bit_2), direction

tape = [0] * 3 + [1] * 7 + [0] * 6

current_state = 'del1'
current_position = 3
current_bit = tape[current_position]

print(tape)
while (current_state, current_bit) in instructions:
    next_state, new_bit, direction = instructions[current_state, current_bit]
    tape[current_position] = new_bit
    current_state = next_state
    if direction == 'R':
        current_position += 1
    else:
        current_position -= 1
    current_bit = tape[current_position]
    print(tape)
>>>
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0]

輸出結(jié)果不好看唇牧，可以通過(guò)寫(xiě)print的函數(shù)來(lái)優(yōu)化輸出方法：

instructions = {}

def print_tape():
    print(' '.join(str(e) for e in tape))
    
def print_state():
    print('  ' * current_position, current_state, sep = '')
    
def print_tape_and_state():
    print_tape()
    print_state()

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, int(bit_1)] = state_2, int(bit_2), direction

tape = [0] * 3 + [1] * 7 + [0] * 6

current_state = 'del1'
current_position = 3
current_bit = tape[current_position]

print_tape_and_state()
while (current_state, current_bit) in instructions:
    next_state, new_bit, direction = instructions[current_state, current_bit]
    tape[current_position] = new_bit
    current_state = next_state
    if direction == 'R':
        current_position += 1
    else:
        current_position -= 1
    current_bit = tape[current_position]
    print_tape_and_state()
>>>
0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0
      del1
0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
        del2
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
          mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
            mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
              mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
                mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
                  mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
                    mov1R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
                      mov2R
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
                    mov1L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
                  mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
                mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
              mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
            mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
          mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
        mov2L
0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0
          del1
0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0
            del2
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
              mov1R
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
                mov1R
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
                  mov1R
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
                    mov1R
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
                      mov2R
0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0
                        mov2R
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
                      mov1L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
                    mov1L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
                  mov2L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
                mov2L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
              mov2L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
            mov2L
0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0
              del1
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0
                del2
0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0
                  mov1R
0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0
                    mov1R
0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0
                      mov2R
0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0
                        mov2R
0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0
                          mov2R
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                        mov1L
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                      mov1L
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                    mov1L
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                  mov2L
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                mov2L
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0
                  del1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
                    del2

使用join()內(nèi)置函數(shù)把每一行的list用空格連接起來(lái)罕扎，然后在下一行更換state的位置把state輸出。
轉(zhuǎn)換state和bit的if條件判斷看起來(lái)很難看丐重，繼續(xù)優(yōu)化：

instructions = {}

def print_tape():
    print(' '.join(str(e) for e in tape))
    
def print_state():
    print('  ' * current_position, current_state, sep = '')
    
def print_tape_and_state():
    print_tape()
    print_state()

with open('division_by_2.txt') as f:
    for line in f:
        state_1, bit_1, state_2, bit_2, direction = line.split()
        instructions[state_1, int(bit_1)] = state_2, int(bit_2), direction

tape = [0] * 3 + [1] * 7 + [0] * 6

current_state = 'del1'
current_position = 3
current_bit = tape[current_position]

print_tape_and_state()
while (current_state, current_bit) in instructions:
    next_state, new_bit, direction = instructions[current_state, current_bit]
    tape[current_position] = new_bit
    current_state = next_state
    current_position += (direction == 'R') * 2 - 1
    #如果direction是'R'，那么這個(gè)boolean結(jié)果是1杆查，所以現(xiàn)在的位置就+1扮惦；
    #如果direction不是'R'，那么這個(gè)boolean結(jié)果是0亲桦，所以現(xiàn)在的位置就-1崖蜜。
    current_bit = tape[current_position]
    print_tape_and_state()
>>>
輸出結(jié)果和上面的一樣

2.3.2 python網(wǎng)絡(luò)爬取處理world bank數(shù)據(jù)

python3 worldbank.py運(yùn)行課程材料里的網(wǎng)絡(luò)爬蟲(chóng)程序。如果報(bào)錯(cuò)客峭，可能是缺少bs4和openpyxl的安裝包豫领，使用前文提到的pip3方法安裝。
因?yàn)榕赖降臄?shù)據(jù)格式是' $123.67 million '之類(lèi)的舔琅，在處理數(shù)據(jù)前要先把這樣的string轉(zhuǎn)換成真正的number等恐。

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

s = '   $123.67 million '
units['million']
>>>
1000000

思路和python模擬圖靈機(jī)是一樣的，創(chuàng)建一個(gè)叫做units的dictionary建立string（million, billion, etc.）和units（10**6, 10**9）之間的映射關(guān)系。
接著應(yīng)用建立的units機(jī)制處理爬下來(lái)的string類(lèi)型的數(shù)據(jù)：

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

s = '   $123.67 million '

for unit in units:
    if unit in s:
        s = s.rstrip(unit)
print(s)
>>>
   $123.67 million 

使用內(nèi)置函數(shù)rstrip(unit)來(lái)去除爬取的string中的unit文字（比如课蔬，million, billion等在units字典中的內(nèi)容）囱稽。
運(yùn)行發(fā)現(xiàn)出錯(cuò)，沒(méi)能實(shí)現(xiàn)目標(biāo)二跋，原因是unit前面有空格战惊，繼續(xù)改進(jìn)：

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

s = '   $123.67 million '

for unit in units:
    if unit in s:
        s = s.strip().rstrip(unit)
print(s)
>>>
$123.67 

這樣完成去掉unit的工作，再去掉$符號(hào)：

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

s = '   $123.67 million '

for unit in units:
    if unit in s:
        s = s.strip().rstrip(unit).lstrip('$')
print(s)
>>>
123.67

用內(nèi)置函數(shù)lstrip('$')從左邊去掉了$符號(hào)扎即，但輸出結(jié)果中在123.67后面還有空格殘存吞获，所以繼續(xù)優(yōu)化程序：

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

# thousand/million/billion
s = '   $123.67 million '

for unit in units:
    if unit in s:
        x = float(s.strip().rstrip(unit).lstrip('$')) * units[unit]
print(x)
>>>
123.67

然后把去掉unit的數(shù)字修改為真正的數(shù)字，比如123.67應(yīng)該是123.67*(10**6)

units = {'thousand': 10**3, 'million': 10**6, 'billion': 10**9}

# thousand/million/billion
s = '   $123.67 million '

for unit in units:
    if unit in s:
        x = int(float(s.strip().rstrip(unit).lstrip('$')) * units[unit])
print(x)
>>>
123670000

為了把爬取下來(lái)的數(shù)字放到表格中谚鄙，還需要知道放入的行號(hào)各拷，所以使用內(nèi)置函數(shù)enumerate()來(lái)同時(shí)存儲(chǔ)行號(hào)和數(shù)字：

L = [10, 23, 67, 98]
for number, value in enumerate(L, 2):
    print(number, value)
>>>
2 10
3 23
4 67
5 98

從第二行開(kāi)始存儲(chǔ)爬取的數(shù)據(jù)。

往期回顧
COMP9021 Principles of Programming WEEK1 Optional