基于圖形計算器的算法實現(xiàn)與算法初步教學(xué)

楊一奮

摘 ?要：作為一種實現(xiàn)算法的有力工具，圖形計算器不但可以將算法化的思路落到實處，更可以在可視化的基礎(chǔ)上提供分析算法的通道. 文章從實例出發(fā)，詳解了算法實現(xiàn)和算法分析的具體操作，并提出基于圖形計算器的手持特點，可以使“算法”成為學(xué)生主動建構(gòu)的結(jié)果，而其中蘊涵的算法思想恰是學(xué)生所真正“可以理解、可以學(xué)到手和加以推廣應(yīng)用的”.

關(guān)鍵詞：算法實現(xiàn);圖形計算計算器;算理;算法比較

我們知道，算法是指為解決問題而實施有窮操作過程的描述，更是一種便于機械化的重復(fù)迭代，學(xué)習(xí)算法需要學(xué)習(xí)程式化的過程，因此，“算法思想已經(jīng)成為現(xiàn)代人應(yīng)具備的一種數(shù)學(xué)素養(yǎng)”.其中算法分析和算法實現(xiàn)是兩個重要步驟，沒有算法分析，我們無從檢驗算法設(shè)計的正確性;離開算法實現(xiàn)，我們的算法學(xué)習(xí)只能停留于“紙上談兵”階段. 事實上，算法設(shè)計的優(yōu)劣需要上機檢驗，算法設(shè)計的改進需要調(diào)試修正，更重要的是讓學(xué)生在計算機上實現(xiàn)問題解決的同時經(jīng)歷一個由不那么精確、不那么完整到比較精確、比較完善的發(fā)展過程，使“算法”不僅是宣布某個結(jié)果，而且也是學(xué)生主動建構(gòu)的結(jié)果，因此算法教學(xué)應(yīng)提倡算法化.

雖然從理論上講算法教學(xué)離不開算法實現(xiàn)，但應(yīng)用實際卻停留于“紙上談兵”，究其原因還在于偽代碼表示的算法不能被計算機所“接受”，雖然幾何畫板、Excel也能實現(xiàn)算法，但卻頗費周折. 作為一種集數(shù)值計算、函數(shù)圖象顯示、編程、數(shù)據(jù)分析等功能于一身的手持式信息技術(shù)，圖形計算器無疑為算法實現(xiàn)提供了一條捷徑. 以Casio fx-CG20為例，借助其自帶的【程序】模塊，可以輕松實現(xiàn)“提出問題→建立模型→設(shè)計算法→編寫程序→計算器調(diào)試”的算法教學(xué)全過程.

計算器語法與偽代碼的轉(zhuǎn)換

通常教材中描述算法用的是偽代碼，雖然方便表達，但卻有著不可執(zhí)行性，為方便起見，我們將圖形計算器語法與偽代碼的表達比較如表1.

循環(huán)結(jié)構(gòu)的算法實現(xiàn)

我們知道，算法的價值在于機械化（為計算機所能執(zhí)行）的重復(fù)執(zhí)行，因此循環(huán)結(jié)構(gòu)是算法的重點和核心. 循環(huán)結(jié)構(gòu)的構(gòu)造關(guān)鍵在于：循環(huán)體的形成、相應(yīng)循環(huán)變量的賦值以及循環(huán)結(jié)構(gòu)的控制（包括循環(huán)的執(zhí)行和終止），也就是說“從什么地方開始”，“反復(fù)做什么”，“在什么條件下結(jié)束”.

例1 ?設(shè)計一個算法，計算100以內(nèi)被3除余1的所有正數(shù)的和.

【算法分析】 ?符合條件的數(shù)為1、4、7、…、100共34個數(shù)，本題就是求這34個數(shù)的和，即從1開始，反復(fù)累加比前一數(shù)大3的數(shù)，直加到第34個數(shù)為止. 循環(huán)次數(shù)確定時一般考慮用For循環(huán)設(shè)計程序，可考慮用累加變量S（初始值設(shè)定為0）來接受結(jié)果，從而循環(huán)體中的賦值語句S+I→S（其中I為計數(shù)變量，I的值分別對應(yīng)1，4，7，…，100）. 具體程序如圖1所示.

圖1

【算法釋疑】 ?For循環(huán)結(jié)構(gòu)比較簡單，往往通過計數(shù)變量來控制循環(huán)結(jié)構(gòu)（本題中I為循環(huán)控制變量），其中“1→I”為對循環(huán)控制變量賦初值，“Step3”相當于語句“I+3→I”，而“To 100”則表示循環(huán)的結(jié)束，相當于While循環(huán)中的“While I≤100”，圖1的程序如果改寫成While循環(huán)則程序如圖2所示.

圖2

例2 ?設(shè)計求滿足條件12+22+32+…+n2>102的最小正整數(shù)的算法.

【算法分析】 ?由于n的值事先不知道（也就是說循環(huán)次數(shù)不確定），我們只能通過試錯的方法，用從1開始反復(fù)累加比前一個數(shù)大1的數(shù)的平方，然后將和與105作大小比較，直到和大于105為止，一般情況下這樣的算法我們采用WHILE循環(huán)（設(shè)置累加變量S、計數(shù)變量n）來實現(xiàn)，偽代碼程序如圖3所示，計算器實現(xiàn)如圖4“所示”.

圖4

計算器中的算法比較

在計算器中雖然可以較輕松地實現(xiàn)算法，但在算計設(shè)計過程中我們常常會出現(xiàn)循環(huán)體語句倒置的問題，如例2中我們就容易出現(xiàn)語句40和語句50對調(diào)的情況，這樣執(zhí)行圖5的程序產(chǎn)生的結(jié)果（執(zhí)行結(jié)果為68）卻和圖5的結(jié)果（執(zhí)行結(jié)果為67）相迥異，于是擺在我們面前的問題就是哪一個算法正確，如何修正算法？

圖5

解決問題需要追蹤每一次循環(huán)執(zhí)行后算法變量值的變化，手工操作顯然不易，一個可行的思路將變量值輸出到【統(tǒng)計】模塊中，通過列表的方式將數(shù)據(jù)“看得見”. 具體操作是在程序中插入兩段語句（如圖6和圖7中標注部分），語句的含義是把變量的結(jié)果按順序輸出到表格的第1、2、3、4列中. 然后切換到【統(tǒng)計】模塊，可以發(fā)現(xiàn)1～4列均有數(shù)值輸入，撥動BN鍵仔細觀察列首（圖8）列尾（圖9），可以看出程序“I”中變量N、S的賦值有一定的錯位（見圖中標注部分），從算法分析可以看出，程序5需要做一定的調(diào)整（或者循環(huán)前變量N的初值賦值變更為“1→N”，或者循環(huán)后增加語句“N-1→N”）. 更進一步的思考是程序4是先遞進后累加，而程序5則是先累加后遞進，從而可以看出需要重視循環(huán)體中語句的順序，分析算法往往需要追蹤循環(huán)的前面兩步和最后兩步.

圖8

圖9

利用圖形計算器在不同模塊的關(guān)聯(lián)性，我們可以實現(xiàn)循環(huán)變量的追蹤，其實我們還可以將算法中的結(jié)果可視化.

例3 ?隨機模擬法估算圓周率的算法實現(xiàn).

進入【程序】模塊，輸入圖10所示的程序命令，其中第2行到第4行的語句是畫正方形、畫圓語句，此外“Read Plot A，B”是描點語句;按F1執(zhí)行后，可得到圖11所示的結(jié)果.

通過圖文并茂的展示，我們不但可以幫助學(xué)生確信結(jié)果，更可以將注意力放在算法原理的剖析上：程序中數(shù)值A(chǔ)、B為0～1之間的隨機數(shù)，這樣構(gòu)成的點（A，B）一定落在單位正方形內(nèi)，而通過條件判斷可以考察點（A，B）是否在圓（x-0.5）2+（y-0.5）2= ?內(nèi)，在圓內(nèi)則統(tǒng)計，不在圓內(nèi)則不統(tǒng)計;如果總共產(chǎn)生N個隨機點，而落在圓內(nèi)的有K個點，這樣有概率計算公式 ?≈ ?，即π≈ ?.

綜上可知，作為一種實現(xiàn)算法的有力工具，圖形計算器無疑為信息技術(shù)與數(shù)學(xué)學(xué)科的整合提供了新的思路和選擇，從而從技術(shù)層面確保了算法化教學(xué)的開展. 我們也應(yīng)看到，語言只是工具，算法才是程序設(shè)計的靈魂，何況“算法”應(yīng)是學(xué)生主動建構(gòu)的結(jié)果，因此我們關(guān)注算法實現(xiàn)也要重視算法設(shè)計和流程圖的教學(xué)，更要創(chuàng)設(shè)問題情境讓學(xué)生有機會探索解決問題的算法，唯有如此才能保證蘊涵在算法中的算法思想為學(xué)生所真正“可以理解、可以學(xué)到手和加以推廣應(yīng)用的”.