4.9數(shù)組常用算法-專題輔導(dǎo)課件

C程序設(shè)計(jì)專題輔導(dǎo)課

算法基礎(chǔ)

內(nèi)容提要：算法(algorithm)的概念算法的表達(dá)典型算法及其實(shí)現(xiàn)—排序查找其它算法一、算法的概念1.1算法是什么？1.2算法的五個(gè)要素1.3簡(jiǎn)單算法－程序的例子1.1算法是什么？算法：解決特定類型問(wèn)題的方法和步驟著名的Wirth公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序1.1算法是什么？（續(xù)）算法程序邏輯描述解決問(wèn)題的思想方法：步驟描述用某語(yǔ)言表達(dá)的算法過(guò)程：指令集合問(wèn)題解決問(wèn)題的數(shù)據(jù)表示（數(shù)據(jù)結(jié)構(gòu)）1.2算法的五個(gè)要素確定性：對(duì)同一個(gè)算法，相同的輸入應(yīng)該得到相同的輸出，不會(huì)因?yàn)椴煌臋C(jī)器和不同時(shí)間運(yùn)行而不同有窮性：算法中的步驟應(yīng)該是有限的，否則計(jì)算機(jī)就會(huì)永遠(yuǎn)無(wú)休止地執(zhí)行程序有效性：算法中的每一個(gè)步驟都應(yīng)該能被有效地執(zhí)行，并應(yīng)能得到一個(gè)明確的結(jié)果（大象裝入冰箱的問(wèn)題）輸入：有零個(gè)或多個(gè)輸出：有一個(gè)或多個(gè)

1.3簡(jiǎn)單算法－程序的例子歐幾里德（Euclid）算法：求兩個(gè)正整數(shù)A和B的最大公約數(shù)計(jì)算過(guò)程舉例：設(shè)A=18B=30①A=30B=18②C=A%B=12③A=18B=12④C=A%B=6⑤A=12B=6⑥C=A%B=0⑦最大公約數(shù)就是B=6第一步：比較A和B這兩個(gè)數(shù)：A設(shè)置為較大的數(shù)，B為較小的數(shù)；第二步：A除以B，得到余數(shù)C；第三步：如果C等于0，則最大公約數(shù)就是B，算法結(jié)束；否則將B賦值給A，C賦值給B；第四步：重復(fù)進(jìn)行第二步、第三步。int

Euclid(inta,intb){intc;

if(a<b){c=a;a=b;b=c;}

while(c=a%b){a=b;b=c;}returnb;}二、算法的表達(dá)2.1用自然語(yǔ)言描述算法2.2用流程圖描述算法2.3用偽代碼描述算法2.1用自然語(yǔ)言描述算法問(wèn)題：判斷一個(gè)正整數(shù)n是否為素?cái)?shù)的算法。算法描述一：將n作為被除數(shù)，用2到n平方根的各個(gè)整數(shù)輪流去除，如果都不能整除，則n是素?cái)?shù)；否則n不是素?cái)?shù)。算法描述二：第一步：輸入n的值,計(jì)算n的平方根m；第二步：j=2(用j去除n)；第三步：n被j除，得到余數(shù)a；第四步：如果a==0，表示n能被j整除，

顯示信息“n不是素?cái)?shù)”，算法結(jié)束；

否則進(jìn)入下一步；第五步：將j加1送回給j；第六步：如果j<=m,則跳到第三步執(zhí)行；

否則顯示“n是素?cái)?shù)”的信息，算法結(jié)束。2.2用流程圖描述算法2.3用偽代碼描述算法int

prime(intn){m=n的開(kāi)方;for(j=2;j<=m;j++){if(n被j整除)

break;}if(j>m)return1;/*是素?cái)?shù)*/elsereturn0;

/*不是素?cái)?shù)*/}歐幾里德（Euclid）算法：int

Euclid(inta,intb){if(a<b

)交換a和b;c=

a除以b的余數(shù);while(c!=0){a=b;b=c;c=

a除以b的余數(shù);}

returnb;

/*最大公因子*/}三、典型算法及其實(shí)現(xiàn)3.1排序算法

3.2查找算法

3.3常用算法舉例

3.1排序算法1、選擇排序2、冒泡排序3、插入排序4、*歸并排序問(wèn)題：給定n個(gè)元素的數(shù)組a，對(duì)其中的元素從小到大排序，結(jié)果仍然在數(shù)組a中。排序算法－選擇排序35281設(shè)n=5；5個(gè)數(shù)是：35281(1)15283(2)2583(3)385(4)58排序算法－冒泡排序35281設(shè)n=5；5個(gè)數(shù)是：35281(1)3

2

5

1

8

(2)2

3

1

5

8

(3)2

1358

(4)1

2

358冒泡排序(偽代碼算法)voidBubbleSort(inta[],intn){

for(end=n-1;end>0;end--){

for(i=0;i<end;i++)if(

a[i]>a[i+1]){交換a[i]和a[i+1];}}

}

Entern:5Enter10integers:35281Aftersorted:12358排序算法－插入排序void

InsertionSort(inta[],intN){

intj,P;

int

Tmp;

for(P=1;P<N;P++){

Tmp=a[P];/*下一個(gè)元素*/

for(j=P;j>0&&a[j-1]>Tmp;j--) a[j]=a[j-1]; /*前面已排序的部分元素后移，在合適地方的給新元素留出位置*/ a[j]=Tmp;/*新來(lái)元素放入合適的位置*/}/*for-P循環(huán)結(jié)束*/}排序算法－插入排序35281設(shè)n=5；5個(gè)數(shù)是：35281(1)3(2)3

5(3)23

5(4)23

5

8(5)123

5

8

1、合并兩個(gè)有序序列：1132426215273812AptrBptrCptrAptrCptrBptrCptr排序算法－歸并排序void

MSort(intA[],int

TmpArray[],intLeft,intRight){

intCenter;

if(Left<Right){/*還有元素需要排序*/ Center=(Left+Right)/2;

MSort(A,TmpArray,Left,Center);

MSort(A,TmpArray,Center+1,Right);

Merge(A,TmpArray,Left,Center+1,Right);}}void

Mergesort(intA[],intN){

int

TmpArray[MAXSIZE];/*臨時(shí)工作空間*/

MSort(A,TmpArray,0,N-1);

}2、遞歸歸并排序算法/*Lpos=左半邊起始位置,Rpos=右半邊起始位置*/void

Merge(intA[],int

TmpArray[],int

Lpos,int

Rpos,int

RightEnd){

inti,LeftEnd,NumElements,TmpPos;

LeftEnd=Rpos-1;

TmpPos=Lpos;

NumElements=RightEnd-Lpos+1;

while(Lpos<=LeftEnd&&Rpos<=RightEnd)/*mainloop*/

if(A[Lpos]<=A[Rpos])

TmpArray[TmpPos++]=A[Lpos++];

else

TmpArray[TmpPos++]=A[Rpos++];

while(Lpos<=LeftEnd)/*Copyrestoffirsthalf*/

TmpArray[TmpPos++]=A[Lpos++];

while(Rpos<=RightEnd)/*Copyrestofsecondhalf*/

TmpArray[TmpPos++]=A[Rpos++];

for(i=0;i<NumElements;i++,RightEnd--)

/*CopyTmpArrayback*/

A[RightEnd]=TmpArray[RightEnd];}3、迭代（非遞歸）歸并排序算法A0123…………n4n3n2n1…………………………排序算法－歸并排序設(shè)n=6；6個(gè)整數(shù)是：352871(1)352871(2)3

5

28

17

(3)23

58

17

(4)123

5

78

352817(1)352

871(2)3

5

2

87

1

(3)3

5

2

8

7

1(3’)3

5

2

78

1(2’)23

5

178(1’)123

5

78

迭代算法示例：遞歸算法示例：3.2查找算法1、順序查找2、二分查找3、二分查找推廣－非線性方程的根問(wèn)題：給定n個(gè)元素的數(shù)組a，查找某元素x是否在數(shù)組a中。如果在，返回該元素在數(shù)組中的下標(biāo)，否則返回-1。順序查找——從列表的第一個(gè)數(shù)據(jù)（或叫做元素）開(kāi)始，如果給定的數(shù)據(jù)和表中的數(shù)據(jù)匹配時(shí)，查找過(guò)程結(jié)束，給出這個(gè)數(shù)據(jù)所在表中的位置（下標(biāo)）。3.2查找算法－順序查找int

Find(inta[],intn,intx){inti;/*n個(gè)元素存放在a[1]-a[n]中*/a[0]=x;/*“哨兵”*/

for(i=n;a[i]!=x;--i);returni;}int

Find(inta[],intn,intx){inti;

/*n個(gè)元素存放在a[0]-a[n-1]中*/

for(i=0;a[i]!=x&&i<n;++i);returni;}二分查找——也叫折半查找。比較列表處于一半（中間）位置的數(shù)據(jù)是否與要查找的數(shù)x相同，相同則結(jié)束查找，否則判斷是在前半部分還是后半部分（根據(jù)列表的排序確定的），然后繼續(xù)同樣的查找過(guò)程。

查找不成功的條件是查找區(qū)間已經(jīng)<=0。3.2查找算法－二分查找二分查找要求數(shù)據(jù)已經(jīng)排序。二分查找比順序查找快得多！3.2二分查找算法一個(gè)有點(diǎn)類似的問(wèn)題－－猜價(jià)格游戲：保證在較短時(shí)間內(nèi)猜出一件商品的價(jià)格（假設(shè)給定價(jià)格區(qū)間[10,1000]元,且是整數(shù)）。條件：當(dāng)報(bào)出一個(gè)價(jià)格時(shí)，系統(tǒng)提示：高了、低了或正確。3.2二分查找算法二分查找算法（自然語(yǔ)言描述）：假設(shè)數(shù)組A的當(dāng)前查找區(qū)間的下標(biāo)為[low,high]，查找元素為x；

(1)若high<low，查找失敗，算法結(jié)束；否則取區(qū)間中間下標(biāo)：mid=(low+high)/2;(2)若x<A[mid]，x在[low,high]的左半?yún)^(qū)，則調(diào)整新區(qū)間邊界：low不變,high=mid-1，轉(zhuǎn)(1)；(3)若x>A[mid]，x在[low,high]的右半?yún)^(qū)，則調(diào)整新區(qū)間邊界：low=mid+1,high不變，轉(zhuǎn)(1)；(4)若x==A[mid]，則找到，算法結(jié)束。int

BiSearch(intx,intA[],intn){/*n個(gè)元素存放在A[1]—A[n]*/

int

low,high,mid；low=1;high=n;while(low<=high){mid=(low+high)/2;if(x<A[mid])high=mid-1;/*x在左半?yún)^(qū)*/elseif(x>A[mid])low=mid+1;/*x在右半?yún)^(qū)*/elsebreak;/*找到！*/}if(low<=high)returnmid;elsereturn0;}

3.2二分查找程序3.2二分查找推廣－非線性方程求根設(shè)有非線性方程：

f(x)=0其中f(x)在[a,b]區(qū)間內(nèi)連續(xù)且f(a)f(b)<0。因而f(x)在[a,b]區(qū)間內(nèi)至少有一個(gè)實(shí)根x0，即：f(x0)=0。寫(xiě)一個(gè)程序求f(x)在[a,b]區(qū)間內(nèi)的一個(gè)近似實(shí)根。結(jié)束條件：|f(x)|<ε

或b-a<ε二分法求非線性方程的根二分法求根（自然語(yǔ)言描述）：假設(shè)f(x)在[a,b]內(nèi)連續(xù)，且f(a)f(b)<0，給定誤差ε；

(1)若b-a<ε,返回x0=(a+b)/2作為近似根，算法結(jié)束；否則取區(qū)間中點(diǎn)m=(a+b)/2;若f(m)=0,返回x0=m,算法結(jié)束；(2)若f(a)f(m)>0，在[m,b]內(nèi)必有根，則調(diào)整新區(qū)間邊界：b不變,a=m，轉(zhuǎn)(1)；(3)若f(a)f(m)<0，在[a,m]內(nèi)必有根，則調(diào)整新區(qū)間邊界：a不變,b=m，轉(zhuǎn)(1)；double

BiRoot(doublex,double

a,doubleb,doubleeps){/*求值函數(shù)doublef(doublex)需要另外定義*/ doublemid,fm,fa=f(a),fb=f(b);

if(fa==0.)returna;if(fb==0.)returnb;

if(fa*fb>0.){FatalError(“Fail”);return0.;}while(b-a>eps){mid=(b+a)/2;fm=f(mid);if(fm)==0.)returnmid;/*找到一個(gè)根*/elseif(fm*fa>0.){a=m;fa=fm;}/*留右半?yún)^(qū)*/else{b=m;fb=fm;}/*留左半?yún)^(qū)*/}}

3.2二分法求根3.3常用算法舉例例1：輸入n（2≤n≤5，程序不需要對(duì)此范圍進(jìn)行判斷），再輸入n個(gè)整數(shù)保存到數(shù)組a中，通過(guò)循環(huán)查找n個(gè)數(shù)中是否有重復(fù)的數(shù)，如果有則輸出Yes，否則輸出No。

要求在循環(huán)過(guò)程中，任何兩個(gè)數(shù)的比較次數(shù)不得超過(guò)1次（比如對(duì)a[0]與a[1]比較后接下去又對(duì)a[1]與a[0]比較是不符合要求的），并且要求一旦找到有數(shù)重復(fù)則立即結(jié)束循環(huán)。

－－

08年夏考題

#include<stdio.h> voidmain() {inta[5],i,j,n;

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=0;i<=n-2;i++){ for((1);j<=n-1;j++){

if(a[i]==a[j])(2); } if((3))

break; } if((4))

puts("No"); else

puts("Yes");

}j=i+1breakj<=n-1i==n-1或i>=n-1或i>n-23.3常用算法舉例例2：函數(shù)f(A,…,x)有三個(gè)參數(shù),它們分別是已排序(升序)的數(shù)組A、整數(shù)n(A的當(dāng)前元素個(gè)數(shù))以及x(要插入到A中的整數(shù))。函數(shù)f(…)的功能是把x插入A中，而A仍然保持升序，但n增加了1。例如,A的原來(lái)5個(gè)元素是(2,4,6,8,10),n=5,x=1,程序運(yùn)行結(jié)束后的輸出是1#2#4#6#8#10#。請(qǐng)完成下面程序。

－－06年考題

#include<stdio.h>voidfintA[],int*n,intx){inti;i=__(1)__;while((i>0)&&(x<A[i-1])){__(2)__; i--;}

A[i]=x;(*n)++;}voidmain(){

inti,A[10]={2,4,6,8,10},n=5,x=1;f(______(3)_______);

for(i=0;i<n;i++)

printf("%d#",A[i]);}*nA[i]=A[i-1];A,&n,x3.3常用算法舉例例3：數(shù)組元素循環(huán)后移問(wèn)題一個(gè)數(shù)組中存有n（1<=n<=100）個(gè)整數(shù)，在不允許使用另外數(shù)組的前提下，將每個(gè)數(shù)順序向后移m（m>=0）個(gè)位置（最后m個(gè)數(shù)循環(huán)移至最前面的m個(gè)數(shù)）。輸入n、m及n個(gè)整數(shù)，輸出循環(huán)后移m位以后的n個(gè)整數(shù)。輸入：62123456輸出：561234

數(shù)組元素循環(huán)后移問(wèn)題（續(xù)）1．問(wèn)題分析輸入的n個(gè)整數(shù)可以放在一個(gè)一維數(shù)組中，循環(huán)右移一位的操作重復(fù)進(jìn)行m次即可。這種做法的數(shù)據(jù)移動(dòng)次數(shù)大約是m(n+1)次。2．要點(diǎn)A）“循環(huán)右移一位的操作重復(fù)進(jìn)行m次”，B）m可以處理成小于n的數(shù)，以減少工作量。當(dāng)m>n時(shí)，可以用m%n代替m，效果相同。但移動(dòng)次數(shù)大約是(m%n)*(n+1)次。

#include<stdio.h>voidshift(intarray[],intn){

inti,array_end;

array_end=array[n-1];

for(i=n-1;i>0;i--)/*n個(gè)元素循環(huán)位移1位*/

array[i]=array[i-1];

array[0]=array_end;}voidmain(){intnumber[100],n,m,i;……/*輸入*/m%=n;/*當(dāng)m大于等于n時(shí)轉(zhuǎn)化成等價(jià)的小于n的數(shù)*/for(i=0;i<m;i++)

shift(number,n);/*n個(gè)元素循環(huán)位移1位*/……

/*輸出*/}數(shù)組元素循環(huán)后移問(wèn)題（續(xù)）思考1：如果修改題目要求，允許使用另外一個(gè)大小為m（假設(shè)n>m>0）數(shù)組，則如何提高程序效率？

012345234501思考2：不改變題目的任何限定(即不允許使用另外數(shù)組)，能否設(shè)計(jì)一種移動(dòng)次數(shù)不超過(guò)(n+gc)的方法？[gc是最大公約數(shù)]

例：n=6,m=4gc=2趟每趟移動(dòng)n/gc=3個(gè)數(shù)0tmp:240voidshift_m(intarray[

],intn,intm){

inti,tmp[M];

/*M是>=m的常數(shù)*/

for(i=n-1;i>=n-m;i--)/*復(fù)制保留最后m個(gè)元素*/

tmp[i-n+m