遞歸算法課堂教學(xué)設(shè)計探討

王琳 張學(xué)波

摘要：結(jié)合大學(xué)計算機基礎(chǔ)課程的開設(shè)情況，針對課程中一些不易理解且難以講解的知識點，如遞歸算法，本文結(jié)合遞歸算法經(jīng)典示例漢諾塔問題，探討了一個新的課堂教學(xué)設(shè)計，并應(yīng)用于實際的教學(xué)中。首先如何引入課堂，抓住學(xué)生的興趣，然后提出問題，思考遞歸算法和漢諾塔之間的關(guān)系，并通過互動環(huán)節(jié)，讓學(xué)生動手嘗試挪動漢諾模型，學(xué)會使用計算思維進行思考與分析。最后依據(jù)遞歸原理，用Python語言編寫漢諾塔的遞歸函數(shù)。在實際教學(xué)過程中，該課堂設(shè)計提高了學(xué)員學(xué)習(xí)的主動性和參與度，提升了課堂教學(xué)質(zhì)量和學(xué)員的計算思維能力。

關(guān)鍵詞：課堂設(shè)計;遞歸算法;漢諾塔問題;可視化;turtle

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）27-0208-02

“大學(xué)計算機基礎(chǔ)”是大學(xué)本科教育的第一門計算機公共基礎(chǔ)課程，課程的主要目的是從計算機應(yīng)用、計算機系統(tǒng)理解和計算思維培養(yǎng)三個方面提高學(xué)生的計算機應(yīng)用能力。從2008年開始，以“計算思維”的培養(yǎng)為主線開展計算科學(xué)通識教育，逐漸成為國內(nèi)外計算機基礎(chǔ)教育界的共識。

基于這種共識，“大學(xué)計算機課程”選擇Python作為實踐語言，將信息編碼、微機原理、操作系統(tǒng)、網(wǎng)絡(luò)、數(shù)據(jù)庫等知識既作為教學(xué)內(nèi)容，又作為計算思維求解問題的研究對象加以實踐。希望通過這種問題求解的學(xué)習(xí)和實踐過程，在培養(yǎng)學(xué)生理解計算機基礎(chǔ)知識的同時，能有意識地將計算思維的方法和技能運用在各自專業(yè)的學(xué)習(xí)中，能解決具有一定難度的實際問題。

作為課程的重難點之一的第三章，即計算思維這一章，要求學(xué)生在理解計算思維的同時，要了解一些典型算法，并能夠掌握典型算法的Python實現(xiàn)方法。本文以遞歸算法為例，探討如何更好地進行課堂設(shè)計。

遞歸算法作為經(jīng)典算法之一，雖然實現(xiàn)較容易，但理解起來有一定的難度，為了讓學(xué)生能更直觀的理解遞歸算法，課程專門設(shè)置了一個遞歸算法經(jīng)典示例漢諾塔問題，利用Python的turtle庫實現(xiàn)漢諾塔的可視化，幫助學(xué)生從抽象的理論思維過渡到直觀的可視化應(yīng)用。

1 如何引入課堂

教師在講解漢諾塔問題之前，可以借助動畫的形式展現(xiàn)可視化的漢諾塔，便于較快地抓住學(xué)生的注意力，提高學(xué)習(xí)興趣;引導(dǎo)學(xué)生在觀看動畫的同時，思考漢諾塔中的每個盤片是怎樣移動的？利用Python語言如何編寫程序?qū)崿F(xiàn)它的可視化效果？

帶著這些問題，教師引出漢諾塔問題的傳說和移動規(guī)則。漢諾塔問題來源于一個古老的傳說， 傳說印度教里有一個神叫梵天，梵天在創(chuàng)造世界的時候做了三根金剛石柱子，其中在 1號柱子按大小順序套著64個黃金盤片，梵天要求僧侶們把這64個盤片借助于中間的2號柱子移到3號柱子上，按原來的樣子擺放好。盤片在移動的過程中要遵守兩個規(guī)則：一次只能移動一個盤片;大盤片不能疊放在小盤片的上面。

講解完規(guī)則后，繼續(xù)借助于傳說，將學(xué)生的興趣和好奇心拉至最高點。如果按照這樣的規(guī)則進行搬移，梵天預(yù)言，一旦這些盤片完成搬移，世界將會毀滅。該結(jié)論一出，學(xué)生們紛紛表示懷疑;在這個互動環(huán)節(jié)，可以讓學(xué)生大致算一算，假如搬完所有盤片需要多長的時間？經(jīng)過計算，搬完所有盤片需要移動的次數(shù)是264-1=1.8×1019次，也就是1800億億次，如果每秒搬動一次，則需要584，942，417，355年，也就是五千億年！拿五千億年和我們?nèi)祟惖拈L河幾百萬年相比，要搬完64個盤片是不可能的。

通過證實結(jié)論，學(xué)生的疑慮消除了，此時講解思路180度轉(zhuǎn)彎，視角回到當(dāng)今的計算機時代、數(shù)據(jù)化時代，人工不能完成的事情是不是可以借助于計算機實現(xiàn)呢？借助于計算機，利用抽象化、自動化的方式將實際問題進行轉(zhuǎn)化，從而解決這個問題，這正是大學(xué)計算機基礎(chǔ)課程的目的，利用計算思維解決各領(lǐng)域的實際問題。

2 如何引導(dǎo)學(xué)生利用計算思維分析遞歸算法和漢諾塔之間的關(guān)系

計算思維是運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動。計算思維是運用計算機科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類的行為。它包括了涵蓋計算機科學(xué)之廣度的一系列思維活動。當(dāng)我們必須求解一個特定的問題時，首先會問：解決這個問題有多么困難？怎樣才是最佳的解決方法？計算機科學(xué)根據(jù)堅實的理論基礎(chǔ)來準確地回答這些問題。表述問題的難度就是工具的基本能力，必須考慮的因素包括機器的指令系統(tǒng)、資源約束和操作環(huán)境[1，2]。

教師可以借助于提前準備好的教具-漢諾塔模型，讓學(xué)生以分組的方式動手嘗試簡單漢諾塔的移動過程，并展開小組討論。在實踐的過程中，有些小組成員思維反應(yīng)較快，能夠完成5-6層漢諾塔的移動，有些小組陷入了移動的僵局。無論是完成快的小組還是慢的小組，都很難說清漢諾塔和遞歸算法之間的關(guān)系。

帶著這個問題，教師進行示范，從一個盤片的漢諾塔開始擺起，當(dāng)擺到兩個盤片的漢諾塔時，學(xué)生思考總結(jié)出移動三部曲，先移走上面的小盤片至中間柱，再移動大盤片至右側(cè)的目標柱，最后移動小盤片到目標柱。利用移動三部曲，在挪動三個盤片的漢諾塔時，可以把上面的兩個小盤片看成一個整體，完成三部曲，再將整體還原為兩個小盤片，兩個小盤片的移動剛剛已經(jīng)做過。這時，學(xué)生恍然大悟，可以利用三部曲嘗試移動3個甚至更多盤片。最后，教師進行總結(jié)，借助于五個盤片的漢諾塔，并用遞歸圖更好地詮釋了漢諾塔的三部曲移動正是借助了遞歸算法。

分析完漢諾塔和遞歸算法之間的關(guān)系后，整理思路，依據(jù)遞歸算法原理，設(shè)計求解漢諾塔問題的函數(shù)hanoi（n， A， B， C），設(shè)置4個參數(shù)，用n代表盤片的數(shù)量，用A、B、C分別代表起始柱、中間柱和目標柱。然后引導(dǎo)學(xué)生借助Python語言編寫該函數(shù)，利用IF、ELSE分支結(jié)構(gòu)，分為兩種情況：當(dāng)只有1個盤片時，直接從A柱移至B柱;當(dāng)大于1個盤片時，按上述的移動三部曲進行移動。