計(jì)算思維的基礎(chǔ)知識-資料下載頁
2025-04-29 07:55本頁面
【正文】 使用。 排序算法 10 100 1K 10K 100K 1M 插入排序 56 5145 515621 冒泡排序 61 8174 549432 選擇排序 47 4717 478694 快速排序 39 歸并排序 70 基數(shù)排序 117 哈希排序 61 計(jì)算思維 基礎(chǔ)知識 39/45 二、漢諾塔問題 計(jì)算學(xué)科的典型問題 印度古老傳說 ：在世界中心貝拿勒斯的圣廟里，一塊黃銅板上插著三根寶石針 A、 B和 C。印度教的主神梵天在創(chuàng)造世界時，在其中一根針上從下到上地穿好了由大到小的 64片金片，這就是所謂的漢諾塔問題。 不論白天黑夜，總有一個僧侶在按下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有金片移到另外一根針上時，世界將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。 計(jì)算思維 基礎(chǔ)知識 40/45 不管這個傳說的可信度有多大，如果僅考慮把 64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢？這里需要使用 遞歸算法 。 假設(shè)有 n片，移動次數(shù)是 f(n) 顯然 f(1)=1， f(2)=3， f(3)=7，且 f(k+1)=2*f(k)+1 不難證明 f(n)=2^n1 當(dāng) n=64時， f(64)=2^641=18446744073709551615次 如果每秒鐘移動一次，共需多長時間呢？ 一年有 31536000秒，則 18446744073709551615/31536000=5849億年 計(jì)算學(xué)科的典型問題 計(jì)算思維 基礎(chǔ)知識 41/45 三、國王的婚姻 計(jì)算學(xué)科的典型問題 國王：艾述 (喜愛數(shù)學(xué) ) 宰相：孔喚石 (數(shù)學(xué)家 ) 公主：秋碧貞楠 (鄰國 ) 公主：求出 48770428644836899的一個真因子 國王： 2,3,4,┅,30000 多數(shù)據(jù) (一天 ) 公主：驗(yàn)證一下， 223092871 宰相：將全國百姓按自然數(shù)的順序編號，百姓用自己的編號去除公主的數(shù)，誰除盡來領(lǐng)賞。 童話說明 ：①國王本人計(jì)算 (串行算法，時間復(fù)雜性 ) ② 全國百姓計(jì)算 (并行算法，空間復(fù)雜性 ) 計(jì)算思維 基礎(chǔ)知識 42/45 四、旅行商問題 旅行商問題 (TSP)的描述 ：一位商人去 n個城市推銷貨物，所有城市走一遍后，再回到起點(diǎn)，問如何事先確定好一條最短的路線，使其旅行的費(fèi)用最少。 計(jì)算學(xué)科的典型問題 路徑 ABCDA的總距離是： 4+2+4+2=12 路徑 ABDCA的總距離是： 4+6+4+6=20 路徑 ACBDA的總距離是： 6+2+6+2=16 路徑 ACDBA的總距離是： 6+4+6+4=20 路徑 ADCBA的總距離是： 2+4+2+4=12 路徑 ADBCA的總距離是： 2+6+2+6=16 計(jì)算思維 基礎(chǔ)知識 43/45 城市數(shù)目為 4時，組合路徑數(shù)為 6 城市數(shù)目為 n時，組合路徑數(shù)為 (n1)! 當(dāng)城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急劇增長，以至到達(dá)無法計(jì)算的地步，這就是所謂的組合爆炸問題。 計(jì)算學(xué)科的典型問題 假如城市的數(shù)目增為 20個，組合路徑數(shù)則為 (201)！ ≈ 1017 若計(jì)算機(jī)以每秒檢索 1000萬條路線的速度計(jì)算，也需要花上 386年的時間。 計(jì)算思維 基礎(chǔ)知識 44/45 本章小結(jié) ? 科學(xué)的定義和種類 理論科學(xué) 、 實(shí)驗(yàn)科學(xué) 、 計(jì)算科學(xué) ? 計(jì)算科學(xué)和計(jì)算學(xué)科 (不同視角 ) 計(jì)算機(jī)科學(xué)知識體 (14個知識領(lǐng)域 ) ? 計(jì)算機(jī)科學(xué)與計(jì)算機(jī)學(xué)科 (不同視角 ) 計(jì)算機(jī)科學(xué)與技術(shù)一級學(xué)科、二級學(xué)科 ? 思維的定義、組成、特征和類型 ? 科學(xué)思維的定義和分類 理論思維 、 實(shí)驗(yàn)思維 、 計(jì)算思維 計(jì)算思維 基礎(chǔ)知識 45/45 ? 計(jì)算思維的定義、詳細(xì)描述、特征和本質(zhì) ? 計(jì)算思維與計(jì)算機(jī)的關(guān)系 ? 計(jì)算思維的應(yīng)用領(lǐng)域 （生物學(xué)、腦科學(xué)、化學(xué)、經(jīng)濟(jì)學(xué)、藝術(shù)、工程學(xué)、社會科學(xué)等） ? 計(jì)算學(xué)科的典型問題 （通過排序問題、漢諾塔問題、國王的婚姻、旅行商問題來說明 人所固有的能力與局限性、計(jì)算機(jī)的計(jì)算能力與局限性，以及問題到底有多復(fù)雜） 本章小結(jié)
公司管理相關(guān)推薦
鄂ICP備17016276號-1