1、計算思維陶先平南京大學計算機軟件研究所找假幣-何謂“計算思維”？給你70個外觀完全一樣的金幣,但是你知道其中有一個是假幣,其重量比真幣輕。給你一架沒有砝碼的天平，你可以在天平兩邊擺任意多個金幣，比較他們的輕重。請設計一種方法，通過若干次稱量，確定哪一個是假幣。第一個解法先將70個金幣平均分兩份，放到天平兩邊。假幣必在輕的那一側的35個中。將那35個加上另一側中任意一個，再平分稱量。將輕的一側的18個平分再稱量。將輕的一側的9個加另外任意一個再平分稱量。將輕的一側的5個加另外任意一個再平分稱量。將輕的一側的3個加另外任意一個再平分稱量。將輕的一側的2個分別放到天平兩邊，輕的是假幣。完成總共稱7次

2、但是，你應該問自己：還能更好嗎？第一個解法稍稍改進先將70個金幣平均分兩份，放到天平兩邊。假幣必在輕的那一側的35個中。將那35個中任意一個放一旁，其余再平分稱量，每邊17個。若相等則旁邊的是假幣，否則將輕的一側的17個中任意一個放旁邊，其余的再平分再稱量，每邊8個。若相等則旁邊的是假幣，否則將輕的一側的8個平分再稱量，每邊4個將輕的一側的4個再平分稱量，每邊2個。將輕的一側的2個再平分稱量，每邊個。輕的是假幣。完成總共稱6次但是，你還應該問自己：還能更好嗎？一個更好的辦法1.23:24.461.8:9.1647.54:55.6224.31:32.40.47.49:50.5263.65:66.

3、6855.57:58.6047:4853:5450:51.稱四次！但是，你還應該問自己：這是最好的嗎？我們為什么會這樣思考來找到最快的方法？第一種方案:問題空間： 我們所觀察到的對象 (每個對象的狀態及其變化)第二種方案:幾乎每次壓縮問題空間到一半幾乎每次壓縮問題空間到三分之一如何表達我們的這個思想？寫個程序！Procedure FindIt(n) /從n個硬幣中找出一個較輕的假幣 if n=2 /只有兩個硬幣 天平上翹起的是假幣；程序結束； if n=3 /有三個硬幣 任取兩個放在天平上； 如果平衡，假幣為第三個，否則為翹起的天平端硬幣；程序結束； else /有多于三個硬幣 將硬幣分為幾乎

4、數量相同的三堆n1,n2,n3； /其中必定有兩堆數量相同 稱量其中數量相同的兩堆； /不妨假設n1=n2 如果兩堆不同重 /不妨假設n1堆輕 FindIt(n1); else FindIt(n3); 到此為止，這個問題我們解決了嗎？No！我們還應該至少回答這些問題： 你能證明你的解法是正確的嗎？ 你能證明你的解法是最優的嗎？ 你能證明你的程序沒有錯誤嗎？9/6/2022再一個互動游戲：統計到場人數：0，所有人都站起來，每個人都握有一個數字：11，每兩個人組成一組，將手中數字相加，并記住。其中一人坐下；2，重復第一步，直到教室中只有一人；3，最后一人，大聲報出數字；這個游戲，給了我們什么啟發？

5、1，依然是“壓縮問題空間”：N壓縮到n-1 =n壓縮到n/2三人或者四人或者都是一種可能的選擇，只要一次統計能夠被“簡單”完成2，如果每次分組（兩人組）后，組內的統計、累計都可以在組內完成，那么：我就只需要完成分組、同步和最后數據的收集工作每個小組，可以并行完成組內工作每個小組都是一個小型計算機系統N個人，如果小組規模是m，那么我只需要進行約logmn次的分組、同步工作我是一個管理了多個可并行運行的計算機系統的“并行計算機系統”多核系統是一個典型案例分治法+并行處理：極大提高了問題求解的效率如何表達我們的解題過程呢？假設我們有p+1個處理器(0,p),其中第0號是master，其它是slave

6、Parallel Procedure count(n) if (Im the master) 將n個數據分為p份：n1,n2,np for (i=1 to p step 1) count(ni); for (i=1 to p step 1) receive value from pi; sum = sum+value； elseelse /slaves 接收master給予的數據； for (i=1 to n/p step 1) value= GetValue(i); sum = sum+value； send sum to master;是什么導致了我們的獨特視角？關于計算思維的一些理解計算

7、思維是我們認知計算的過程中積累形成的思考“模式” 計算思維教學需要傳遞計算給我們帶來的可能性以及實現這些可能的基本方法算法是解讀計算思維的最佳載體1，計算思維是我們認知計算過程中積累的思考“模式”思維是一種認知過程計算思維是我們認知計算過程中若干層面的抽象及其實現中“沉淀”下來的一些計算思維：抽象化+自動化： 三個層面的抽象過程及相應的自動化過程如何去“傳遞”抽象化+自動化？2，計算思維教/學需要傳遞/感悟計算給我們帶來的可能性以及實現這些可能的基本方法想以前想不到之事做以前做不到之事做以前做不好之事想以前想不到之事全球脈動(Global Pulse)計劃：聯合國已經推出的新項目，希望利用“大

8、數據”來促進全球經濟發展進行所謂的“情緒分析”，使用軟件來對社交網站和文本消息中的信息作出分析幫助預測某個給定地區的失業率、支出削減或是疾病爆發等現象目標在于利用數字化的早期預警信號來提前指導援助項目，以阻止某個地區重新陷入貧困等困境做以前做不到之事人類基因組計劃HGP計劃計算機科學家遺傳學家生理學家臨床和病理學家結構生物學家細胞生物學家生物化學家做以前做不好之事ERP系統針對物資資源管理（物流）、人力資源管理（人流）、財務資源管理（財流）、信息資源管理（信息流）而開展的集成一體化的企業管理信息技術帶給了我們龐大的處理能力：復雜業務模型、復雜管理要求、復雜合作關系、復雜時空數據類型計算給這個世

9、界帶來的不是這個和那個技術，也不是這個或者那個炫目應用計算帶給我們的是無限的想象空間和強有力的實現手段人有多大膽地有多大產試圖給出計算思維的定義 美國卡內基-梅隆大學教授Jeannette M. Wing(周以真)領導世界上可能是唯一的”計算思維研究中心”, 并大力推動這一概念被認可。以下內容摘自她的文章：Computational Thinking: What and Why? Link Magazine, 2010結束語計算思維看不見，摸不著，但影響著你的決策！計算思維：當你面臨一個要解決的問題時，如果你的第一感覺是去尋找一個數學模型對問題和解進行建模，去嘗試著通過算法來尋找解，并嘗試著思考如何用一個輔助工具開展計算時，計算思維已經在影響你了！有很多的計算過程中沉淀下來的模式，被封裝為計算思維，可以被我們直接使用作業請你為某個型號的電子詞典，設計一個查找單詞的遞歸算法(偽代碼）提示：1，電子詞典已經按照詞典序排好