計(jì)算思維與語(yǔ)言技能陳道蓄

1、計(jì)算思維與語(yǔ)言技能- 在程序設(shè)計(jì)課中如何權(quán)衡陳道蓄南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系2014年11月29日 鄭州我們經(jīng)常從教程序設(shè)計(jì)課的老師口中聽(tīng)到這樣的話:“我這個(gè)課可不是只教一種語(yǔ)言的，我們教的是思想！”我們能說(shuō)清楚嗎？問(wèn)題1：什么是思想？問(wèn)題2：是什么思想？問(wèn)題3：學(xué)生感悟到“思想”了嗎？什么是計(jì)算思維？或者我們換一個(gè)問(wèn)法：什么不是？計(jì)算機(jī)文化：為什么“遇到問(wèn)題上百度”算不上是計(jì)算思維？計(jì)算機(jī)技術(shù)：為什么“了解操作系統(tǒng)的功能與結(jié)構(gòu)”也不應(yīng)該算是計(jì)算思維？怎樣能讓計(jì)算機(jī)幫我們解題？思維“傳遞”與“載體”“思想”只能傳遞, 不能直接“教”。有效的“傳遞”需要兩個(gè)條件：合適的“載體”，適當(dāng)?shù)摹袄印卑?/p>

2、照上述想法來(lái)審視我們目前的程序設(shè)計(jì)課程載體相對(duì)復(fù)雜；例子相對(duì)簡(jiǎn)單基本想法與改革路線基本想法：顯式區(qū)分“思維方法”與“編程技能”對(duì)不同的目標(biāo)采用不同的教學(xué)方法方法設(shè)計(jì)基本思路：“思維”靠“悟”；“技能”靠“練”做法：引導(dǎo)學(xué)生去“悟”，不依靠特定語(yǔ)言；加大訓(xùn)練強(qiáng)度，不拘泥于語(yǔ)言成分?；緝?nèi)容載體1，計(jì)算機(jī)為什么能解題？2，基本的算法結(jié)構(gòu)3，基本的數(shù)據(jù)結(jié)構(gòu)4，遞歸及其代價(jià)下面提供一些課堂實(shí)例片斷計(jì)算機(jī)問(wèn)題求解計(jì)算機(jī)問(wèn)題求解問(wèn)題1a:計(jì)算機(jī)究竟能干什么？問(wèn)題1b:人究竟是如何解題的？問(wèn)題1：為什么計(jì)算機(jī)能幫我們解題？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)問(wèn)題2：我們可以讓計(jì)算機(jī)“間接地”執(zhí)行什么操作？你試試讓計(jì)算機(jī)比較兩個(gè)1-bit二進(jìn)制數(shù)是否相等，只用前面提到的運(yùn)算，如果需要，你可以使用輔助的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你能將這個(gè)操作擴(kuò)展到, 比如, 32位內(nèi)的整數(shù)嗎?稍微增加一點(diǎn)操作計(jì)算兩個(gè)1-bit二進(jìn)制數(shù)的和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; 如果只允許原來(lái)三個(gè)基本操作, 能完成這個(gè)任務(wù)嗎?多層次抽象 用一位的加法“間接操作”可以實(shí)現(xiàn)普通加法操作；加法操作又可以作為一步操作用在更復(fù)雜的“間接操作”

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

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

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

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

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

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

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