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

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

数调用函数set(n)，故该算法的时间复杂度为Ο(n)。
实验五 集合划分问题


2、题目分析：
题目要求计算n个元素的集合共有多少个划分（其中每个划分都由不同的非空子集组成），n个元素的集合划分为m个块的划分数为F(n,m)=F(n-1,m-1)+m*F(n-1,m),m从1到n的划分个数相加即可求得总的划分数。

3、算法设计：
a. 这一题的结果数很大，需要使用64位长整型：__int64；
b. 函数div()采用递归的方式计算n个元素的集合划分为i个块的划分数：
①div (n,1)=1，div (n,n)=1;
②div (n,i)= div (n-1,i-1)+i*div (n-1,i)
c. 主函数采用for循环调用函数div(n,i)（1≤i≤n）对划分数进行累加统计。
4、源程序：

#include<stdio.h>

__int64?div(__int64?n,__int64?i)
{
if(i==1||i==n)
return?1;
else?return?div(n-1,i-1)+i*div(n-1,i);
}

main()
{
__int64?i,n,s=0;
scanf("%I64d",&n);
for(i=1;i<=n;i++)
s=s+div(n,i);
printf("%I64d",s);
return?0;
}


5、算法分析：
函数div()的时间复杂度为，主函数内for循环的时间复杂度为O(n)，函数div()嵌套在for循环内，故该算法的时间复杂度为。

实验七 编辑距离问题

1、问题描述：
?设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这
里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另
一个字符。将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编
辑距离，记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它
们的编辑距离d(A,B)。

2、题目分析：
题目要求计算两字符串的编辑距离，可以采用动态规划算法求解，由最优子结构性质可建立递归关系如下：
其中数组d[i][j] 存储长度分别为i、j的两字符串的编辑距离；用edit标记所比较
的字符是否相同，相同为0，不同为1；用m、n存储字符串a、b的长度。

3、算法设计：
a. 函数min()找出三个数中的最小值；

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