字典序问题.docx

《字典序问题.docx》由会员分享，可在线阅读，更多相关《字典序问题.docx（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流字典序问题【精品文档】第 5 页算法分析与设计实验报告第 1 次实验姓名学号201班级时间3.5上午地点四合院 实验名称字典序问题实验目的通过上机实验，要求掌握字典序问题的问题描述、算法设计思想、程序设计。实验原理使用递归的算法，根据不同的输入用例，能准确的输出用例的编码。实验步骤 先设计一个函数计算以i开头长度为k的字符串的个数； 再设计一个函数计算长度为k的所有升序字符串的个数； 输入字符串调用函数1和2，计算出编码； 用文件输入想要计算的字符串，求得的编码再输出到文件中。关键代码/计算以i开头长度为k的字符串的个数int f(int i,int k

2、)int sum=0;if(k=1)return 1;elsefor(int j=i+1;j=26;j+) sum=sum+f(j,k-1); return sum; /计算长度为k的所有升序字符串的个数int g(int k)int sum=0;for(int i=1;i=26;i+)sum=sum+f(i,k);return sum; int SUM(string a)int b=a0-a+1;int sum=0;int n=a.size();for(int i=1;i=n-1;i+)sum=sum+g(i); for(int i=1;ib;i+) sum=sum+f(i,n);for(i

3、nt i=1,c=b;in;i+)int t=ai-a+1;int len=n-i;for(int j=c+1;jt;j+)sum=sum+f(j,len);c=t;return sum+1;测试结果实验心得一开始看到这个题目我想到了用排列组合的知识来解，小班课上同学讲解的方法也是这个方法，后来我看课本上是利用递归的方法，于是我便尝试用递归的方法来解决这个问题，一开始并不顺利，我便上网查找资料和代码，通过阅读别人写过的代码，自己一点一点写出了解这个问题的代码。通过这个实验让我对递归实现一个问题有了更好的认识，同时一个题有多种解法也对我有很大的启发。 实验得分助教签名附录：完整代码#includ

4、e #include #includeusing namespace std;/计算以i开头长度为k的字符串的个数int f(int i,int k)int sum=0;if(k=1)return 1;elsefor(int j=i+1;j=26;j+) sum=sum+f(j,k-1);return sum;/计算长度为k的所有升序字符串的个数int g(int k)int sum=0;for(int i=1;i=26;i+)sum=sum+f(i,k);return sum;int SUM(string a)int b=a0-a+1;int sum=0;int n=a.size();for

5、(int i=1;i=n-1;i+)sum=sum+g(i); for(int i=1;ib;i+) sum=sum+f(i,n);for(int i=1,c=b;in;i+)int t=ai-a+1;int len=n-i;for(int j=c+1;jt;j+)sum=sum+f(j,len);c=t;return sum+1;int main(int argc, char* argv) ifstream in(input1.txt); ofstream out(output1.txt); coutn;coutnendl;cout文件中读入的每行数据为：endl;for(int i=1;ia; coutaendl; outSUM(a)endl;cout请到文件中查看结果endl; return 0;