王民川

鄭州廣播電視大學(xué)，河南鄭州 450007

“C++”環(huán)境下的算法探討

王民川

鄭州廣播電視大學(xué)，河南鄭州 450007

本文通過一個(gè)實(shí)例揭示如何將算法原理和程序設(shè)計(jì)相互結(jié)合；如何借助程序開發(fā)實(shí)踐來進(jìn)一步理解二分法求近似根算法的實(shí)質(zhì)，從而深刻理解算法原理，增加學(xué)生成功建構(gòu)數(shù)學(xué)概念、解決數(shù)學(xué)問題的可能性，進(jìn)而使以學(xué)生發(fā)展為本的教育理念得以實(shí)現(xiàn)。

算法；二分算法；教學(xué)； C++

“現(xiàn)代意義上的‘算法’通常指可以用計(jì)算機(jī)來解決的某一類問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成”[1]。算法實(shí)際上就是解決問題的一種程序性方法，它通常指向某一個(gè)或一類問題，而解決的過程是程序性和構(gòu)造性的。計(jì)算機(jī)解決問題的過程就是對(duì)算法的執(zhí)行過程，但這個(gè)算法必須是計(jì)算機(jī)能理解的語言描述，而我們采取“C++”這種程序設(shè)計(jì)語言就是計(jì)算機(jī)可以理解的語言。

C++是C的一個(gè)擴(kuò)充版本。C是于1978年在貝爾實(shí)驗(yàn)室誕生的。開發(fā)C的目的是為了創(chuàng)造一種可以在多種平臺(tái)上使用的簡單語言（比匯編和機(jī)器代碼簡單…）。后來在80年代早期C被擴(kuò)充為C++用于創(chuàng)造一種面向?qū)ο蟮恼Z言。O（bject，對(duì)象）O（riented，基于）P（rogramming，編程）是一種用類來構(gòu)造程序的編程方式。類型標(biāo)識(shí)符用以區(qū)分main函數(shù)及后繼類。OOP在方法上，C++在實(shí)現(xiàn)上使編寫極為復(fù)雜的圖形應(yīng)用環(huán)境（例如Windows,Macintosh…）成為可能。

以下我們以一個(gè)二分查找法實(shí)例探討如何在C++中應(yīng)用算法教學(xué)：

二分法的概念：一般地，對(duì)于函數(shù)f(x),如果存在實(shí)數(shù)c,當(dāng)x=c是f(c)=0,那么把x=c叫做函數(shù)f(x)的零點(diǎn)。解方程即要求f(x)的所有零點(diǎn)。先找到a、b，使f(a)，f(b)異號(hào)，說明在區(qū)間(a,b)內(nèi)一定有零點(diǎn)，然后求f[(a+b)/2],現(xiàn)在假設(shè)f(a)＜0,f(b)>0,a＜b如果f[(a+b)/2]=0，該點(diǎn)就是零點(diǎn)，如果f[(a+b)/2]＜0，則在區(qū)間（(a+b)/2，b)內(nèi)有零點(diǎn)，按上述方法在求該區(qū)間中點(diǎn)的函數(shù)值，這樣就可以不斷接近零點(diǎn)如果f[(a+b)/2]】>0，同上通過每次把f(x)的零點(diǎn)所在小區(qū)間收縮一半的方法，使區(qū)間的兩個(gè)端點(diǎn)逐步迫近函數(shù)的零點(diǎn)，以求得零點(diǎn)的近似值，這種方法叫做二分法。由于計(jì)算過程的具體運(yùn)算復(fù)雜，但每一步的方式相同，所以可通過編寫程序來運(yùn)算。

假如有一組數(shù)為3，12，24，36，55，68，75，88要查給定的值24.可設(shè)3個(gè)變量front，mid，end分別指向數(shù)據(jù)的上界，中間和下界，mid=（front+end）/2。

1）開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因?yàn)閙id>x，故應(yīng)在前半段中查找。

2）令新的end=mid-1=2，而front=0不變，則新的mid=1。此時(shí)x>mid，故確定應(yīng)在后半段中查找。

3）令新的front=mid+1=2，而end=2不變，則新的mid=2，此時(shí)a[mid]=x，查找成功。

如果要查找的數(shù)不是數(shù)列中的數(shù)，例如x=25，當(dāng)?shù)谌闻袛鄷r(shí)，x>a[mid]，按以上規(guī)律，令front=mid+1，即front=3，出現(xiàn)front>end的情況，表示查找不成功。

例：在有序的有N個(gè)元素的數(shù)組中查找用戶輸進(jìn)去的數(shù)據(jù)x。

算法如下：

1）確定查找范圍front=0，end=N-1，計(jì)算中項(xiàng)mid（front+end）/2。

2）若a[mid]=x或front>=end，則結(jié)束查找；否則，向下繼續(xù)。

3）若a[mid]＜x,說明待查找的元素值只可能在比中項(xiàng)元素大的范圍內(nèi)，則把mid+1的值賦給front，并重新計(jì)算mid，轉(zhuǎn)去執(zhí)行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項(xiàng)元素小的范圍內(nèi)，則把mid-1的值賦給end，并重新計(jì)算mid，轉(zhuǎn)去執(zhí)行步驟2。

代碼：

總之，在信息技術(shù)創(chuàng)設(shè)的數(shù)學(xué)學(xué)習(xí)環(huán)境中，操作、觀察、試驗(yàn)、發(fā)現(xiàn)等過程變得具體而清晰，通過實(shí)例可以讓抽象的數(shù)學(xué)算法解決一些生活中的實(shí)際問題，學(xué)生就會(huì)在輕松又愉快的環(huán)境中學(xué)會(huì)，沒有盲目填鴨之感。還能幫助他們從具體的現(xiàn)象和事物中，獲得對(duì)事物之間關(guān)系的認(rèn)識(shí)，這是一種受益終生的能力。

[1]人民教育出版社、課程教材研究所.普通高中課程標(biāo)準(zhǔn)實(shí) 驗(yàn)教科書（A版）數(shù)學(xué)3.第1版.人民教育出版社，2004，5.

[2]C++面向?qū)ο笈cVisualC++程序設(shè)計(jì)案例教程.北京大學(xué)出版社，2009，3.

TP393

A

1674-6708（2010）22-0210-01