经典ACM算法合集经典ACM算法合集(7)

经典ACM算法合集经典ACM算法合集

j]=j;
for( i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
int edit=( a[i-1] == b[j-1] ? 0 : 1);
d[i][j]=min((d[i-1][j-1]+edit),
(d[i][j-1]+1),(d[i-1][j]+1));
}
}
temp = d[m][n];
free(d);
return temp;
}

main()
{
char a[10000],b[10000];
scanf("%s\n%s",a,b);
printf("%d",d(a,b));
return 0;
}


5、算法分析：
函数d()采用了双重循环，里层的for循环复杂度为O(n)，外层的for循环复杂度为O(m)，主函数调用了函数d()，故该算法的时间复杂度为O(mn)。

实验八 程序存储问题

1、问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是i l ， 1 ≤i ≤n。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。

2、题目分析：
题目要求计算给定长度的磁带最多可存储的程序个数，先对程序的长度从小到大排序，再采用贪心算法求解。

3、算法设计：
a. 定义数组a[n]存储n个程序的长度，s为磁带的长度；
b. 调用库函数sort(a,a+n)对程序的长度从小到大排序；
c. 函数most()计算磁带最多可存储的程序数，采用while循环依次对排序后的程序
长度进行累加，用i计算程序个数，用sum计算程序累加长度（初始i=0,sum=0）：
① sum=sum+a[i];
② 若sum<=s，i加1，否则i为所求；
③ i=n时循环结束；
d. 若while循环结束时仍有sum<=s，则n为所求。

4、源程序：

#include<iostream>
using namespace std;
#include<algorithm>
int a[1000000];

int most(int *a,int n,int s)
{
int i=0,sum=0;
while(i<n)
{
sum=a[i]+sum;
if(sum<=s)
i++;
else return i;
}
return n;
}

main()
{
int i,n,s;
scanf("%d %d\n",&n,&s);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
printf("%d",most(a,n,s));
return 0;
}

5、算法分析：
函数most()的时间杂度为Ο(n)，主函数调用的库函数sort(a,a+n)的时间复杂度为，且主函数调用函数most()，故该算法的时间杂度为。
实验九 最优服务次序问题

1、问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 ≤i≤n。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。对于给定的n个顾客需要的服务时间，编程计算最
优服务次序。

2、题目分析：
考虑到每个顾客需要的服务时间已给定，要计算最优服务次序，可以先对顾客需要的服务时间由短到长排序，再采用贪心算法求解。

3、算法设计：
a. 定义数组a[n]存储n个顾客需要的服务时间；
b. 调用库函数sort(a,a+n)对顾客需要的服务

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(7)全文阅读和word下载服务。