計算思維與語言技能陳道蓄

1、計算(j sun)思維與語言技能- 在程序設計課中如何權衡陳道蓄南京(nn jn)大學計算機科學與技術系2014年11月29日 鄭州共四十九頁我們經常從教程序設計(chn x sh j)課的老師口中聽到這樣的話:“我這個(zh ge)課可不是只教一種語言的，我們教的是思想！”共四十九頁我們(w men)能說清楚嗎？問題1：什么(shn me)是思想？問題2：是什么思想？問題3：學生感悟到“思想”了嗎？共四十九頁什么(shn me)是計算思維？或者我們(w men)換一個問法：什么不是？計算機文化：為什么“遇到問題上百度”算不上是計算思維？計算機技術：為什么“了解操作系統(tǒng)的功能與結構”也不應該算

2、是計算思維？怎樣能讓計算機幫我們解題？共四十九頁思維“傳遞(chund)”與“載體”“思想”只能傳遞, 不能直接“教”。有效(yuxio)的“傳遞”需要兩個條件：合適的“載體”，適當?shù)摹袄印卑凑丈鲜鱿敕▉韺徱曃覀兡壳暗某绦蛟O計課程載體相對復雜；例子相對簡單共四十九頁基本(jbn)想法與改革路線基本想法：顯式區(qū)分“思維方法”與“編程技能”對不同的目標采用不同的教學方法方法設計基本思路：“思維”靠“悟”；“技能”靠“練”做法：引導學生去“悟”，不依靠特定語言(yyn)；加大訓練強度，不拘泥于語言成分。共四十九頁基本內容(nirng)載體1，計算機為什么能解題？2，基本的算法結構3，基本的數(shù)據(jù)結構

3、(sh j ji u)4，遞歸及其代價下面提供一些課堂實例片斷共四十九頁計算機問題(wnt)求解計算機問題(wnt)求解問題1a:計算機究竟能干什么？問題1b:人究竟是如何解題的？問題1：為什么計算機能幫我們解題？共四十九頁Even More Amazing 0 1 0 1 10 1 0 0 10 1 1 0 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)共四十九頁問題(wnt)2：我們可以讓計算機“間接地”執(zhí)行什么操作？你試試讓計算機比較兩個1-bit二

4、進制數(shù)是否相等，只用前面提到的運算(yn sun)，如果需要，你可以使用輔助的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=1Otherwise eq=0你能將這個操作擴展到, 比如(br), 32位內的整數(shù)嗎?共四十九頁稍微增加(zngji)一點操作計算(j sun)兩個1-bit二進制數(shù)的和xyz1z0tx+yadd (x,y)1. zero z0; 2. zero z1;

5、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; 如果只允許原來三個基本操作, 能完成這個任務嗎?共四十九頁多層次抽象(chuxing) 用一位的加法“間接操作”可以實現(xiàn)普通加法操作；加法操作又可以作為一步操作用在更復雜的“間接操作”中。實際上現(xiàn)在計算機內部電路能提供的操作遠不只是那幾個(j )最簡單的“直接”操作。共四十九頁問題(wnt)1:你會吃蟹黃湯包嗎?輕輕提, 慢慢(mn mn)移, 先開窗

6、, 再喝湯。共四十九頁吃一只蟹黃(xihung)湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，and then將包子慢慢移動到面前的小碟子(di zi)中，and then 在包子的正上方咬開一個小口，and then通過小口吸食包子里的湯(當心別燙著)，and then將包子送入口中。完成！共四十九頁問題2：你如何確保(qubo)過程無誤？假如我們認為在步驟4和5執(zhí)行前要確保前面的結果是正確(zhngqu)的，可以在相應的地方設個“監(jiān)視哨” “guard”。共四十九頁問題3：但是(dnsh)我們并不只是吃一只，那怎么辦呢？共四十九頁策略一：控制(kngzh)數(shù)量假如(jir)規(guī)定吃8只：

7、開始設一個計數(shù)器，并將其值設定為0。吃一只湯包計數(shù)器值加1，并判斷其是否為8否是結束注意：這個過程的“結構”與計數(shù)器的初始值沒有關系！共四十九頁策略(cl)二：吃飽為止是否已飽？是否 問題4：如果即使(JSH)飽了，也希望至少品嘗一只，該怎么辦？上下顛倒共四十九頁如何確定(qudng)循環(huán)過程是正確的？循環(huán)不變式這是一個邏輯表達式在循環(huán)體中它應該(ynggi)始終為“真”例如：用一個逐項累加的循環(huán)計算a*b, 循環(huán)不變式可以是：“存放中間結果的量的值=a*“循環(huán)變量的當前值”問題5：你能為上述兩種吃蟹黃湯包的策略選定一個循環(huán)不變式嗎？共四十九頁“冒泡”排序(pi x) 循環(huán)的嵌套自下(z xi

8、)往上這一段干的是什么事情?共四十九頁問題6:是否可以將“冒泡”中的內層循環(huán)表示成一個(y )procedure/subroutine, 形式上成為單層循環(huán)？Max(E, low, high): 找出指定(zhdng)范圍內的最大元素共四十九頁有人(yu rn)知道飽不飽，但有人(yu rn)不知道！開始(kish)要吃湯包的人不到5歲嗎？是選用策略1選用策略2否結束問題7：如果要判斷的不止是兩種可能，那怎么辦？共四十九頁分類(fn li)定量控制開始要吃湯包的人不到5歲嗎？否參數(shù)設為2是結束要吃湯包的人不到60歲嗎？參數(shù)設為8是參數(shù)設為4否選用策略1(帶參數(shù))共四十九頁對包含“money”一

9、詞的句子(j zi)計數(shù)搜索(su su)“money”一詞搜索句子結尾標記共四十九頁問題8：前面的例子中“搜索”兩次，盡管對象不同，動作(dngzu)確是一樣的，有可能只描述一次嗎？回想一下前面討論“冒泡”排序時提出(t ch)的問題？共四十九頁共四十九頁問題(wnt)9：你能總結一下采用subroutine的好處嗎共四十九頁以“遞歸”的思維用于證明：數(shù)學歸納法教你一個小“魔術”：用一副撲克牌（不用(byng)“大小鬼”）事先按照紅黑相間排列好將牌大致分為兩份，確保下面可見的兩張牌顏色不同請一位觀者按常規(guī)方法洗牌1次（只是1次?。┈F(xiàn)在你可以不用看，保證“隨便”抽出的兩張牌一定是“一紅一黑”。

10、基于“遞歸”的推理：怎么能做到以上效果的？不過是數(shù)學歸納法而已！遞歸：一種(y zhn)思維方式共四十九頁從數(shù)學歸納法到利用(lyng)遞歸的思想解題往前跨一小步 只是(zhsh)一小步而已數(shù)學歸納法奠基：直接確認假設：假設對較小的目標值（比如k），待證結論成立歸納：你的任務是從“對于k成立”推導出“對于k+1”仍然成立。用遞歸手段解題Base case：直接給出結果假設：假設對較小的目標值（比如n-1或者n/2），“有人”幫你算出結果了歸納：你的任務是從“那個結果”推算出對于n的結果書寫形式，其實不難！共四十九頁Hanoi Tower Easy or Difficult?還記得前頁上那個(n

11、 ge)“假設”嗎？但是(dnsh)，“那個結果”在哪兒呢？共四十九頁這才是“真實”的執(zhí)行過程！你看到的算法共四十九頁問題11：你能比較一下遞歸方法(fngf)與數(shù)學歸納法嗎？為什么計算機出現(xiàn)之前只流行(lixng)數(shù)學歸納法，卻沒有廣泛使用的“遞歸解題法”？共四十九頁遞歸和數(shù)學(shxu)歸納法寫一個(y )程序真得很容易！證明它正確其實也不難！移64個盤子試試Hanoi Tower共四十九頁問題(wnt)1:“變量”是不是“量”？x x + 1 該如何(rh)理解？共四十九頁什么(shn me)是“結構”？問題2：你認為(rnwi)這段話中哪些詞最關鍵？你會想到什么兒時的游戲嗎?共四十九頁

12、數(shù)據(jù)(shj)和“位置”“全班同學排好隊！”是什么意思(y s)？每人有了一個“位置”。其實這個“位置”是相對的。如果安排一種按照位置進行的“游戲”，“到了什么位置就知道該做什么”。如何以前面的觀點來理解vector, 或稱為list, 或稱為one-dimensional array是一種數(shù)據(jù)結構？共四十九頁問題3：數(shù)組（向量）和循環(huán)是什么(shn me)關系？共四十九頁共四十九頁“隨意(su y)”和“受限”在書架的一層上取一本書在機場(jchng)的飲水機旁取一個紙杯問題5：你能說出這兩者的差別嗎？共四十九頁共四十九頁更復雜(fz)的“位置”關系 “樹”共四十九頁用樹排序： 第1步：將數(shù)

13、組表示(biosh)為“二分搜索樹”問題7:你能看出這個(zh ge)樹是如何生成的嗎?共四十九頁用樹排序： 第2步：以“某種”方式(fngsh)遍歷樹“ left-first traversal”“ second-visit output:問題8:為什么輸出(shch)肯定是從小到大的?共四十九頁問題9：樹和遞歸有什么(shn me)關系？課堂示例片斷(pindun)到此為止共四十九頁編程技能(jnng) 自學加訓練Programming Tasks以周為單位(dnwi)安排，每周1-2個；在整個“計算機問題求解”課程中按照18*4周安排。.Documents教學珠峰計劃班教學資料2012級

14、第1學期計算機問題求解-課程指南-2012級第1學期.docx.Documents教學珠峰計劃班教學資料2012級第2學期計算機問題求解-課程指南-2012級第2學期.docx共四十九頁第2周的編程任務(rn wu)題意概要:3，某公司員工提高工資7.6%，并從6個月前開始實施并補發(fā)。輸入每人的原來(yunli)的年收入，輸出該補發(fā)的數(shù)額、新的年收入和月收入。允許用戶計算任意多次。10，輸入10個整數(shù)，輸出所有大于0的數(shù)的和、所有不大于0的數(shù)的和以及全體數(shù)的和。每個數(shù)只輸入一次，不能要求用戶按照是否大于0等條件分類輸入。 共四十九頁結束語取得的經驗明顯提高了學生學習的積極性和主動性在第一學期結束時基本可以消除入學時學生在程序設計經歷上的巨大差異帶來的負面影響明顯加大了對學生解決問題的能力的要求，在一定程度上取得了在基礎課中提高學生能力的經驗(jngyn)面臨的挑戰(zhàn)在更大范圍內推廣，主要難點應該不是學生（內容深度是可以調整的），而是教師配備足夠合格的跟蹤輔導力量最深的體會之一: 可能我們(w men)原來太不相信學生的能力了!共四十九頁內容摘要計算思維與語言技能- 在程序設計課中如何權衡?！拔疫@個課可不是只教一種語言的，我們教的是思想。你能將這個操作擴展(kuzhn)到, 比如, 32位內的整數(shù)嗎。用一位的加法“間