庖丁解牛 破解算法大題

鄭名輝

【背景】根據(jù)浙江省信息技術(shù)選考試題來看，第14、16、17題為算法題，其中17題往往題目復(fù)雜，難度也最大，學(xué)生的丟分率非常高。而丟分率高的原因有多方面，其中之一就是根本來不及。此外因為方法不當(dāng)，雖耗費大量寶貴的時間，導(dǎo)致效果極差。正是處于這種現(xiàn)狀，筆者開始深入研究，希望能從中找尋出一套行之有效的解題技巧。

由于本校生源屬于淳安縣第三批次類學(xué)生（經(jīng)歷兩道篩選后進(jìn)入我校的學(xué)生），其底子薄，智力水平一般且無特別突出者。而算法大題，卻需要很強(qiáng)的邏輯思維，被很多人稱之為“聰明人的游戲”，故對于我們這樣的學(xué)生在歷屆選考當(dāng)中，算法第17大題往往不得不先放棄，實數(shù)無奈之舉?？墒歉鶕?jù)筆者的研究與探討發(fā)現(xiàn)，選考中的算法大題其實不需要太高深的理論和強(qiáng)大的“智慧大腦”，需要的是：平時加強(qiáng)思維訓(xùn)練，加強(qiáng)算法基礎(chǔ)知識的把握，然后引入恰當(dāng)?shù)姆椒?，“普通人”也可以解這道最難的算法大題。

【準(zhǔn)備】

1.PPT課件1份（內(nèi)含待講解的算法大題1道及其妙解策略）

2.相關(guān)學(xué)生講義一張，并做好課前預(yù)習(xí)

【教學(xué)過程】

一、以課件展示一道很長的算法大題（經(jīng)典的第17題），引入話題

課件問：這是信息技術(shù)選考卷中的第17算法大題，拿到這道題后，你怎么入手？

情形1：先讀題再逐句逐句研讀代碼？

老師：如果用這種方法，我想往往會導(dǎo)致時間不夠，吃力不討好，但結(jié)果仍然不知何處！怎么辦？

情形2：猜？

老師：如果沒有一定的思維推理，沒有對程序代碼的把握，瞎猜有用？那，又怎么辦？

二、以一道題為例，逐步引入解題技巧

老師：同學(xué)們，請看題。這第一小題要求求出“-108”的2進(jìn)制補(bǔ)碼。好，這個時候我再去看題目要求，“若n<0，則將n+128轉(zhuǎn)換為對應(yīng)的7位2進(jìn)制數(shù)，前面的符號位為1”。

引出1：如何讀題？這是以例子來理解題目的比較省時且能快速理解題意的方法。

引出2：通過這道題目的解題，把握其“解決問題的方法，即算法”！

老師：對于這道題，相信同學(xué)們都可以做出來，因為它接下去就只用到一個知識點……

學(xué)生：十進(jìn)制化二進(jìn)制。如果沒有回答，則老師可直接提出。

老師：好，既然是進(jìn)制轉(zhuǎn)換，那就簡單了。故通過此題老師想告訴同學(xué)們兩點：第一，如何快速讀題;第二，此題解答的過程，其實也幫助我們掌握其算法的核心思想;第三，那就是本堂課的重點——算法的解題技巧，第1法——運用基本知識解答之！

引出老師總結(jié)的所有方法：

老師：然后我們繼續(xù)看第（2）小題這3空，這個如果繼續(xù)用第1法——運用基本知識解答可行嗎？

學(xué)生：不可行。

老師：那怎么辦？

If學(xué)生：邏輯推理，大膽猜?。ǖ?法）

then老師：這方法合適么？如果我們對代碼沒有做分析，簡單推理能得到答案么？

Else if學(xué)生：快速讀題，把握“解決問題的方法”——算法！（第3法）

then老師：其實第（1）空已經(jīng)幫我我們掌握了該算法的核心思想。

Else if學(xué)生：把握程序結(jié)構(gòu)，庖丁解牛（第4法）

then老師：對。對于它，在把握算法的核心思想后，我們就需要從大結(jié)構(gòu)去把握這道題。

……

老師：同學(xué)們，請大家仔細(xì)觀察，該程序由3段代碼構(gòu)成，分別是SUB和兩個自定義函數(shù)構(gòu)成。如果我們搞定了他們的各自功能，則對于解題一定有幫助。

老師：從SUB過程可知，Text2.text的作用是把2進(jìn)制補(bǔ)碼的結(jié)果顯示出來，故該SUB的功能是輸出結(jié)果！而①處一句話，是不可能把問題解決的，通過簡單邏輯推敲，它必定與下面的代碼有關(guān)！

該段代碼是一個bm自定義函數(shù)，其功能根據(jù)算法的核心思想，我們也可以快速斷定：bm函數(shù)是補(bǔ)0或者補(bǔ)1。轉(zhuǎn)化成二進(jìn)制，這段代碼里頭顯然沒有。但是一個d2b（n）引起了我們的注意，它又是什么呢？

學(xué)生：下面的d2b函數(shù)！

老師：對！我們繼續(xù)看，我們繼續(xù)看，這段代碼的結(jié)構(gòu)太眼熟了，同學(xué)們，老師看出來了，你們呢？

學(xué)生：換成二進(jìn)制！

老師：哪里看出來的？

學(xué)生：……

老師：平時我們聯(lián)系十進(jìn)制化二進(jìn)制，用的是除二取余法。那上面的代碼里頭“p=n mod 2”是什么意思，有什么用？

學(xué)生：邏輯推理，大膽猜？

老師：可以。但是如果平時的功課做好了，就不用猜，直接確定：下面一定會出現(xiàn)n=n＼2或類似功能的語句。因為這兩句配套使用，就實現(xiàn)了十進(jìn)制化二進(jìn)制。所以老師第一眼就把握了這段函數(shù)的結(jié)果，當(dāng)然這第③空就非常簡單了！答案就是n=n＼2。

現(xiàn)在我們已經(jīng)對其結(jié)構(gòu)及其各結(jié)構(gòu)的功能的確定，則第②空，根據(jù)Sgn（n）>0的情況對比，很容易確定其答案為bm=”1”&d2b（n），其中的n=n+128也佐證了這一點！

老師：到了這里，我想再看第①處，則很容易想到其與bm函數(shù)有關(guān)，根據(jù)bm函數(shù)的參數(shù)可以確定答案為：bm（dec）。

這就是把握程序結(jié)構(gòu)之后，帶來的好處！它有助于我們從整體上把握，而不落入只見樹木不見森林的困境，也無法走出算法給我們，出題人給我們事先預(yù)設(shè)好、安排好的陷阱！

三、方法總結(jié)

1.基礎(chǔ)知識應(yīng)用——對于第（1）空的進(jìn)制轉(zhuǎn)換。

2.邏輯推理，大膽猜??！——對于第②空，我們可以邏輯推理大膽猜，但前提是要通過第（1）空先把握該算法的核心思想！

3.快速讀題，把握“解決問題的方法”——算法，在解答第（1）空和第②空時，很明顯要用到。

4.把握程序結(jié)構(gòu)，力爭“庖丁解?！薄?/p>

通過大結(jié)構(gòu)的把握，讓我們做一回“庖丁”，順利解開“算法”這道牛！

5.最后記得驗算。

驗算，是為了防止特例和特殊值或情況，出題人的陷阱之一，不得不防！

【課堂及課后練習(xí)】把剩余的1（課堂練習(xí)）+2（課后練習(xí)）道17算法題用上述方法去實踐、練習(xí)。