排列的字典序问题(共5页).docx

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

1、精选优质文档-倾情为你奉上算法分析与设计实验报告第 2 次实验姓名学号班级时间3.19上午地点四合院 实验名称排列的字典序问题实验目的通过上机实验，要求掌握排列的字典序问题算法的问题描述、算法设计思想、程序设计。实验原理使用递归的方法，根据不同的输入用例，能准确的输出用例中的序数，并计算下一个序列。实验步骤写出计算字典序的函数 get_code（），在该函数中调用计算阶乘的函数 cal_a（），由此算出字符串的字典序；写出计算下一个排列的函数 get_next（）；将字典序和下一个排列输出到文件中。关键代码void rev(int *p,int begin,int end)/数组倒置 int

2、tempend-begin;for(int i=begin;i=begin;i-) pi=tempend-i;int cal_a(int a,int b)/计算阶乘 int answer=1;if(a=0&b=0) return 1;for(int i=0;ib;i+)answer=answer*a;a-;return answer;int get_code(int *a,int n)/计算序数 int count1=0;for(int i=0;in;i+)for(int j=i+1;jn;j+)if(aj=0;i-)if(ai-1ai)/出现左边元素小于右边元素的情况时，不符合规律，即找到了

3、变换的左边界。 left_limit=i-1;int temp=aleft_limit+1-aleft_limit;/temp用于保存两个数的差，为方便后续操作，初始值为左边界+1-左边界int rem=left_limit+1;/rem用于保存数组下标 for(int j=left_limit;j0&aj-aleft_limittemp) temp=aj-aleft_limit; rem=j; swap(arem,aleft_limit);rev(a,left_limit+1,n-1);break; 测试结果实验心得这次的实验和上一次的字典序问题有一些相似，主要不同的地方在于要写出下一个序列

4、，通过看书和听同学在小班课上的讨论我明白了如何找出下一个序列，通过阅读同学的代码我也知道了如何用c+实现这个程序。这个算法的复杂度主要体现在一位一位计算阶乘和将数组倒置方面。通过本次试验我对递归有了更进一步的认识，希望以后可以做的更好。实验得分助教签名附录：完整代码#include #include using namespace std;void rev(int *p,int begin,int end)/数组倒置 int tempend-begin;for(int i=begin;i=begin;i-) pi=tempend-i;int cal_a(int a,int b)/计算阶乘 in

5、t answer=1;if(a=0&b=0) return 1;for(int i=0;ib;i+)answer=answer*a;a-;return answer;int get_code(int *a,int n)/计算序数 int count1=0;for(int i=0;in;i+)for(int j=i+1;jn;j+)if(aj=0;i-)if(ai-1ai)/出现左边元素小于右边元素的情况时，不符合规律，即找到了变换的左边界。 left_limit=i-1;int temp=aleft_limit+1-aleft_limit;/temp用于保存两个数的差，为方便后续操作，初始值为左边界+1-左边界int rem=left_limit+1;/rem用于保存数组下标 for(int j=left_limit;j0&aj-aleft_limita;int arraya;for(int i=0;iarrayi;f1.close();f2.open(output.txt) ;f2get_code(array,a)endl;get_next(array,a);for(int i=0;ia;i+) f2arrayi ;f2endl;f2.close() ;return 0;专心-专注-专业