計算機(jī)文化與計算思維

1、1第一章第一章 計算機(jī)文化與計算思維計算機(jī)文化與計算思維1.1 引言引言 1.2 計算機(jī)計算機(jī)的誕生和發(fā)展的誕生和發(fā)展 1.3 計算思維基礎(chǔ)計算思維基礎(chǔ)2 1.1 1.1 引言引言 人類為什么要發(fā)明計算機(jī)？ 人的計算速度很低 祖沖之計算祖沖之計算至小數(shù)點(diǎn)后至小數(shù)點(diǎn)后7位數(shù)用了位數(shù)用了15年年 計算計算3030的行列式需要幾個人年的行列式需要幾個人年 中國第一棵原子彈研制時，數(shù)百位科學(xué)家在大禮堂打算盤中國第一棵原子彈研制時，數(shù)百位科學(xué)家在大禮堂打算盤 早期的計算工具 算算 籌籌 春秋戰(zhàn)國時期春秋戰(zhàn)國時期世界上最早的計算工具世界上最早的計算工具 算算 盤盤 中國唐代中國唐代 第一種手動式計數(shù)器第一

2、種手動式計數(shù)器 沿有至今沿有至今 計算尺計算尺 1622年年 手動式，上世紀(jì)手動式，上世紀(jì)70年代被計算器取代年代被計算器取代可進(jìn)行加、減、乘、除、指數(shù)、三角函數(shù)可進(jìn)行加、減、乘、除、指數(shù)、三角函數(shù) 加法器加法器 1642年年 機(jī)械式，只能做加法機(jī)械式，只能做加法1642 Blaise Pascal1822 1822 差分機(jī)差分機(jī)1833 分析機(jī)分析機(jī)電子計算機(jī)時代電子計算機(jī)時代計算機(jī)發(fā)展史計算機(jī)發(fā)展史 人類追求的計算工具人類追求的計算工具算籌算籌中國最早的計算工具中國最早的計算工具 算籌是我國古代的計算籌是我國古代的計算工具?；I即小竹算工具?；I即小竹棍或小木棍棍或小木棍也有用骨也有用骨或金屬

3、材料制成的或金屬材料制成的，古人用它來進(jìn)行計算，古人用它來進(jìn)行計算，稱為算籌。稱為算籌。計算機(jī)的起源計算機(jī)的起源計算機(jī)發(fā)展史計算機(jī)發(fā)展史公元公元600年左右，我年左右，我國出現(xiàn)新的計算工國出現(xiàn)新的計算工具具算盤算盤。計算機(jī)發(fā)展史計算機(jī)發(fā)展史機(jī)械式計算機(jī)機(jī)械式計算機(jī)Blaise Pascal帕斯卡帕斯卡 計算機(jī)發(fā)展史計算機(jī)發(fā)展史1642年，年僅年，年僅19歲的法國偉大歲的法國偉大科學(xué)家科學(xué)家帕斯卡帕斯卡引用算盤的原理引用算盤的原理，發(fā)明了第一部機(jī)械式計算器，發(fā)明了第一部機(jī)械式計算器，在他的計算器中有一些互相，在他的計算器中有一些互相聯(lián)鎖的齒輪，一個轉(zhuǎn)過十位的聯(lián)鎖的齒輪，一個轉(zhuǎn)過十位的齒輪會使另一

4、個齒輪轉(zhuǎn)過一位齒輪會使另一個齒輪轉(zhuǎn)過一位，人們可以像撥電話號碼盤那，人們可以像撥電話號碼盤那樣，把數(shù)字撥進(jìn)去，計算結(jié)果樣，把數(shù)字撥進(jìn)去，計算結(jié)果就會出現(xiàn)在另一個窗口中，但就會出現(xiàn)在另一個窗口中，但是是只能做加減計算只能做加減計算。18121812年差分機(jī)年差分機(jī) 查爾斯查爾斯. .巴貝奇巴貝奇 1834年設(shè)計的分析機(jī)年設(shè)計的分析機(jī) 由許多輪子組成的保存數(shù)據(jù)的存儲庫；由許多輪子組成的保存數(shù)據(jù)的存儲庫；運(yùn)算裝置；能對操作順序進(jìn)行控制，并選運(yùn)算裝置；能對操作順序進(jìn)行控制，并選擇所需處理的數(shù)據(jù)以及輸出結(jié)果的裝置。擇所需處理的數(shù)據(jù)以及輸出結(jié)果的裝置。主要用于計算多項(xiàng)式，運(yùn)算精度達(dá)到小數(shù)主要用于計算多項(xiàng)式

5、，運(yùn)算精度達(dá)到小數(shù)點(diǎn)后點(diǎn)后6 6位位巴貝奇的分析機(jī)巴貝奇的分析機(jī)是歷史上最早的專是歷史上最早的專用計算機(jī)和通用計用計算機(jī)和通用計算機(jī)的完整構(gòu)思算機(jī)的完整構(gòu)思.ENIAC：長長30.4830.48米，寬米，寬1 1米，占米，占地面積地面積170170平方米，平方米，3030個操作臺，個操作臺，約相當(dāng)于約相當(dāng)于1010件普通房間的大小，件普通房間的大小，重達(dá)重達(dá)3030噸，耗電量噸，耗電量150150千瓦，造千瓦，造價價4848萬美元。它使用萬美元。它使用1800018000個電個電子管，子管，7000070000個電阻，個電阻，1000010000個電個電容，容，15001500個繼電器，個繼電

6、器，60006000多個開多個開關(guān)，每秒執(zhí)行關(guān)，每秒執(zhí)行50005000次加法或次加法或400400次乘法，是繼電器計算機(jī)的次乘法，是繼電器計算機(jī)的10001000倍、倍、手工計算的手工計算的2020萬倍萬倍。 計算機(jī)發(fā)展史計算機(jī)發(fā)展史 第一臺電子計算機(jī)（第一臺電子計算機(jī)（ENIAC）9 1.1 1.1 引言引言 計算器計算器 1673年年德國德國Gottfried Leibniz，機(jī)械式，機(jī)械式 可進(jìn)行加、減、乘可進(jìn)行加、減、乘、除和開方、除和開方 差分機(jī)和分析機(jī)差分機(jī)和分析機(jī) 查爾斯查爾斯. .巴貝奇巴貝奇 1812年差分機(jī)年差分機(jī) 1834年分析機(jī)年分析機(jī) 分析機(jī)：體現(xiàn)了現(xiàn)代電子計算機(jī)的

7、結(jié)構(gòu)、設(shè)計思想分析機(jī)：體現(xiàn)了現(xiàn)代電子計算機(jī)的結(jié)構(gòu)、設(shè)計思想 被稱為現(xiàn)代通用計算機(jī)的雛形被稱為現(xiàn)代通用計算機(jī)的雛形10（1）M的狀態(tài)：接受狀態(tài)、進(jìn)位狀態(tài)。初始時處于進(jìn)位狀態(tài)。的狀態(tài)：接受狀態(tài)、進(jìn)位狀態(tài)。初始時處于進(jìn)位狀態(tài)。（2）從右向左掃描紙帶。）從右向左掃描紙帶。 進(jìn)位狀態(tài)：讀到進(jìn)位狀態(tài)：讀到0或空白，則改寫或空白，則改寫1，進(jìn)入接受狀態(tài)，立即停機(jī)；，進(jìn)入接受狀態(tài)，立即停機(jī)； 讀到讀到1，則改寫為，則改寫為0，狀態(tài)保住不變，讀寫頭左移，狀態(tài)保住不變，讀寫頭左移。1.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 計算機(jī)的誕生 圖靈機(jī)、圖靈機(jī)、ENIAC和馮和馮諾依曼體系結(jié)構(gòu)在理論上、工作原理

8、、體系結(jié)諾依曼體系結(jié)構(gòu)在理論上、工作原理、體系結(jié)構(gòu)上奠定現(xiàn)代電子計算機(jī)的基礎(chǔ)構(gòu)上奠定現(xiàn)代電子計算機(jī)的基礎(chǔ) 圖靈機(jī)圖靈機(jī)(Turing machine，TM ) 阿蘭阿蘭圖靈（圖靈（Alan Mathison Turing ，19121954） 解決問題；解決問題；什么是計算？什么是可計算性？什么是計算？什么是可計算性？ 組成：計算組成：計算X+1的圖靈機(jī)的圖靈機(jī)M紙帶紙帶 讀寫頭讀寫頭 111.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 圖靈機(jī)的能力圖靈機(jī)的能力=高級程序設(shè)計語言高級程序設(shè)計語言=現(xiàn)代通用計算機(jī)現(xiàn)代通用計算機(jī) 邱奇、圖靈和哥德爾斷言：邱奇、圖靈和哥德爾斷言： 一切直覺上能

9、行可計算的函數(shù)都可用圖靈機(jī)計算，反之亦然一切直覺上能行可計算的函數(shù)都可用圖靈機(jī)計算，反之亦然邱奇邱奇圖靈論題圖靈論題 世界上的問題 可計算的：圖靈機(jī)可計算的就是可計算的 不可計算的 圖靈的貢獻(xiàn) 圖靈機(jī)模型：解決了可計算問題 計算機(jī)的理論問題圖靈測試：回答了什么樣的機(jī)器具有智能 人工智能的理論基礎(chǔ) 美國計算機(jī)學(xué)會美國計算機(jī)學(xué)會ACM于于1966年創(chuàng)立了年創(chuàng)立了“圖靈獎圖靈獎” 計算機(jī)科學(xué)之父計算機(jī)科學(xué)之父 人工智能之父人工智能之父121.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 ENIAC（電子數(shù)字積分計算機(jī)）（電子數(shù)字積分計算機(jī)） 1946.21955.10 賓州大學(xué)賓州大學(xué):每秒每秒

10、5千次加減運(yùn)算千次加減運(yùn)算:沒有存儲器沒有存儲器:采用十進(jìn)制采用十進(jìn)制第一款商用計算機(jī)：第一款商用計算機(jī)：UNIVAL1947年，莫奇萊和?？颂啬辏嫒R和?？颂貎H表明電子計算機(jī)時代的到來僅表明電子計算機(jī)時代的到來 131.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 馮馮諾依曼體系結(jié)構(gòu)計算機(jī)諾依曼體系結(jié)構(gòu)計算機(jī) 人人類第二臺計算機(jī)；類第二臺計算機(jī)；EDVAC（離散變量自動電子計算機(jī)）（離散變量自動電子計算機(jī)） 1945年年 馮馮諾依曼參與研制并且發(fā)表：諾依曼參與研制并且發(fā)表：關(guān)于關(guān)于 EDVAC的報告草案的報告草案:采用二進(jìn)制采用二進(jìn)制 :存儲程序：存儲程序：程序和數(shù)據(jù)一起存儲在內(nèi)存中程

11、序和數(shù)據(jù)一起存儲在內(nèi)存中 :五個部分：五個部分：運(yùn)算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備運(yùn)算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備 奠定了現(xiàn)代計算機(jī)體系結(jié)構(gòu)和工作原理奠定了現(xiàn)代計算機(jī)體系結(jié)構(gòu)和工作原理迄今為止的計算機(jī)都采用這種思想，稱為馮迄今為止的計算機(jī)都采用這種思想，稱為馮諾依曼計算機(jī)諾依曼計算機(jī) 14 計算機(jī)的分代時代年份器件運(yùn)算速度軟件應(yīng)用一 46-58電子管每秒幾千次 機(jī)器語言匯編語言 科學(xué)計算軍事領(lǐng)域二58-64晶體管每秒幾十萬次 高級語言數(shù)據(jù)處理工業(yè)控制 三64-70集成電路每秒幾百萬次 操作系統(tǒng)文字處理圖形處理四71年迄今大規(guī)模集成電路達(dá)到每秒億億次 數(shù)據(jù)庫、網(wǎng)絡(luò)等各個領(lǐng)域電子

12、管電子管晶體管晶體管集成電路集成電路大規(guī)模集成電路大規(guī)模集成電路1.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展15 發(fā)展趨勢：微型化、巨型化、網(wǎng)絡(luò)化和智能化發(fā)展趨勢：微型化、巨型化、網(wǎng)絡(luò)化和智能化 未來新型計算機(jī)未來新型計算機(jī) 光計算機(jī)光計算機(jī) 利用光子取代電子進(jìn)行數(shù)據(jù)運(yùn)算、傳輸和存儲利用光子取代電子進(jìn)行數(shù)據(jù)運(yùn)算、傳輸和存儲 不同波長的表示不同的數(shù)據(jù)不同波長的表示不同的數(shù)據(jù) 優(yōu)點(diǎn)：超高速優(yōu)點(diǎn)：超高速 缺點(diǎn)：體積龐大缺點(diǎn)：體積龐大 生物計算機(jī)（分子計算機(jī)）生物計算機(jī)（分子計算機(jī)） 2 02 0 世 紀(jì)世 紀(jì) 8 08 0 年 代 中 期 開 始 研 制年 代 中 期 開 始 研 制 采用了

13、生物芯片采用了生物芯片 量子計算機(jī)量子計算機(jī) 利用處于多現(xiàn)實(shí)態(tài)下的原子進(jìn)行運(yùn)算的計算機(jī)，利用處于多現(xiàn)實(shí)態(tài)下的原子進(jìn)行運(yùn)算的計算機(jī)， 這種多現(xiàn)實(shí)態(tài)是量子力學(xué)的標(biāo)志。這種多現(xiàn)實(shí)態(tài)是量子力學(xué)的標(biāo)志。 1.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展16 計算機(jī)的分類 按綜合性能按綜合性能指標(biāo)分類指標(biāo)分類高性能計算機(jī)（高性能計算機(jī)（巨型機(jī)或大型機(jī)巨型機(jī)或大型機(jī)）：）： 速度最快、處理能力最強(qiáng)、速度最快、處理能力最強(qiáng)、 最快：最快：Titan 每秒每秒2億億次浮點(diǎn)運(yùn)算億億次浮點(diǎn)運(yùn)算 中國：天河中國：天河1A 每秒每秒4.70千萬億次浮點(diǎn)運(yùn)算千萬億次浮點(diǎn)運(yùn)算 第第8 工作站工作站：介于介于PCPC與小

14、型機(jī)之間高檔微機(jī)系統(tǒng)與小型機(jī)之間高檔微機(jī)系統(tǒng) 高分辨率、大容量內(nèi)外存，圖形功能較強(qiáng)高分辨率、大容量內(nèi)外存，圖形功能較強(qiáng)微型計算機(jī)微型計算機(jī)： 桌面型計算機(jī)、筆記本電腦、平板電腦、移動設(shè)備桌面型計算機(jī)、筆記本電腦、平板電腦、移動設(shè)備 服務(wù)器：網(wǎng)絡(luò)環(huán)境中對外提供服務(wù)的計算機(jī)系統(tǒng)服務(wù)器：網(wǎng)絡(luò)環(huán)境中對外提供服務(wù)的計算機(jī)系統(tǒng)按用途分類按用途分類通用機(jī)通用機(jī)專用機(jī)專用機(jī)1.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展嵌入式計算機(jī)：數(shù)量超過嵌入式計算機(jī)：數(shù)量超過PCPC 171.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 計算機(jī)的應(yīng)用類型1. 科學(xué)計算科學(xué)計算2. 數(shù)據(jù)處理數(shù)據(jù)處理3. 電子商務(wù)電

15、子商務(wù) B2B 阿里巴巴阿里巴巴 B2C 京東商城京東商城 C2C 淘寶網(wǎng)淘寶網(wǎng)4. 過程控制過程控制5. CAD/CAM/CIMS6. 多媒體技術(shù)多媒體技術(shù) 7. .人工智能人工智能卡斯帕羅夫?qū)摹吧钏{(lán)” 181.2 1.2 計算機(jī)的誕生和發(fā)展計算機(jī)的誕生和發(fā)展 計算機(jī)文化 物質(zhì)文化物質(zhì)文化 計算機(jī)的軟、硬件設(shè)備以及使用方法計算機(jī)的軟、硬件設(shè)備以及使用方法 非物質(zhì)文化非物質(zhì)文化 計算機(jī)學(xué)科對自然科學(xué)和社會科學(xué)等的廣泛滲透，計算機(jī)學(xué)科對自然科學(xué)和社會科學(xué)等的廣泛滲透， 創(chuàng)造和形成了新的科學(xué)思想、科學(xué)方法、科學(xué)精神、價值標(biāo)準(zhǔn)等創(chuàng)造和形成了新的科學(xué)思想、科學(xué)方法、科學(xué)精神、價值標(biāo)準(zhǔn)等 計算機(jī)應(yīng)用改

16、變了傳統(tǒng)社會，形成了網(wǎng)絡(luò)社會等虛擬的社會形態(tài)計算機(jī)應(yīng)用改變了傳統(tǒng)社會，形成了網(wǎng)絡(luò)社會等虛擬的社會形態(tài) 產(chǎn)生了相應(yīng)的語言、風(fēng)俗、道德、法律等產(chǎn)生了相應(yīng)的語言、風(fēng)俗、道德、法律等 最重要的是計算機(jī)網(wǎng)絡(luò)文化最重要的是計算機(jī)網(wǎng)絡(luò)文化 19示例示例1 1： 計算計算f(x)是是a, b上的積分上的積分 數(shù)學(xué)方法數(shù)學(xué)方法 牛頓牛頓萊布尼茲：萊布尼茲： f(x) F(x) 計算思維計算思維 黎曼積分：對黎曼積分：對a, b進(jìn)行進(jìn)行n等分等分 計算小矩形面積計算小矩形面積 累加累加 三大科學(xué)思維三大科學(xué)思維計算思維：計算思維：運(yùn)用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行運(yùn)用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解問題求解、系統(tǒng)設(shè)計系

17、統(tǒng)設(shè)計、 以及以及人類行為理解人類行為理解等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動 1.3 1.3 計算思維計算思維理論思維（推理思維）理論思維（推理思維） 特征：以推理和演繹為特征特征：以推理和演繹為特征 代表學(xué)科：數(shù)學(xué)代表學(xué)科：數(shù)學(xué) 實(shí)驗(yàn)思維（實(shí)證思維）實(shí)驗(yàn)思維（實(shí)證思維） 特征：觀察和總結(jié)自然規(guī)律特征：觀察和總結(jié)自然規(guī)律 代表學(xué)科：物理學(xué)代表學(xué)科：物理學(xué) 計算思維（構(gòu)造思維）計算思維（構(gòu)造思維） 特征：設(shè)計和構(gòu)造特征：設(shè)計和構(gòu)造 代表學(xué)科：計算機(jī)科學(xué)代表學(xué)科：計算機(jī)科學(xué) baxF| )(20 迭代法迭代法 迭代過程：迭代過程：1!=1 2!=1!*2

18、3!=2!*3 n!=(n-1)!*n 程序：程序： s=1; for(i=1;i=n;i+) s=s*i; 經(jīng)典迭代：牛頓迭代法經(jīng)典迭代：牛頓迭代法 J20研制過程就是迭代過程：研制過程就是迭代過程： 原型機(jī)原型機(jī)0 原型機(jī)原型機(jī)1 原型機(jī)原型機(jī)2 原型機(jī)原型機(jī)3示例示例2： 計算計算n的階乘的階乘f(n)=n!1.3 1.3 計算思維計算思維 遞歸遞歸 分分解解問題問題小問題小問題n!(n-1)!問題問題分分解解小問題小問題更小更小問題問題最小最小問題問題分分解解分分解解不能再分解不能再分解n!(n-1)!(n-2)!1! int fac(int n) if(n=1) return(1);

19、 else return(fac(n-1)*n); void main() int y; y=f(4) couty;21示例示例1.3 哥尼斯堡七橋問題哥尼斯堡七橋問題 18世紀(jì)經(jīng)典數(shù)學(xué)問題世紀(jì)經(jīng)典數(shù)學(xué)問題 在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點(diǎn)？座橋一次，再回到起點(diǎn)？1計算思維的本質(zhì)：抽象和自動化計算思維的本質(zhì)：抽象和自動化 抽象：抽象：完全超越物理的時空觀，并完全用符號來

20、表示完全超越物理的時空觀，并完全用符號來表示 數(shù)學(xué)抽象是一種特例數(shù)學(xué)抽象是一種特例1.3 1.3 計算思維計算思維 哥尼斯堡七橋問題哥尼斯堡七橋問題 哥尼斯堡七橋問題的抽象哥尼斯堡七橋問題的抽象 自動化：自動化：機(jī)械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽像機(jī)械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽像 222計算思維的特征計算思維的特征 是屬于人的思維方式，不是計算機(jī)的思維方式是屬于人的思維方式，不是計算機(jī)的思維方式 遞歸、迭代、黎曼積分早已提出，是人類賦予計算機(jī)遞歸、迭代、黎曼積分早已提出，是人類賦予計算機(jī) 可以由人執(zhí)行，也可以由計算機(jī)執(zhí)行可以由人執(zhí)行，也可以由計算機(jī)執(zhí)行 是思想，不是人造物是思想

21、，不是人造物 是概念化，不是程序化是概念化，不是程序化 3計算思維的基本問題計算思維的基本問題 可計算性可計算性 一個問題是可計算的是指可以使用計算機(jī)在有限步驟內(nèi)解決一個問題是可計算的是指可以使用計算機(jī)在有限步驟內(nèi)解決 邱奇圖靈論題：圖靈機(jī)可以計算的就是可計算的邱奇圖靈論題：圖靈機(jī)可以計算的就是可計算的 計算復(fù)雜性計算復(fù)雜性 時間復(fù)雜性和空間復(fù)雜性時間復(fù)雜性和空間復(fù)雜性 1.3 1.3 計算思維計算思維23示例示例4 矩陣相乘：矩陣相乘：Cnn=AnnBnn1.3 1.3 計算思維計算思維 計算計算cij需要需要n次乘法和次乘法和n-1次加法次加法 c中有中有n2個元素，故個元素，故c需要需要

22、n3次乘法和次乘法和n2*(n-1)次加法次加法示示例例5 漢諾塔問題漢諾塔問題 大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上按照大小順序摞著從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。只能移動一個圓盤。 241.3 1.3 計算思維計算思維漢諾塔問題分析漢諾塔

23、問題分析 假設(shè)有假設(shè)有n黃金圓盤，移動次數(shù)是黃金圓盤，移動次數(shù)是f(n) 有有f(1)=1，f(2)=3，f(3)=7，f(k+1）=2*f(k)+1 故故f(n)=2n-1，時間復(fù)雜性記作，時間復(fù)雜性記作O(2n) f(64) = 264-1=18446744073709551615 假如每秒鐘移動一次，一個假如每秒鐘移動一次，一個365天，則約需要天，則約需要584942417355年，即年，即5849億億年年 而地球的壽命才而地球的壽命才45億年。億年。 假使用計算機(jī)進(jìn)行每秒假使用計算機(jī)進(jìn)行每秒1億次的移動，也需要億次的移動，也需要5849年。年。 時間復(fù)雜性：時間復(fù)雜性：O(1) O(logn) O(n) O(nlogn) O(n2）O(n3) O(nk) O(2n) 當(dāng)當(dāng)n值稍大時，值稍大時，O(2n)的問題就無法計算了的問題就無法計算了 254圖靈測試圖靈測試 機(jī)器能有智能嗎？換一句話來，通過什么樣的測試機(jī)器才能稱擁有智能？機(jī)器能有智能嗎？換一句話來，通過什么樣的測試機(jī)器才能稱擁有智能？ 1.3 1.3 計算思維計算思維無法判斷對方是人還是計算機(jī)，那么就可以認(rèn)為計算機(jī)具有同人相當(dāng)?shù)闹橇o法判斷對方是人還是計算機(jī)，那么就可以認(rèn)為計算機(jī)具有同人相當(dāng)?shù)闹橇?測試場景測試場景 265計算思維基本方