1、計算思維與語言技能- 在程序設計課中如何權衡陳道蓄南京大學計算機科學與技術系2014年11月29日 鄭州我們經常從教程序設計課的老師口中聽到這樣的話:“我這個課可不是只教一種語言的，我們教的是思想！”我們能說清楚嗎？問題1：什么是思想？問題2：是什么思想？問題3：學生感悟到“思想”了嗎？什么是計算思維？或者我們換一個問法：什么不是？計算機文化：為什么“遇到問題上百度”算不上是計算思維？計算機技術：為什么“了解操作系統的功能與結構”也不應該算是計算思維？怎樣能讓計算機幫我們解題？思維“傳遞”與“載體”“思想”只能傳遞, 不能直接“教”。有效的“傳遞”需要兩個條件：合適的“載體”，適當的“例子”按

2、照上述想法來審視我們目前的程序設計課程載體相對復雜；例子相對簡單基本想法與改革路線基本想法：顯式區分“思維方法”與“編程技能”對不同的目標采用不同的教學方法方法設計基本思路：“思維”靠“悟”；“技能”靠“練”做法：引導學生去“悟”，不依靠特定語言；加大訓練強度，不拘泥于語言成分。基本內容載體1，計算機為什么能解題？2，基本的算法結構3，基本的數據結構4，遞歸及其代價下面提供一些課堂實例片斷計算機問題求解計算機問題求解問題1a:計算機究竟能干什么？問題1b:人究竟是如何解題的？問題1：為什么計算機能幫我們解題？Even More Amazing 0 1 0 1 10 1 0 0 10 1 1 0

3、 10 1 0 1 10 1 0 0 10 1 0 0 10 1 0 1 10 1 0 1 10 0 0 1 1FlippingZeroingTesting(if 1, flipping)問題2：我們可以讓計算機“間接地”執行什么操作？你試試讓計算機比較兩個1-bit二進制數是否相等，只用前面提到的運算，如果需要，你可以使用輔助的bits.xyeqEquality test (x,y)zero eq;flip eq;/* equality ontest x flip eq;test y flip eq;/* equality on only turn twiceIf x=y eq=1Other

4、wise eq=0你能將這個操作擴展到, 比如, 32位內的整數嗎?稍微增加一點操作計算兩個1-bit二進制數的和xyz1z0tx+yadd (x,y)1. zero z0; 2. zero z1;3. equality test(x,y);4. test eq goto 75. flip z0;6. exit;7. zero t;8. flip t; 9. equality test(x, t);10. test eq flip z1; 如果只允許原來三個基本操作, 能完成這個任務嗎?多層次抽象 用一位的加法“間接操作”可以實現普通加法操作；加法操作又可以作為一步操作用在更復雜的“間接操作”

5、中。實際上現在計算機內部電路能提供的操作遠不只是那幾個最簡單的“直接”操作。問題1:你會吃蟹黃湯包嗎?輕輕提, 慢慢移, 先開窗, 再喝湯。吃一只蟹黃湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，and then將包子慢慢移動到面前的小碟子中，and then 在包子的正上方咬開一個小口，and then通過小口吸食包子里的湯(當心別燙著)，and then將包子送入口中。完成！問題2：你如何確保過程無誤？假如我們認為在步驟4和5執行前要確保前面的結果是正確的，可以在相應的地方設個“監視哨” “guard”。問題3：但是我們并不只是吃一只，那怎么辦呢？策略一：控制數量假如規定吃8只：開始設

6、一個計數器，并將其值設定為0。吃一只湯包計數器值加1，并判斷其是否為8否是結束注意：這個過程的“結構”與計數器的初始值沒有關系！策略二：吃飽為止是否已飽？是否 問題4：如果即使飽了，也希望至少品嘗一只，該怎么辦？上下顛倒如何確定循環過程是正確的？循環不變式這是一個邏輯表達式在循環體中它應該始終為“真”例如：用一個逐項累加的循環計算a*b, 循環不變式可以是：“存放中間結果的量的值=a*“循環變量的當前值”問題5：你能為上述兩種吃蟹黃湯包的策略選定一個循環不變式嗎？“冒泡”排序 循環的嵌套自下往上這一段干的是什么事情?問題6:是否可以將“冒泡”中的內層循環表示成一個procedure/subro

7、utine, 形式上成為單層循環？Max(E, low, high): 找出指定范圍內的最大元素有人知道飽不飽，但有人不知道！開始要吃湯包的人不到5歲嗎？是選用策略1選用策略2否結束問題7：如果要判斷的不止是兩種可能，那怎么辦？分類定量控制開始要吃湯包的人不到5歲嗎？否參數設為2是結束要吃湯包的人不到60歲嗎？參數設為8是參數設為4否選用策略1(帶參數)對包含“money”一詞的句子計數搜索“money”一詞搜索句子結尾標記問題8：前面的例子中“搜索”兩次，盡管對象不同，動作確是一樣的，有可能只描述一次嗎？回想一下前面討論“冒泡”排序時提出的問題？問題9：你能總結一下采用subroutine的

8、好處嗎以“遞歸”的思維用于證明：數學歸納法教你一個小“魔術”：用一副撲克牌（不用“大小鬼”）事先按照紅黑相間排列好將牌大致分為兩份，確保下面可見的兩張牌顏色不同請一位觀者按常規方法洗牌1次（只是1次！）現在你可以不用看，保證“隨便”抽出的兩張牌一定是“一紅一黑”。基于“遞歸”的推理：怎么能做到以上效果的？不過是數學歸納法而已！遞歸：一種思維方式從數學歸納法到利用遞歸的思想解題往前跨一小步 只是一小步而已數學歸納法奠基：直接確認假設：假設對較小的目標值（比如k），待證結論成立歸納：你的任務是從“對于k成立”推導出“對于k+1”仍然成立。用遞歸手段解題Base case：直接給出結果假設：假設對較

9、小的目標值（比如n-1或者n/2），“有人”幫你算出結果了歸納：你的任務是從“那個結果”推算出對于n的結果書寫形式，其實不難！Hanoi Tower Easy or Difficult?還記得前頁上那個“假設”嗎？但是，“那個結果”在哪兒呢？這才是“真實”的執行過程！你看到的算法問題11：你能比較一下遞歸方法與數學歸納法嗎？為什么計算機出現之前只流行數學歸納法，卻沒有廣泛使用的“遞歸解題法”？遞歸和數學歸納法寫一個程序真得很容易！證明它正確其實也不難！移64個盤子試試Hanoi Tower問題1:“變量”是不是“量”？x x + 1 該如何理解？什么是“結構”？問題2：你認為這段話中哪些詞最關

10、鍵？你會想到什么兒時的游戲嗎?數據和“位置”“全班同學排好隊！”是什么意思？每人有了一個“位置”。其實這個“位置”是相對的。如果安排一種按照位置進行的“游戲”，“到了什么位置就知道該做什么”。如何以前面的觀點來理解vector, 或稱為list, 或稱為one-dimensional array是一種數據結構？問題3：數組（向量）和循環是什么關系？“隨意”和“受限”在書架的一層上取一本書在機場的飲水機旁取一個紙杯問題5：你能說出這兩者的差別嗎？更復雜的“位置”關系 “樹”用樹排序： 第1步：將數組表示為“二分搜索樹”問題7:你能看出這個樹是如何生成的嗎?用樹排序： 第2步：以“某種”方式遍歷樹

11、“ left-first traversal”“ second-visit output:問題8:為什么輸出肯定是從小到大的?問題9：樹和遞歸有什么關系？課堂示例片斷到此為止編程技能 自學加訓練Programming Tasks以周為單位安排，每周1-2個；在整個“計算機問題求解”課程中按照18*4周安排。.Documents教學珠峰計劃班教學資料2012級第1學期計算機問題求解-課程指南-2012級第1學期.docx.Documents教學珠峰計劃班教學資料2012級第2學期計算機問題求解-課程指南-2012級第2學期.docx第2周的編程任務題意概要:3，某公司員工提高工資7.6%，并從6個月前開始實施并補發。輸入每人的原來的年收入，輸出該補發的數額、新的年收入和月收入。允許用戶計算任意多次。10，輸入10個整數，輸出所有大于0的數的和、所有不大于0的數的和以及全體數的和。每個數只輸入一次，不能要求用戶按照是否大于0等條件分類輸入。 結束語取得的