算法分析与设计实验报告
第 2 次实验
这次的实验和上一次的字典序问题有一些相似，主要不同的地方在于要写出下
附录：完整代码
#include <iostream>
#include <fstream>
using namespace std;
void rev(int *p,int begin,int end)//数组倒置
{
int temp[end-begin];
for(int i=begin;i<=end;i++)
temp[i-begin]=p[i];
for(int i=end;i>=begin;i--)
p[i]=temp[end-i];
}
int cal_a(int a,int b)//计算阶乘
{
int answer=1;
if(a==0&&b==0)
return 1;
for(int i=0;i<b;i++)
{
answer=answer*a;
a--;
}
return answer;
}
int get_code(int *a,int n)//计算序数
{
int count1=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[j]<a[i])
{
count1+=cal_a(n-i-1,n-i-1);
}
}
}
return count1;
}
void get_next(int *a,int n)
{
int left_limit;//确定变换的左边界
for(int i=n-1;i>=0;i--)
{
if(a[i-1]<a[i])//出现左边元素小于右边元素的情况时，不符合规律，即找到了变换的左边界。

{
left_limit=i-1;
int temp=a[left_limit+1]-a[left_limit];//temp用于保存两个数的差，为方便后续操作，初始值为左边界+1-左边界
int rem=left_limit+1;//rem用于保存数组下标
for(int j=left_limit;j<n;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;
}
}
}
int main(){
int a;
fstream f1;
ofstream f2;
f1.open("input.txt");
f1>>a;
int array[a];
for(int i=0;i<a;i++)
f1>>array[i];
f1.close();
f2.open("output.txt") ;
f2<<get_code(array,a)<<endl;
get_next(array,a);
for(int i=0;i<a;i++)
f2<<array[i]<<' ';
f2<<endl;
f2.close() ;
return 0;
}。