算法原理经典算法实现Word文档下载推荐.docx
《算法原理经典算法实现Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《算法原理经典算法实现Word文档下载推荐.docx（38页珍藏版）》请在冰点文库上搜索。
selectionSort（arr,count）;
\n排序后数组为：
arr[i]）;
\n请输入要查找的数字：
scanf（"
%d"
&
key）;
rs=binary_search（arr,10,key）;
rs）;
voidselectionSort（intdata[],intcount）
inti,j,min,temp;
for（i=0;
count;
i++）{
/*findtheminimum*/
min=i;
for（j=i+1;
j<
j++）
if（data[j]<
data[min]）
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;
mid=%d\n"
data[mid]）;
if（data[mid-1]==key）
return1;
elseif（data[mid-1]>
key）
key%d比data[mid-1]%d小，取前半段\n"
key,data[mid-1]）;
returnbinary_search（&
data[0],mid,key）;
else
key%d比data[mid-1]%d大，取后半段\n"
data[mid],n-mid,key）;
（3）用递归算法求出数组的最大最小元素
//FindMaxAndMin.cpp:
定义控制台应用程序的入口点。
//
iostream>
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];
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）;
//总的最小值
inta[]={1,2,3,4,-4,2,6,3};
intlen=sizeof（a）/sizeof（int）;
intmax,min;
MaxandMin（a,0,len-1,max,min）;
cout<
<
max<
"
min<
endl;
system（"
pause"
（4）归并排序算法实现
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））;
i<
n1;
i++）//对左数组赋值
left[i]=data[p+i];
for（j=0;
j<
n2;
j++）//对右数组赋值
right[j]=data[q+1+j];
i=j=0;
k=p;
while（i<
n1&
&
n2）//将数组元素值两两比较，并合并到data数组
if（left[i]<
=right[j]）
data[k++]=left[i++];
data[k++]=right[j++];
for（;
i++）//如果左数组有元素剩余，则将剩余元素合并到data数组
data[k++]=left[i];
j++）//如果右数组有元素剩余，则将剩余元素合并到data数组
data[k++]=right[j];
voidmergeSort（int*data,intp,intr）
intq;
if（p<
r）//只有一个或无记录时不须排序
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;
//输入数据
请输入数组的长度:
;
cin>
>
n;
input=（int*）malloc（sizeof（int）*（n））;
请对数组赋值:
for（inti=0;
++i）
{
input[i];
}
//处理数据
mergeSort（input,0,n-1）;
//输出结果
input[i]<
}
（5）快速排序算法实现
#include<
voidquickSort（inta[],int,int）;
intarray[]={34,65,12,43,67,5,78,10,3,70},k;
intlen=sizeof（array）/sizeof（int）;
Theorginalarrayare:
for（k=0;
k<
len;
k++）
cout<
array[k]<
"
quickSort（array,0,len-1）;
Thesortedarrayare:
voidquickSort（ints[],intl,intr）
if（l<
r）
inti=l,j=r,x=s[l];
while（i<
j）
while（i<
j&
s[j]>
=x）//从右向左找第一个小于x的数
j--;
if（i<
s[i++]=s[j];
s[i]<
x）//从左向右找第一个大于等于x的数
i++;
s[j--]=s[i];
s[i]=x;
quickSort（s,l,i-1）;
//递归调用
quickSort（s,i+1,r）;
（6）算法5.4实现（带有期限和效益的单位时间的作业排序贪心算法）
/*
带有限期和收益的单位时间的作业排序贪心算法
*/
/*算法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;
=n;
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&
inti,j,f[100];
f[i]=i;
//P[i]=-1;
k=0;
for（i=1;
if（n>
d[i]）
j=d[i];
j=n;
while（f[j]!
=j）
j=f[j];
if（f[j]!
=0）
J[k]=i;
f[j]=f[j-1];
voidsort（intp[],intd[],intm）
inttemp;
inti,j,k;
m;
k=i;
for（j=i+1;
j++）
if（p[k]<
p[j]）
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;
intp[100];
intd[100];
intJ[100];
intn,i,k;
请输入作业数：
&
n）;
输入作业期限：
/n"
d[i]）;
输入作业收益：
p[i]）;
/*使用JS和FJS之前，需要先对p进行排序，使其按非降次序变化*/
sort（p,d,n）;
k=0;
FJS（d,J,n,k）;
=k;
%d-%d-%d"
p[J[i]],d[J[i]],J[i]）;
getchar（）;
（7）算法5.6实现（生成二元归并树算法）
structHuffmanNode
intweight;
intparent;
intlchild,rchild;
};
classHuffmanTree
public:
HuffmanNode*Node;
intTree（intweightnum）;
intHuffmanTree:
:
Tree（intweightnum）
inti,j,pos1,pos2;
intmin1,min2;
Node=newstructHuffmanNode[2*weightnum-1];
for（i=0;
i<
weightnum;
i++）
请输入第"
i+1<
个字符的权值:
Node[i].weight;
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
for（i=weightnum;
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;
min2）
{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].weight=Node[pos1].weight+Node[pos2].weight;
}//for
j=2*weightnum-2;
intl,r;
while（Node[j].lchild!
=-1||Node[j].rchild!
=-1）
rootis:
Node[j].weight<
l=Node[j].lchild;
r=Node[j].rchild;
lchildis:
Node[l].weight<
rchildis:
Node[r].weight<
j--;
return0;
{cout<
|--------生成最优的二元归并树---------|"
|----------1027401097-许静晨----------|"
|-------------------------------------|"
inti;
while（i）
intweightnum;
请输入权值的个数:
HuffmanTreet;
t.Tree（weightnum）;
Press<
1>
torunagain"
0>
toexit"
i;
（8）0-1背包问题算法实现
#defineMAX_NUM5
#defineMAX_WEIGHT10
//动态规划求解
intzero_one_pack（inttotal_weight,intw[],intv[],intflag[],intn）{
intc[MAX_NUM+1][MAX_WEIGHT+1]={0};
//c[i][j]表示前i个物体放入容量为j的背包获得的最大价值
//<
spanstyle="
background-color:
rgb（255,0,0）;
状态转移方程：
c[i][j]=max{c[i-1][j],c[i-1][j-w[i]]+v[i]}<
/span>
//状态转移方程的解释：
第i件物品要么放，要么不放
//如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值
//如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值
for（inti=1;
=n;
for（intj=1;
=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]]）{
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<
需要放入的物品如下"
<
endl;
=3;
if（flag[i]==1）
重量为"
w[i]<
价值为"
v[i]<
总的价值为:
total_value<
（9）算法6.3实现（每对节点之间的最短路径）
#defineMAX8888
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];
7;
i++）{
j<
j++）{
a[i][j]=cost[i][j];
if（i!
=j&
a[i][j]!
=MAX）
path[i][j]=j;
path[i][j]=0;
升级会员 