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

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

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

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

4、進(jìn)制數(shù)是否相等，只用前面提到的運(yùn)算(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你能將這個(gè)操作擴(kuò)展到, 比如(br), 32位內(nèi)的整數(shù)嗎?共四十九頁稍微增加(zngji)一點(diǎn)操作計(jì)算(j sun)兩個(gè)1-bit二進(jìn)制數(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; 如果只允許原來三個(gè)基本操作, 能完成這個(gè)任務(wù)嗎?共四十九頁多層次抽象(chuxing) 用一位的加法“間接操作”可以實(shí)現(xiàn)普通加法操作；加法操作又可以作為一步操作用在更復(fù)雜的“間接操作”中。實(shí)際上現(xiàn)在計(jì)算機(jī)內(nèi)部電路能提供的操作遠(yuǎn)不只是那幾個(gè)(j )最簡(jiǎn)單的“直接”操作。共四十九頁問題(wnt)1:你會(huì)吃蟹黃湯包嗎?輕輕提, 慢慢(mn mn)移, 先開窗

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

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

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

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

10、基于“遞歸”的推理：怎么能做到以上效果的？不過是數(shù)學(xué)歸納法而已！遞歸：一種(y zhn)思維方式共四十九頁從數(shù)學(xué)歸納法到利用(lyng)遞歸的思想解題往前跨一小步 只是(zhsh)一小步而已數(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ì)較小的目標(biāo)值（比如n-1或者n/2），“有人”幫你算出結(jié)果了歸納：你的任務(wù)是從“那個(gè)結(jié)果”推算出對(duì)于n的結(jié)果書寫形式，其實(shí)不難！共四十九頁Hanoi Tower Easy or Difficult?還記得前頁上那個(gè)(n

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

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

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

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