算法原理经典算法实现.docx
- 文档编号:1699982
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:38
- 大小:366.12KB
算法原理经典算法实现.docx
《算法原理经典算法实现.docx》由会员分享,可在线阅读,更多相关《算法原理经典算法实现.docx(38页珍藏版)》请在冰点文库上搜索。
算法原理经典算法实现
(1)实现斐波那契数列的递归算法
#include
#include
voidfeibolaqi()
{
intfirst,second;
first=second=1;
printf("%d%d",first,second);
for(intn=0;n<20;++n)
{
inttemp=first+second;
first=second;
second=temp;
printf("%d",second);
}
}
intmain()
{
feibolaqi();
return0;
}
(2)实现二分检索的递归算法
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
voidselectionSort(intdata[],intcount);
intbinary_search(int*a,intn,intkey);
voidmain()
{
inti,key,rs;
intarr[10];
intcount;
printf("排序前数组为:
");
srand((int)time(0));
for(i=0;i<10;i++)
{
arr[i]=rand()%100;
printf("%d",arr[i]);
}
count=sizeof(arr)/sizeof(arr[0]);
selectionSort(arr,count);
printf("\n排序后数组为:
");
for(i=0;i<10;i++)
{
printf("%d",arr[i]);
}
printf("\n请输入要查找的数字:
");
scanf("%d",&key);
rs=binary_search(arr,10,key);
printf("%d",rs);
}
voidselectionSort(intdata[],intcount)
{
inti,j,min,temp;
for(i=0;i /*findtheminimum*/ min=i; for(j=i+1;j if(data[j] min=j; temp=data[i]; data[i]=data[min]; data[min]=temp; } } intbinary_search(int*data,intn,intkey) { intmid; if(n==1){ return(data[0]==key); }else{ mid=n/2; printf("mid=%d\n",data[mid]); if(data[mid-1]==key) return1; elseif(data[mid-1]>key) { printf("key%d比data[mid-1]%d小,取前半段\n",key,data[mid-1]); returnbinary_search(&data[0],mid,key); } else { printf("key%d比data[mid-1]%d大,取后半段\n",key,data[mid-1]); returnbinary_search(&data[mid],n-mid,key); } } } (3)用递归算法求出数组的最大最小元素 //FindMaxAndMin.cpp: 定义控制台应用程序的入口点。 // #include usingnamespacestd; //求数组的最大值和最小值,返回值在maxValue和minValue voidMaxandMin(int*a,intl,intr,int&maxValue,int&minValue) { if(l==r)//l与r之间只有一个元素 { maxValue=a[l]; minValue=a[l]; return; } if(l+1==r)//l与r之间只有两个元素 { if(a[l]>=a[r]) { maxValue=a[l]; minValue=a[r]; } else { maxValue=a[r]; minValue=a[l]; } return; } intm=(l+r)/2;//求中点 intlmax;//左半部份最大值 intlmin;//左半部份最小值 MaxandMin(a,l,m,lmax,lmin);//递归计算左半部份 intrmax;//右半部份最大值 intrmin;//右半部份最小值 MaxandMin(a,m+1,r,rmax,rmin);//递归计算右半部份 maxValue=max(lmax,rmax);//总的最大值 minValue=min(lmin,rmin);//总的最小值 } intmain() { inta[]={1,2,3,4,-4,2,6,3}; intlen=sizeof(a)/sizeof(int); intmax,min; MaxandMin(a,0,len-1,max,min); cout< system("pause"); return0; } (4)归并排序算法实现 #include usingnamespacestd; voidmerge(int*data,intp,intq,intr) { intn1,n2,i,j,k; int*left=NULL,*right=NULL; n1=q-p+1; n2=r-q; left=(int*)malloc(sizeof(int)*(n1)); right=(int*)malloc(sizeof(int)*(n2)); for(i=0;i left[i]=data[p+i]; for(j=0;j right[j]=data[q+1+j]; i=j=0; k=p; while(i { if(left[i]<=right[j]) data[k++]=left[i++]; else data[k++]=right[j++]; } for(;i data[k++]=left[i]; for(;j data[k++]=right[j]; } voidmergeSort(int*data,intp,intr) { intq; if(p { q=(int)((p+r)/2);//将data数组分成两半 mergeSort(data,p,q);//递归拆分左数组 mergeSort(data,q+1,r);//递归拆分右数组 merge(data,p,q,r);//合并数组 } } intmain() { intn; int*input=NULL; //输入数据 cout<<"请输入数组的长度: "; cin>>n; input=(int*)malloc(sizeof(int)*(n)); cout<<"请对数组赋值: "; for(inti=0;i { cin>>input[i]; } //处理数据 mergeSort(input,0,n-1); //输出结果 for(inti=0;i cout< cout< system("pause"); return0; } (5)快速排序算法实现 #include usingnamespacestd; voidquickSort(inta[],int,int); intmain() { intarray[]={34,65,12,43,67,5,78,10,3,70},k; intlen=sizeof(array)/sizeof(int); cout<<"Theorginalarrayare: "< for(k=0;k cout< cout< quickSort(array,0,len-1); cout<<"Thesortedarrayare: "< for(k=0;k cout< cout< system("pause"); return0; } voidquickSort(ints[],intl,intr) { if(l { inti=l,j=r,x=s[l]; while(i { while(i j--; if(i s[i++]=s[j]; while(i i++; if(i s[j--]=s[i]; } s[i]=x; quickSort(s,l,i-1);//递归调用 quickSort(s,i+1,r); } } (6)算法5.4实现(带有期限和效益的单位时间的作业排序贪心算法) /* 带有限期和收益的单位时间的作业排序贪心算法 */ #include /*算法1,复杂度O(n*n)*/ voidJS(intd[],intJ[],intn,int&k) { /*终止时,d[J[i]]<=d[J[i+1]]*/ inti,j,r; d[0]=J[0]=0; k=1; J[1]=1; for(i=2;i<=n;i++) { r=k; while(d[J[r]]>d[i]&&d[J[r]]! =r) r--; if(d[J[r]]<=d[i]&&d[i]>r) { for(j=k;j>r;j--) J[i+1]=J[i]; J[r+1]=i; k++; } } } /*算法2,复杂度O(n)*/ voidFJS(intd[],intJ[],intn,int&k) { inti,j,f[100]; for(i=0;i<=n;i++) { f[i]=i; //P[i]=-1; } k=0; for(i=1;i<=n;i++) { if(n>d[i]) j=d[i]; else j=n; while(f[j]! =j) j=f[j]; if(f[j]! =0) { k++; J[k]=i; f[j]=f[j-1]; } } } voidsort(intp[],intd[],intm) { inttemp; inti,j,k; for(i=0;i { k=i; for(j=i+1;j if(p[k] k=j; if(k! =i) { temp=p[k]; p[k]=p[i]; p[i]=temp; temp=d[k]; d[k]=d[i]; d[i]=temp; } } } intmain() { intp[100]; intd[100]; intJ[100]; intn,i,k; printf("请输入作业数: "); scanf("%d",&n); printf("输入作业期限: /n"); for(i=1;i<=n;i++) scanf("%d",&d[i]); printf("输入作业收益: /n"); for(i=1;i<=n;i++) scanf("%d",&p[i]); /*使用JS和FJS之前,需要先对p进行排序,使其按非降次序变化*/ sort(p,d,n); k=0; FJS(d,J,n,k); for(i=1;i<=k;i++) printf("%d-%d-%d",p[J[i]],d[J[i]],J[i]); getchar(); getchar(); getchar(); return0; } (7)算法5.6实现(生成二元归并树算法) #include usingnamespacestd; structHuffmanNode { intweight; intparent; intlchild,rchild; }; classHuffmanTree { public: HuffmanNode*Node; public: intTree(intweightnum); }; intHuffmanTree: : Tree(intweightnum) { inti,j,pos1,pos2; intmin1,min2; Node=newstructHuffmanNode[2*weightnum-1]; for(i=0;i { cout<<"请输入第"< "; cin>>Node[i].weight; Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; } for(i=weightnum;i<2*weightnum-1;i++){ pos1=-1;pos2=-1; min1=min2=32762; j=0; while(j<=i-1) { if(Node[j].parent==-1) { if(Node[j].weight<=min1) {min2=min1;min1=Node[j].weight; pos2=pos1;pos1=j;} else if(Node[j].weight {min2=Node[j].weight;pos2=j;} } j++; }//while Node[pos1].parent=i; Node[pos2].parent=i; Node[i].lchild=pos1; Node[i].rchild=pos2; Node[i].parent=-1; Node[i].weight=Node[pos1].weight+Node[pos2].weight; }//for j=2*weightnum-2; intl,r; while(Node[j].lchild! =-1||Node[j].rchild! =-1) { cout<<"rootis: "< l=Node[j].lchild; r=Node[j].rchild; cout<<"lchildis: "< cout<<"rchildis: "< cout< j--; } return0; } voidmain() {cout<<"|--------生成最优的二元归并树---------|"< cout<<"|----------1027401097-许静晨----------|"< cout<<"|-------------------------------------|"< inti; while(i) { intweightnum; cout<<"请输入权值的个数: "; cin>>weightnum; HuffmanTreet; t.Tree(weightnum); cout<<"Press<1>torunagain"< cout<<"Press<0>toexit"< cin>>i; } } (8)0-1背包问题算法实现 #include #defineMAX_NUM5 #defineMAX_WEIGHT10 usingnamespacestd; //动态规划求解 intzero_one_pack(inttotal_weight,intw[],intv[],intflag[],intn){ intc[MAX_NUM+1][MAX_WEIGHT+1]={0};//c[i][j]表示前i个物体放入容量为j的背包获得的最大价值 // rgb(255,0,0);">状态转移方程: c[i][j]=max{c[i-1][j],c[i-1][j-w[i]]+v[i]} //状态转移方程的解释: 第i件物品要么放,要么不放 //如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值 //如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值 for(inti=1;i<=n;i++){ for(intj=1;j<=total_weight;j++){ if(w[i]>j){ //说明第i件物品大于背包的重量,放不进去 c[i][j]=c[i-1][j]; }else{ //说明第i件物品的重量小于背包的重量,所以可以选择第i件物品放还是不放 if(c[i-1][j]>v[i]+c[i-1][j-w[i]]){ c[i][j]=c[i-1][j]; } else{ c[i][j]=v[i]+c[i-1][j-w[i]]; } } } } //下面求解哪个物品应该放进背包 inti=n,j=total_weight; while(c[i][j]! =0){ if(c[i-1][j-w[i]]+v[i]==c[i][j]){ //如果第i个物体在背包,那么显然去掉这个物品之后,前面i-1个物体在重量为j-w[i]的背包下价值是最大的 flag[i]=1; j-=w[i]; //--i;移到外面去 }--i; } returnc[n][total_weight]; } intmain(){ inttotal_weight=10; intw[4]={0,3,4,5}; intv[4]={0,4,5,6}; intflag[4];//flag[i][j]表示在容量为j的时候是否将第i件物品放入背包 inttotal_value=zero_one_pack(total_weight,w,v,flag,3); cout<<"需要放入的物品如下"< for(inti=1;i<=3;i++){ if(flag[i]==1) cout< } cout<<"总的价值为: "< return0; } (9)算法6.3实现(每对节点之间的最短路径) #include #defineMAX8888 intmain() { intcost[7][7]={ 0,20,50,30,MAX,MAX,MAX, MAX,0,25,MAX,MAX,70,MAX, MAX,MAX,0,40,25,50,MAX, MAX,MAX,MAX,0,55,MAX,MAX, MAX,MAX,MAX,MAX,0,10,70, MAX,MAX,MAX,MAX,MAX,0,50, MAX,MAX,MAX,MAX,MAX,MAX,0 }; inta[7][7],path[7][7]; inti,j,k; for(i=0;i<7;i++){ for(j=0;j<7;j++){ a[i][j]=cost[i][j]; if(i! =j&&a[i][j]! =MAX) path[i][j]=j; else path[i][j]=0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 原理 经典 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)