重慶普通高校專升本計(jì)算機(jī)算法整理

1、一、 遞推算法（常用級(jí)數(shù)、數(shù)列求和、二分法、梯形積分法、窮舉法等）1、 常用級(jí)數(shù)、數(shù)列求和例 累加和程序1：應(yīng)用for循環(huán)設(shè)計(jì)/* for循環(huán)求s=1*2+2*3+99*100 */main() long i,s; s=0; for(i=1;i<=99;i+) /* 設(shè)置循環(huán)i=1,2,99 */ s+=i*(i+1); /* 把通項(xiàng)i*(i+1)累加到s中 */printf("1*2+2*3+.+99*100=%ldn",s); /*此處結(jié)果 s 為long，故用 %ld 輸出*/輸出格式符含義：%d 短整形,一般占兩個(gè)字節(jié)，范圍：-3276832767，用于int

2、 ，short int%u 無符號(hào)短整形，一般占兩個(gè)字節(jié)，范圍：065535，用于unsigned int%ld 長(zhǎng)整形,一般占四個(gè)字節(jié)，范圍：-21474836482147483647，用于long，long int%c 字符型，用于char%s 字符串，用于char a%f 單精度浮點(diǎn)型，用于float%lf 雙精度浮點(diǎn)型，用于double程序2： 應(yīng)用while循環(huán)設(shè)計(jì) /* while循環(huán)求s=1*2+2*3+99*100 */main() long i,s; i=1;s=0; while(i<=99) /* 設(shè)置循環(huán)i=1,2,99 */ s+=i*(i+1); /* 把通項(xiàng)i

3、*(i+1)累加到s中 */ i+; printf("1*2+2*3+99*100=%ldn",s);例 代數(shù)和/* 求s=1-1/2+1/3-1/4+-1/100 */main() int k,n;float s=0; for(k=1;k<=100;k+) if(k%2=1) s+=1.0/k; /* 應(yīng)用分支實(shí)現(xiàn)符號(hào)一正一負(fù) */ else s-=1.0/k; printf("s=%9.6f",s);例 階乘計(jì)算/* 循環(huán)累乘求階乘n! */main()int i,n;long t;scanf("%d",&n); /

4、* 輸入 n 的值 */t=1; /* 積變量t賦初值1 */for(i=1;i<=n;i+) t=t*i; /* 循環(huán)變量i累乘到t，體現(xiàn)階乘運(yùn)算 */printf("%d!=%ldn",n,t);2、 二分法/折半法（只能對(duì)有序數(shù)列進(jìn)行查找）基本思想：設(shè)n個(gè)有序數(shù)（從小到大）存放在數(shù)組a1-an中，要查找的數(shù)為x。用變量min、max、mid 分別表示查找數(shù)據(jù)范圍的底部（數(shù)組下界）、頂部（數(shù)組的上界）和中間，mid=(max+min)/2，折半查找的算法如下： （1）x=a(mid)，則已找到退出循環(huán)，否則進(jìn)行下面的判斷； （2）x<a(mid)，x必定落在

5、min和mid-1的范圍之內(nèi)，即max =mid-1； （3）x>a(mid)，x必定落在mid+1和max的范圍之內(nèi)，即min =mid+1； （4）在確定了新的查找范圍后，重復(fù)進(jìn)行以上比較，直到找到或者min <= max。將上面的算法寫成如下程序：void main() int a10,mid,min,max,x,i,find; printf("please input the array:n"); for(i=0;i<10;i+) scanf("%d",&ai); printf("please input th

6、e number you want find:n"); scanf("%d",&x); printf("n"); min=0; max=9; find=0; /* find用于標(biāo)記是否找到x */ while(min<=max&&find=0) mid=(max+min)/2; /* 計(jì)算中間 */ if(x=amid) find=1; /* 找到 find=1 */ break; /* 跳出循環(huán) */ else if( x < amid ) max=mid-1; else min=mid+1; if (fi

7、nd=1) printf("the number is found the no %dn",mid); else printf("the number is not foundn");3、 梯形積分法(這個(gè)你應(yīng)該能看懂什么意思，我看不明白。呵呵呵！)#include"math.h"main() int i,n=1000; float a,b,h,t1,t2,s,x; printf("請(qǐng)輸入積分限a,b:"); scanf("%f,%f",&a,&b); h=(b-a)/n; fo

8、r(s=0,i=1;i<=n;i+) x=a+(i-1)*h; t1=exp(-x*x/2); t2=exp(-(x+h)*(x+h)/2); s+=(t1+t2)*h/2; /* 梯形面積累加 */ printf("梯形法算得積分值:%f.n",s);其實(shí)也不用這么麻煩，比較08年真題，他給出了近似公式，這樣就只相當(dāng)于求級(jí)數(shù)了。4、 窮舉法窮舉法是最簡(jiǎn)單也是最低率的，它是指試用所有可能的情況，如下題解方程：8y+4x+y*y=41 x*x+7y+10=2 (0<x<50, 10<y<100)基本思想是用兩個(gè)for循環(huán)void main() i

9、nt x,y,find; find=0; for( x=0; x<50; x+ ) for( y=10; y<100; y+ ) if( 8*y + 4*x + y*y = 41&&x*x + 7*y + 10 = 2 ) find=1; printf("x=%dty=%dn",x,y); if(find=0) printf("x,y not exist");二、 排序算法（選擇法、冒泡法）1、 選擇法排序（升序）基本思想： 1）對(duì)有n個(gè)數(shù)的序列（存放在數(shù)組a(n)中），從中選出最小的數(shù)，與第1個(gè)數(shù)交換位置； 2）除第1 個(gè)數(shù)

10、外，其余n-1個(gè)數(shù)中選最小的數(shù)，與第2個(gè)數(shù)交換位置； 3）依次類推，選擇了n-1次后，這個(gè)數(shù)列已按升序排列。程序代碼如下：/* 輸入10個(gè)整數(shù)，升序排列輸出*/main() int i,j,imin,s,a10; printf("input 10 numbers:n"); for(i=0;i<10;i+) scanf("%d",&ai); for(i=0;i<9;i+) imin=i; for(j=i+1;j<10;j+) if(aimin>aj) /* if(aimin<aj) 降序排列*/ imin=j; if(

11、i!=imin) s=ai; ai=aimin; aimin=s; printf("%dn",ai); 2、 冒泡法排序（升序）基本思想：(將相鄰兩個(gè)數(shù)比較，小的調(diào)到前頭) 1）有n個(gè)數(shù)（存放在數(shù)組an中），第一趟將每相鄰兩個(gè)數(shù)比較，小的調(diào)到前頭，經(jīng)n-1次兩兩相鄰比較后，最大的數(shù)已“沉底”，放在最后一個(gè)位置，小數(shù)上升“浮起”； 2）第二趟對(duì)余下的n-1個(gè)數(shù)（最大的數(shù)已“沉底”）按上法比較，經(jīng)n-2次兩兩相鄰比較后得次大的數(shù)； 3）依次類推，n個(gè)數(shù)共進(jìn)行n-1趟比較，在第j趟中要進(jìn)行n-j次兩兩比較。程序段如下：main() int a10; int i,j,t; prin

12、tf("input 10 numbers:n"); for(i=0;i<10;i+) scanf("%d",&ai); /* 降序 if(ai<ai+1) */ printf("n"); for(j=0;j<9;j+) for(i=0;i<9-j;i+) if(ai>ai+1) t=ai; ai=ai+1; ai+1=t; printf("the sorted numbers:n"); for(i=0;i<10;i+) printf("%dn",ai)

13、;三、 查找算法（順序查找、折半查找）1、 順序查找查找是在程序設(shè)計(jì)中最常用到的算法之一，假定要從n個(gè)整數(shù)中查找x的值是否存在，最原始的辦法是從頭到尾逐個(gè)查找，這種查找的方法稱為順序查找。程序如下：main() void bi_search(int a,int n,int x); /* 被調(diào)函數(shù)在main函數(shù)之后，需說明被調(diào)函數(shù)*/ int a100,x,i,n=15; printf("input the numbers:n"); for(i=0;i<n;i+) scanf("%d",&ai); printf("input x:n

14、"); scanf("%d",&x); bi_search(a,n,x);void bi_search(int a,int n,int x) int i=0,find=0; while(i<n) if(x=ai) printf("find:%d,it is a%d",x,i); printf("n"); find=1; i+; if(!find) printf("%d not been found.",x); printf("n");2、 折半查找四、 有序數(shù)列的插入、刪

15、除操作把一個(gè)整數(shù)按大小順序插入已排好序的數(shù)組中。 為了把一個(gè)數(shù)按大小插入已排好序的數(shù)組中， 應(yīng)首先確定排序是從大到小還是從小到大進(jìn)行的。設(shè)排序是從大到小進(jìn)序的， 則可把欲插入的數(shù)與數(shù)組中各數(shù)逐個(gè)比較， 當(dāng)找到第一個(gè)比插入數(shù)小的元素i時(shí)，該元素之前即為插入位置。然后從數(shù)組最后一個(gè)元素開始到該元素為止，逐個(gè)后移一個(gè)單元。最后把插入數(shù)賦予元素i即可。如果被插入數(shù)比所有的元素值都小則插入最后位置。插入操作程序代碼如下：main() int i,j,p,q,s,n,a11=127,3,6,28,54,68,87,105,162,18;/* 先用選擇排序法 排列數(shù)組 */ for(i=0;i<10;

16、i+) p=i; q=ai; for(j=i+1;j<10;j+) if(q<aj) p=j; q=aj; if(p!=i) s=ai; ai=ap; ap=s; printf("%d ",ai); printf("ninput number:n"); scanf("%d",&n); for(i=0;i<10;i+) if(n>ai) for(s=9;s>=i;s-) as+1=as; /* 移動(dòng) ai之后所有元素 */ break; ai=n; /* 插入n 到 ai */ for(i=0;i&

17、lt;=10;i+) printf("%d ",ai); printf("n");刪除操作程序代碼如下：main() int i,j,p,q,s,n,a11=127,3,6,28,54,68,87,105,162,18; /* 先用選擇排序法 排列數(shù)組 */ for(i=0;i<10;i+) p=i; q=ai; for(j=i+1;j<10;j+) if(q<aj) p=j; q=aj; if(p!=i) s=ai; ai=ap; ap=s; printf("%d ",ai); printf("ninpu

18、t number:n"); scanf("%d",&n); for(i=0;i<10;i+) if(n=ai) for(s=i;s<=9;s+) as=as+1; break; for(i=0;i<=9;i+) printf("%d ",ai); printf("n");在一個(gè)有序的數(shù)列中找到一個(gè)數(shù)并且刪除它main() int a7=0,1,2,3,5,6,i,k,j; for (k=0;k<6;k+) printf("%d ",ak); printf("n&q

19、uot;); printf("Please input the number to delete: "); scanf("%d",&i); for (k=0;k<6;k+) if (i=ak) for (j=k;j<5;j+) aj=aj+1; break; if (k=6) printf("The number not found"); printf("The sorted is :n"); for (k=0;k<5;k+) printf("%d ",ak);五、 初

20、等數(shù)論問題求解的有關(guān)算法（最大數(shù)、最小數(shù)、最大公約數(shù)、最小公倍數(shù)、素?cái)?shù)等）1、 最大公約數(shù)、最小公倍數(shù)(遞歸算法)分析：求最大公約數(shù)的算法思想：(最小公倍數(shù)=兩個(gè)整數(shù)之積/最大公約數(shù)) (1) 對(duì)于已知兩數(shù)m，n，使得m>n； (2) m除以n得余數(shù)r； (3) 若r=0，則n為求得的最大公約數(shù)，算法結(jié)束；否則執(zhí)行(4)； (4) mn，nr，再重復(fù)執(zhí)行(2)。 例如: 求 m=14 ,n=6 的最大公約數(shù). m n r 14 6 2 6 2 0 void main() int nm,r,n,m,t; printf("please input two numbers:n&quo

21、t;); scanf("%d,%d",&m,&n); nm=n*m; if (m<n) t=n; n=m; m=t; r=m%n; while (r!=0) m=n; n=r; r=m%n; printf("最大公約數(shù):%dn",n); printf("最小公倍數(shù):%dn",nm);2、 最大數(shù)/* 輸入一個(gè)數(shù)組，輸出數(shù)組中最大數(shù) */main() int i,a10,max; for ( i=0; i<10; i+ ) scanf ("%d",&ai); max = a0; f

22、or ( i=0; i<10; i+ ) if ( max < ai ) max = ai; printf ("output max %d.n", max );3、 最小數(shù)/* 輸入一個(gè)數(shù)組，輸出數(shù)組中最小數(shù) */main() int i,a10,min; for ( i=0; i<10; i+ ) scanf ("%d",&ai); min = a0; for ( i=0; i<10; i+ ) if ( min > ai ) min = ai; printf ("output max %d.n"

23、;, min );4、 素?cái)?shù)只能被1或本身整除的數(shù)稱為素?cái)?shù)基本思想：把m作為被除數(shù)，將2 m的平方根 作為除數(shù)，如果都除不盡，m就是素?cái)?shù)，否則就不是。（可用以下程序段實(shí)現(xiàn)）#include "math.h" /*引入數(shù)學(xué)函數(shù)庫*/void main() int m,i,k; printf("please input a number:n"); scanf("%d",&m); k=sqrt(m); /*m 開平方*/ for(i=2;i<k;i+) if(m%i=0) break; if(i>=k) printf(&

24、quot;該數(shù)是素?cái)?shù)"); else printf("該數(shù)不是素?cái)?shù)");掌握判斷素?cái)?shù)的基本方后，打印出1到X間的素?cái)?shù)，1到X間有多少個(gè)素?cái)?shù)，這樣的題也該會(huì)做六、 矩陣的處理（生成、交換及基本運(yùn)算）1、 矩陣的和與轉(zhuǎn)置main() int i,j,m,n,x,y,a45,b45; printf("輸入a矩陣:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("%d",&aij); /* 輸入a矩陣的元素 */ printf("輸入b矩陣:n ")

25、; for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("%d",&bij); /* 輸入b矩陣的元素 */ printf("a矩陣:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%3d",aij); /* 打印a矩陣 */ printf("n"); printf("b矩陣:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf(&quo

26、t;%3d",bij); /* 打印b矩陣 */ printf("n"); printf("a,b矩陣之和:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%4d",aij+bij); /* 計(jì)算并打印a+b的元素 */ printf("n"); printf("a矩陣的轉(zhuǎn)置:n "); for(j=1;j<=4;j+) /* 打印a矩陣的轉(zhuǎn)置 */ for(i=1;i<=3;i+) printf("%4

27、d",aij); printf("n"); 小知識(shí)：%md; m為指定的輸出字段的寬度。如果數(shù)據(jù)的位數(shù)小于m,則左端補(bǔ)以空格，若大于m，則按實(shí)際位數(shù)輸出。例如a=123,b=12345,printf("%4d,%4d",a,b);結(jié)果是：_123，12345 _代表空格。2、 矩陣的積求a,b矩陣的積前提是我們要在數(shù)學(xué)上會(huì)矩陣的積main() int i,j,k,d,a45,b53; printf("輸入a矩陣:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("

28、;%d",&aij); /* 輸入a矩陣的元素 */ printf("輸入b矩陣:n "); for(i=1;i<=4;i+) for(j=1;j<=2;j+) scanf("%d",&bij); /* 輸入b矩陣的元素 */ printf("a矩陣:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%3d",aij); /* 打印a矩陣 */ printf("n"); printf("b矩

29、陣:n "); for(i=1;i<=4;i+) for(j=1;j<=2;j+) printf("%3d",bij); /* 打印b矩陣 */ printf("n"); printf("a,b矩陣之積:n "); for(i=1;i<=3;i+) for(j=1;j<=2;j+) d=0; for(k=1;k<=4;k+) d+=aik*bkj; /* 求和計(jì)算積矩陣元素d(i,j) */ printf("%6d",d); /* 打印a,b積矩陣元素d */ printf("n"); 七、 遞歸算法（階乘、最大公約數(shù)等）1、 階乘模塊化機(jī)制及函數(shù)（過程）設(shè)計(jì)與使用如子程序、函數(shù)、過程、類