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

王民川

鄭州廣播電視大學，河南鄭州 450007

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

王民川

鄭州廣播電視大學，河南鄭州 450007

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

算法；二分算法；教學； C++

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

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

以下我們以一個二分查找法實例探討如何在C++中應用算法教學：

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

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

1）開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因為mid>x，故應在前半段中查找。

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

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

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

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

算法如下：

1）確定查找范圍front=0，end=N-1，計算中項mid（front+end）/2。

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

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

代碼：

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

[1]人民教育出版社、課程教材研究所.普通高中課程標準實 驗教科書（A版）數(shù)學3.第1版.人民教育出版社，2004，5.

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

TP393

A

1674-6708（2010）22-0210-01