03算法案例1.算法案例

一、輾轉(zhuǎn)相除法（歐幾里得算法）

（1）算法步驟

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

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

第三步，.

第四步，若,則m，n的最大公約數(shù)等于m；否則，

返回第二步。

（2）程序語句

INPUT

m,n

DO

r=mMODn

m=n

n=r

LOOPUNTIL

r=0

PRINT

m

END

2.更相減損術(shù)

步驟：第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步。

第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。

二、秦九韶算法

秦九韶算法是關(guān)于求高次多項(xiàng)式的函數(shù)值的一個(gè)算法，其過程如下：

把一個(gè)n次多項(xiàng)式改寫成如下形式：

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

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

；

；

這樣，求n次多項(xiàng)式的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值，上述方法稱為秦九韶算法。

（1）算法步驟

第一步，輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)和x的值。

第二步的值初始化為，將i的值初始化為n-1.

第三步，輸入i次項(xiàng)的系數(shù).

第四步：

第五步，判斷i是否大于或等于0.若是，則返回第三步；否則輸出多項(xiàng)式的值v.

(2)程序語句

INPUT“n=”；n

INPUT“an=”；a

INPUT“x=”；x

v=a

i=n-1

WHILEi＞=0

PRINT“i=”；i

INPUT“ai=”；a

v=v*x+a

i=i-1

WEND

PRINT

v

END詳解：無2.進(jìn)位制

（1）進(jìn)位制是人們?yōu)榱擞?jì)算和運(yùn)算方便而約定的記數(shù)系統(tǒng)，約定滿二進(jìn)一，就是二進(jìn)制；滿十進(jìn)一，就是十進(jìn)制；滿十二進(jìn)一，就是十二進(jìn)制；等等。也就是說，“滿幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾。

（2）一般地，若k是一個(gè)大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式

（3）將k進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的方法

只要將上式等號(hào)右面邊的值計(jì)算出來，就得到相應(yīng)的十進(jìn)制數(shù)。

（4）將十進(jìn)制數(shù)轉(zhuǎn)換為k進(jìn)制數(shù)一般用除k取余法，其方法是用k連續(xù)去除