文档介绍：《算法设计与分析》
实验报告
班级
姓名
学号
信息与电子工程学院
2009年9月
实验1 字典序问题
一、问题描述:
,即A={a,b...z}.该字母表产生的长序字符串是指定字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同,,a,b,ab,bc,xz,:
1       a   
2       b 
… 
… 
26     z   
27     ab   
28     ac   
… 
… 
对于任意长度不超过  6   的升序字符串,迅速计算出它在上述字典中的编码。
二、算法分析:
对于给定的长度不超过6的升序字符串,计算出它在上述字典中的编码。
思想:
设以第i个字符打头的长度k的升序字符串个数位f(i,k),长度k的升序字符串总个数为g(k),则g(k)=累加f(i,k),i从1到26 . f(i,1)=1 g(1)=累加f(i,1),i从1到26 . f(i,2)=累加f(j,1)=26-i,j从i+1到26 g(2)=累加f(i,2)=累加(26-i),i从1到26
一般情况,有:f(i,k)=累加f(j,k-1),j从i+1到26
g(k)=累加f(i,k)=累加i(累加j,f(j,k-1)),i从1到26,j从i+1到26
这样得到f,g后就可以针对不同的输入字符串输出其编号
三、程序清单:
#include<iostream>
#include<string>
#include<>
using namespace std;
int f(int i,int k)
{
int sum=0;
if(k==1) return 1;
else {
for(int j=i+1;j<=26;j++)
{
sum+=f(j,k-1);
}
}
return sum;
}
int g(int k)
{
int sum=0;
for(int i=1;i<=26;i++)
{
sum+=f(i,k);
}
return sum;
}
int change(char c)
{
return c-'a'+1;
}
int order(string s)
{
int k=();
int sum=0,temp=0;
for(int i=1;i<k;i++)
{
sum+=g(i);
}
for(int i=1;i<change(s[0]);i++)
{
sum+=f(i,k);
}
for( int i=1,temp=change(s[0]);i<();i++)
{
int t=change(s[i]);
int len=()-i; ¨¨
for(int j=temp+1;j<t;j++)
sum+=f(j,len);
temp=t;
}
return sum+1;
}
int main()
{
freopen("","r",stdin);
int num;
cout<<"请输入个数:"<<endl;
cin>>num;
string ss[100];
for(int i=0;i<num;i++)
{
cin>>ss[i];
}
freopen("","w",stdout);
for(int i=0;i<num;i++)
cout<<order(ss[i])<<endl;
sstem("pause");
return 0;
}
四、性能分析:
  
2 
a
  abc 
 
1 
352
五、实验感想与体会:
通过对大整数的编程实现,我发现了很多问题。像有些输入没按升序输入,有些输了数字,这些都要写错误报告返回形式反馈用户。
实验2 大整数乘法
一、问题描述:
通常,在分析一个算法的计算复杂性时,都将加法和乘法运算当作是基本运算来处理,即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而,