排列的字典序问题

算法分析与设计实验报告第2次实验姓名学号班级时间3.19上午地点四合院实验名称排列的字典序问题实验目的通过上机实验，要求掌握排列的字典序问题算法的问题描述、算法设计思想、程序设计。实验原理使用递归的方法，根据不同的输入用例，能准确的输出用例中的序数，并计算下一个序列。实验步骤①写出计算字典序的函数get_code（），在该函数中调用计算阶乘的函数cal_a（），由此算出字符串的字典序；②写出计算下一个排列的函数get_next（）；③将字典序和下一个排列输出到文件中。关键代码voidrev(int*p,intbegin,intend)//数组倒置{inttemp[end-begin];for(inti=begin;i=end;i++)temp[i-begin]=p[i];for(inti=end;i=begin;i--)p[i]=temp[end-i];}intcal_a(inta,intb)//计算阶乘{intanswer=1;if(a==0&&b==0)return1;for(inti=0;ib;i++){answer=answer*a;a--;}returnanswer;}intget_code(int*a,intn)//计算序数{intcount1=0;for(inti=0;in;i++){for(intj=i+1;jn;j++){if(a[j]a[i]){count1+=cal_a(n-i-1,n-i-1);}}}returncount1;}voidget_next(int*a,intn){intleft_limit;//确定变换的左边界for(inti=n-1;i=0;i--){if(a[i-1]a[i])//出现左边元素小于右边元素的情况时，不符合规律，即找到了变换的左边界。{left_limit=i-1;inttemp=a[left_limit+1]-a[left_limit];//temp用于保存两个数的差，为方便后续操作，初始值为左边界+1-左边界intrem=left_limit+1;//rem用于保存数组下标for(intj=left_limit;jn;j++)//在右边找与左边界相差最小的那个元素{if(a[j]-a[left_limit]0&&a[j]-a[left_limit]temp){temp=a[j]-a[left_limit];rem=j;}}swap(a[rem],a[left_limit]);rev(a,left_limit+1,n-1);break;}}}附录：完整代码#includeiostream#includefstreamusingnamespacestd;voidrev(int*p,intbegin,intend)//数组倒置{inttemp[end-begin];for(inti=begin;i=end;i++)temp[i-begin]=p[i];测试结果实验心得这次的实验和上一次的字典序问题有一些相似，主要不同的地方在于要写出下一个序列，通过看书和听同学在小班课上的讨论我明白了如何找出下一个序列，通过阅读同学的代码我也知道了如何用c++实现这个程序。这个算法的复杂度主要体现在一位一位计算阶乘和将数组倒置方面。通过本次试验我对递归有了更进一步的认识，希望以后可以做的更好。实验得分助教签名for(inti=end;i=begin;i--)p[i]=temp[end-i];}intcal_a(inta,intb)//计算阶乘{intanswer=1;if(a==0&&b==0)return1;for(inti=0;ib;i++){answer=answer*a;a--;}returnanswer;}intget_code(int*a,intn)//计算序数{intcount1=0;for(inti=0;in;i++){for(intj=i+1;jn;j++){if(a[j]a[i]){count1+=cal_a(n-i-1,n-i-1);}}}returncount1;}voidget_next(int*a,intn){intleft_limit;//确定变换的左边界for(inti=n-1;i=0;i--){if(a[i-1]a[i])//出现左边元素小于右边元素的情况时，不符合规律，即找到了变换的左边界。{left_limit=i-1;inttemp=a[left_limit+1]-a[left_limit];//temp用于保存两个数的差，为方便后续操作，初始值为左边界+1-左边界intrem=left_limit+1;//rem用于保存数组下标for(intj=left_limit;jn;j++)//在右边找与左边界相差最小的那个元素{if(a[j]-a[left_limit]0&&a[j]-a[left_limit]temp){temp=a[j]-a[left_limit];rem=j;}}swap(a[rem],a[left_limit]);rev(a,left_limit+1,n-1);break;}}}intmain(){inta;fstreamf1;ofstreamf2;f1.open(input.txt);f1a;intarray[a];for(inti=0;ia;i++)f1array[i];f1.close();f2.open(output.txt);f2get_code(array,a)endl;get_next(array,a);for(inti=0;ia;i++)f2array[i]'';f2endl;f2.close();return0;}