#include<iostream>
#include<cstdio>
using namespace std;
typedef struct {
int val;
int row; /*箭头指向,0表示指向左,1指向右*/
}INTS;
int maxmove(INTS *a,int n) /*找出最大的移动整数K的下标maxi*/
{
int i,maxi=-1,max=0;
if(a[0].row && a[0].val>a[1].val && a[0].val>max) /*如果第1个数的箭头指向右且右边的数比它小*/
{ /*那么第1个数有可能就是最大移动整数,先暂时保存*/
maxi=0;
max=a[0].val;
}
for(i=1;i<n-1;i++) /*从第2个数到倒数第2个数,如果它的箭头指向右并且右边的数比它小 或者 它的箭头*/
{ /*指向左并且左边的数比它小,那么它也有可能是最大移动整数*/
if(a[i].row && a[i].val>a[i+1].val || !a[i].row && a[i].val>a[i-1].val)
{
if(a[i].val>max)
{
maxi=i;
max=a[i].val;
}
}
}
if(!a[n-1].row && a[n-1].val>a[n-2].val && a[n-1].val>max)
{ /*如果最后1个数的箭头指向右且右边的数比它小*/
maxi=n-1; /*那么最后1个数有可能就是最大移动整数,先暂时保存*/
max=a[n-1].val;
}
return maxi;
}
void move(INTS *a,int n,int maxi)
{
int i,temp;
if(a[maxi].row) { /*把最大移动整数K和它箭头指向的相邻整数互换*/
temp=a[maxi+1].val;
a[maxi+1].val=a[maxi].val;
a[maxi].val=temp;
temp=a[maxi+1].row;
a[maxi+1].row=a[maxi].row;
a[maxi].row=temp;
maxi++;
} else {
temp=a[maxi-1].val;
a[maxi-1].val=a[maxi].val;
a[maxi].val=temp;
temp=a[maxi-1].row;
a[maxi-1].row=a[maxi].row;
a[maxi].row=temp;
maxi--;
}
for(i=0;i<n;i++)[Page]
if(a[i].val>a[maxi].val) /*调转所有大于K的整数的方向*/
a[i].row=!a[i].row;
}
int main()
{
INTS com[100];
int i,n,maxi;
printf(\"Please input the number:\");
scanf(\"%d\",&n);
for(i=0;i<n;i++)
{
com[i].val=i+1; /*第一个排列初始化为 1,2,3,……n*/
com[i].row=0; /*箭头全部指向左，即值为0*/
printf(\"%d \",i+1); /*输出第1个排列序列*/
}
printf(\"\\n\");
maxi=maxmove(com,n);
while(maxi!=-1) /*如果存在一个移动整数K，就执行循环*/
{
move(com,n,maxi);
for(i=0;i<n;i++)
printf(\"%d \",com[i].val);
printf(\"\\n\");
maxi=maxmove(com,n);
}
return 0;
}
最新评论