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