2022年算法程序 .pdf

《2022年算法程序 .pdf》由会员分享，可在线阅读，更多相关《2022年算法程序 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法程序 by Jetway from hdu_cloud 随便编了几个程序，主要包括：插入排序，shell排序，快速排序，冒泡排序，递归型、迭代型、自然归并排序，大数相乘， 01 背包问题的贪婪算法，矩阵链相乘的算法插入排序：#include #include using namespace std; #define N 100 #define random(x) (rand()%x) void main() int aN; int n,m,key; cout输入实验次数：n; while(n-) cout输入数组个数：m; cout原始数据为： endl; srand(unsigned)t

2、ime(NULL); for(int i=0;im;i+) ai=random(100); coutai= ai ; coutendl; for(int j=1;j0&aikey;i-) ai+1=ai; ai+1 = key; cout插入排序后： endl; for(i=0;im;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - coutai= ai ; coutendl; Shell 排序#include #inc

3、lude #define random(x) (rand()%x) int a100; using namespace std; void main() int add,n,i,j,t,k; cout输入数组个数：n; srand(unsigned) time(NULL); cout原始数据： endl; for(i=0;in;i+) ai=random(100); coutai= ai ; cout0;add/=2) for(j=add;j=0&t*(a+k);k-=add) *(a+k+add) = *(a+k); *(a+k+add) = t; coutshell 排序后数据： endl

4、; for(i=0;in;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - coutai= ai ; coutendl; 快速排序#include #include #define random(x) (rand()%x) int a100; using namespace std; void swap(int s,int left,int right) int t; t=*(s+left); *(s+left)=*(s

5、+right); *(s+right)=t; int partition(int s,int left,int right) int p = sright; int mid = left; int t; for(int i = left;iright;i+) if(si=sright) swap(s,i,mid); mid+; swap(s,mid,right); return mid; void qsort(int s,int left,int right) if(leftright) int pi = partition(s,left,right); 名师资料总结 - - -精品资料欢迎下

6、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - qsort(s,left,pi-1); qsort(s,pi+1,right); void main() int i,n; cout输入数组个数：n; srand(unsigned)time(NULL); cout原始数据为：endl; for(i=0;in;i+) ai=random(100); coutai = ai ; coutendl; qsort(a,0,n-1); cout快速排序后数据为：endl; f

7、or(i=0;in;i+) coutai = ai ; coutendl; 冒泡排序#include #include #define random(x) (rand()%x) int a100; using namespace std; void main() int n,i,j,t; cout请输入数组个数：n; srand(unsigned)time(NULL); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - cout

8、原始数据为：endl; for(i=0;in;i+) ai = random(100); coutai = ai ; coutendl; for(i=1;i=i;j-) if(*(a+j)*(a+j-1) t=*(a+j); *(a+j)=*(a+j-1); *(a+j-1)=t; cout冒泡排序后数据为：endl; for(i=0;in;i+) coutai = ai ; coutendl; 递归型归并排序#include #include #include #define arrLen 10 #define random(x) (rand()%x) int r100; using nam

9、espace std; / 相邻有序段合并void Merge_two_Arr(int a,int s,int m,int n) int i,j,k ; k = s; i = s; j = m+1 ; while(i=m & j=n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - if(ai=aj ) rk+ = ai+ ; else rk+ = aj+ ; while(i=m) rk+=ai+; while(j=n) rk

10、+=aj+; for(i = 0; in+1;i+) ai = ri; / 合并排序总函数void MergeSort(int a,int s, int n) if(sn) int m = (s+n)/2 ; MergeSort(a,s,m); MergeSort(a,m+1,n) ; Merge_two_Arr(a,s,m,n); void main() cout# 递归归并排序：#endl; int i,aarrLen; srand( (unsigned)time( NULL ) ); cout原始数据： endl; for(i = 0;iarrLen;i+) ai = random(10

11、0); coutai= ai ; coutendl; MergeSort(a,0,9); cout归并排序后数据：endl; for(i = 0;iarrLen;i+) coutai= ai ; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 迭代型归并排序#include #include #include #define arrLen 10 #define random(x) (rand()%x) in

12、t r100; using namespace std; / 相邻有序段合并void Merge_two_Arr(int a,int r,int s,int m,int n) int i,j,k ; k = s; i = s; j = m+1 ; while(i=m & j=n) if(ai=aj ) rk+ = ai+ ; else rk+ = aj+ ; while(i=m) rk+=ai+; while(j=n) rk+=aj+; / 一遍二路合并void MergePass(int a,int r,int n,int len) int s,e; s = 0; while(s+len=n

13、) e = n-1; Merge_two_Arr(a,r,s,s+len-1,e); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - s = e+1; if(sn) for(;sn;s+) rs = as; / 合并排序总函数void MergeSort(int a, int n) int *p; int len = 1; int f = 0; p=(int *)malloc(sizeof(int)*n); while(len

14、n) if(f) MergePass(p,a,n,len); else MergePass(a,p,n,len); len*=2; f=1-f; if(f) for(f = 0;fn;f+) af = pf; free(p); void main() cout# 迭代归并排序：#endl; int i,aarrLen; srand( (unsigned)time( NULL ) ); cout原始数据： endl; for(i = 0;iarrLen;i+) ai = random(100); coutai= ai ; coutendl; MergeSort(a,arrLen); cout归并

15、排序后数据：endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - for(i = 0;iarrLen;i+) coutai= ai ; coutendl; 自然归并排序#include #include #include #define arrlen 10 #define random(x) (rand()%x) int r100; using namespace std; / 扫描待排数组void ScanTarget

16、(int target, int n, int head, int tail) int i,j=0,k=0; headk=0; k+; for(i=1;itargeti) tailj+=i-1; headk+=i; tailj=n-1; / 求长度；int CountHead(int head) int i(0); while(headi!=-1) i+; return i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - /

17、 void Merge(int c, int d, int l, int m, int r) int i,j,k; i=l; j=m+1; k=l; while(i=m) & (j=r) if( ci m ) for(int q=j; q=r; q+) dk+=cq; else for(int q=i; q=m; q+) dk+=cq; / void MergePass(int x, int y, int s, int a, int b, int m) int i=0; while(i = m-2*s) Merge(x,y,ai,bi+s-1,bi+2*s-1); i=i+2*s; if(i+

18、s m) Merge(x,y,ai,bi+s-1,bm-1); else for(int j=i; jm; j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - for(int k=aj; k=bj; k+) yk=xk; / void MergeSort(int a, int head, int tail, int m) int barrlen; int s=1; while(sm) MergePass(a,b,s,he

19、ad,tail,m); s+=s; MergePass(b,a,s,head,tail,m); s+=s; void main() cout# 归并排序： #endl; int i,aarrlen; int targetarrlen,headarrlen,tailarrlen; int m; for(i=0; iarrlen; i+) headi=-1; taili=-1; srand( (unsigned)time( NULL ) ); cout原始数据： endl; for(i = 0;iarrlen;i+) targeti = random(100); couttargeti= targ

20、eti ; coutendl; ScanTarget(target,arrlen,head,tail); m=CountHead(head); MergeSort(target,head,tail,m); cout归并排序后数据：endl; for(i = 0;iarrlen;i+) couttargeti= targeti ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - coutendl; 大数相乘#include #

21、include #include #include using namespace std; void main() cout% 大数相乘 %endlendl; string x, y; coutx; coutendl; couty; / 以字符串形式读入两个非负的大整数reverse(x.begin(), x.end(); reverse(y.begin(), y.end(); int result55555 = 0; for (int i = 0; i x.size(); +i) for (int j = 0; j y.size(); +j) resulti +j += (xi - 0)

22、* (yj - 0); for (i = 0; i = 10) resulti+1 += resulti/10; resulti %= 10; reverse(result, result + x.size() + y.size(); i = 0; while(resulti = 0 & i x.size()+y.size() +i; cout 相乘结果为： ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - if (i x

23、.size()+y.size() copy(result + i, result+x.size()+y.size(), ostream_iterator(cout); cout endl; else cout 0 endl; coutendlendl; 矩阵链相乘（矩阵链相乘时求出运算次数最少的加括号方法）#include #include #include #include #include #include using namespace std; const int len = 10; void output(int flen + 1, int x, int y) if (x y) re

24、turn ; int k = fxy; if (x = y) cout Ax; else cout ( ; output(f, x, k); output(f, k + 1, y); cout ); void main() cout& 矩阵链相乘 &endlendl; srand(unsigned)time(NULL); int plen + 1 = 0; cout 总共len 个矩阵 , 每个矩阵的维数如下:n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17

25、页 - - - - - - - - - p0 = rand() % 100 + 3; for (int i = 1; i = len ; +i) / 随机生成维数在范围20,300)内的矩阵pi = rand() % 300 + 20; cout A i 的维数为 : pi-1 * pi endl; int mlen+1len+1, flen+1len+1; for (i = 1; i = len; +i) for (int j = i; j = len; +j) if (i = j) mij = 0; else mij = 1 26; / 初始化为足够大的值fij = -1; for (in

26、t step = 2; step = len; +step) for (int i = 1; i len) break; for (int k = i; k = (1 = (1 tmp) mij = tmp; fij = k; cout n 最优的加括号方式为: endl; output(f, 1, len); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - cout endlendl; 贪心法 01 背包问题#includ

27、e #include #define random(x) (rand()%x) using namespace std; /* The 0-1 knapsack problem * arg value - valuei is the value of item i * arg weight - weighti is the weight of item i * arg itemAmout - the amount of items * arg volume - the volume of knapsack */ void swap(float a,int n,int m) float t=*(

28、a+n); *(a+n)=*(a+m); *(a+m)=t; int partition(float s,int left,int right) float p = sright; int mid = left; for(int i = left;iright;i+) if(si=sright) swap(s,i,mid); mid+; swap(s,mid,right); return mid; void qsort(float s,int left,int right) if(leftright) int pi = partition(s,left,right); 名师资料总结 - - -

29、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - qsort(s,left,pi-1); qsort(s,pi+1,right); void knapsack01_tanxin(float value, float weight,float p, int itemAmount, float volume) float sum=0,result=0; for(int i=0;iitemAmount;i+) pi=valuei/weighti; cout

30、pi= pi ; coutendl; qsort(p,0,itemAmount-1); int start = itemAmount-1; while(sum=0) result+=pstart; start-; cout总价值= resultendl; void main() int n; float value100,weight100,p100; float volume=30; cout输入有多少件商品：n; srand(unsigned)time(NULL); cout原始数据： endl; cout容量= volumeendl; for(int i=0;in;i+) valuei

31、= random(100)+1.0; coutvaluei= valuei ; coutendl; for(i=0;in;i+) weighti=random(10)+1.0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - coutweighti= weighti ; coutendl; knapsack01_tanxin(value,weight,p,n,volume); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -