高中數(shù)學(xué)必修3中算法的典型例題的Matlab實(shí)現(xiàn)

劉本虹 申艷玲 鄭艷萍

一、引言

高中數(shù)學(xué)3是高中數(shù)學(xué)必修中的五個(gè)模塊之一，它包括算法初步、統(tǒng)計(jì)和概率三章內(nèi)容。算法是數(shù)學(xué)與其應(yīng)用的重要組成部分，是計(jì)算科學(xué)的重要基礎(chǔ)，是連接解決問(wèn)題方法與計(jì)算機(jī)能夠理解的程序語(yǔ)言之間的橋梁，是現(xiàn)代人必須具有的數(shù)學(xué)修養(yǎng)[1]。Matlab是Mathworks公司開(kāi)發(fā)的用于概念設(shè)計(jì)、算法開(kāi)發(fā)、建模仿真、實(shí)時(shí)實(shí)現(xiàn)的集成環(huán)境。其廣泛運(yùn)用于生物醫(yī)學(xué)工程、圖像信號(hào)處理、信號(hào)分析、電信、時(shí)間序列分析、控制論和系統(tǒng)論等領(lǐng)域[2]。在國(guó)內(nèi)高校數(shù)學(xué)專(zhuān)業(yè)開(kāi)設(shè)的多種課程都涉及到Matlab的應(yīng)用，比如數(shù)學(xué)與應(yīng)用數(shù)學(xué)專(zhuān)業(yè)開(kāi)設(shè)的《數(shù)值分析》《數(shù)學(xué)建模》，信息與計(jì)算科學(xué)專(zhuān)業(yè)開(kāi)設(shè)的《數(shù)值逼近》《數(shù)值代數(shù)》《微分方程數(shù)值解》等，許多課程中的數(shù)值實(shí)驗(yàn)部分都需要用Matlab編程實(shí)現(xiàn)。

對(duì)于本科生來(lái)說(shuō)，開(kāi)始接觸算法的相關(guān)課程不太適應(yīng)。主要原因在于一方面無(wú)法理解算法語(yǔ)；另一方面不太理解程序語(yǔ)言。因此，盡早地讓高中生接觸一些簡(jiǎn)單算法，并把算法用Matlab或Mathematica編程實(shí)現(xiàn)是非常有必要的，可以很好地實(shí)現(xiàn)高中到大學(xué)本科相關(guān)課程銜接。

二、主要內(nèi)容

本節(jié)內(nèi)容主要選取或改編于[1]中出現(xiàn)的典型算例及其編程實(shí)現(xiàn)。

例1.編寫(xiě)程序，使任意輸入的n個(gè)整數(shù)按從大到小的順序輸出。(該例題改編于[1]中第一章的例7)

在Matlab中有現(xiàn)成的命令對(duì)數(shù)的大小進(jìn)行排列，本文為了讓學(xué)生更好地理解算法，從而遵照教材所給的算法分析予以Matlab編程，學(xué)生可以看到運(yùn)算每一步的結(jié)果，加深對(duì)照程序語(yǔ)言的理解與應(yīng)用。

算法分析：

把這n個(gè)數(shù)以向量形式輸入，依次比較各分量的大小，進(jìn)行排序。

以下是比較-1；5；300；3002；-5000；119；-100的大小，且按從大到小的次序輸出。其Matlab程序及運(yùn)行結(jié)果如下。

以下算法案例均來(lái)自[1]中第一章第3節(jié)中的案例。

例2.輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法是一種古老而有效的求兩個(gè)正整數(shù)的最大公因子的算法之一，這種算法是歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法[1]。

算法分析：

第一步：給定兩個(gè)正整數(shù)m，n；

第二步：計(jì)算m除以n所得到的余數(shù)r；

第三步：m=n，n=r；

第四步：若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步。

其Matlab程序如下：

注：Matlab中也有內(nèi)置命令gcd(x,y)可求兩個(gè)正整數(shù)x,y的最大公因子。

例3.更相減損術(shù)

更相減損術(shù)是《九章算術(shù)》中求兩個(gè)數(shù)的最大公約數(shù)的方法，其編程結(jié)構(gòu)類(lèi)似于輾轉(zhuǎn)相除法，唯一區(qū)別是前者做除法，后者做減法。其Matlab程序如下：

分別以m=98，n=63為例，其運(yùn)算結(jié)果如下：

這個(gè)運(yùn)算過(guò)程與[1]第一章第3節(jié)例1所給的運(yùn)算過(guò)程：

98-96=35；63-35=28；35-28=7；28-7=21；21-7=21；21-7=14；14-7=7是一致的。

例4.秦九韶算法

我國(guó)南宋時(shí)期的數(shù)學(xué)家秦九韶(約1202～1261)在《數(shù)書(shū)九章》中對(duì)多項(xiàng)式

f(x)=anxn+an-1xn-1+L+a1x+a0

的求值提出如下算法：

把多項(xiàng)式f(x)改寫(xiě)為：

f(x)=an xn+an-1xn-1+L+a1x+a0

=(anxn-1+an-1xn-2+L+a1)x+a0

=((an xn-2+an-1xn-2+L+a2)x+a1)x+a0

=L

=(L(an x+an-1)x+an-2)x+L+a1)x+a0

求多項(xiàng)式值時(shí)，首先計(jì)算內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即

v1=an x+an-1

然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值

v2=an x+an-2

v3=v2x+an-3

L

vn=vn-1x+a0

這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值。

據(jù)此算法計(jì)算f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8當(dāng)x=5時(shí)的值[1]。

Matlab程序及運(yùn)行結(jié)果如下：

例5.進(jìn)位制

進(jìn)位制是人們?yōu)榱擞?jì)算數(shù)和運(yùn)算而約定的計(jì)數(shù)系統(tǒng)。下面以[1]中的例題：設(shè)計(jì)一個(gè)算法，把k進(jìn)制數(shù)a(共有n位)化為十進(jìn)制數(shù)b。

算法分析：

第一步：輸入a,k,n

第二步：b=0,i=1

第三步：b=b+aiki-1,i=i+1

第四步：判斷i＞n是否成立。若是，執(zhí)行第五步；否則，返回第三步。

第五步：輸出b。

注：ai為k進(jìn)制數(shù)a右數(shù)第i位數(shù)。

下面編程把1011001轉(zhuǎn)換為十進(jìn)制，該例題改編于[1]中第三章第3節(jié)的例5。

三、總結(jié)

本文搜集了數(shù)學(xué)必修3中涉及到的典型算例，結(jié)合教材上的算法分析，用matlab進(jìn)行算法實(shí)現(xiàn)，直觀呈現(xiàn)運(yùn)行結(jié)果，依此希望對(duì)高中生對(duì)數(shù)學(xué)算法的理解有所幫助。