思路:每次找当前序列中的最大值,想办法把他放在序列中的末尾就可以了
找最大值时,有以下三种情况:
① 最大值就在序列尾部.无需处理,找前i-1个数中的最大值
② 最大值在序列首部. 将序列翻转,最大值就到了尾部,然后执行①
③ 最大值在某个位置. 挨个搜索查找,找到后,记下标为i,只需把上面这i个数翻转,最大值就到了首部,然后执行②.
我们可以采用递归进行处理
设f(bottom,maxnum)
bottom 是未排好序的前bottom个数(0<=bottom<=n-1)
maxnum是当前未排好序中的元素的最大值
开一个数组s储存数据
再用s_sort数组储存排序后的s,方便我们找maxnum
因为当前序列中的最大值maxnum = s_sort[bottom]
递归函数
int f(int bottom,int maxnum)//bottom 记录底部实际下标[0,n-1],maxnum是上面未排好的数[0,bottom]中的最大值
{if(bottom<=0) return 0;if(s[bottom]==maxnum)//最大值在底部{f(bottom-1,s_sort[bottom-1]);//已经排好这个了,再接着排上面的}else if(s[0]==maxnum)//最大值在顶部{int position =n-bottom;//计算插的位置.如最底部的是n-1, 要插的位置就是n-(n-1)=1 op.push_back(position);//把刀插到最底下做翻转reverse(s,s+bottom+1);f(bottom-1,s_sort[bottom-1]);}else{int i=0;while(s[i]!=maxnum) i++;op.push_back(n-i);reverse(s,s+i+1);//最大值到了最上面f(bottom,maxnum);//直接递归处理}return 0;
}完整代码
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int s[100];//用于实际操作处理
int s_sort[100];//对数组s先进行排序,方便查找最大值maxnum
int ans[100];//用于最后输出原数据
int n=0;
vector<int>op;
int f(int bottom,int maxnum)//bottom 记录底部实际下标[0,n-1],maxnum是上面未排好的数[0,bottom]中的最大值
{if(bottom<=0) return 0;if(s[bottom]==maxnum){f(bottom-1,s_sort[bottom-1]);//已经排好这个了,再接着排上面的}else if(s[0]==maxnum)//最大值在顶部{int position =n-bottom;//记录插的位置如最底部的是n-1, n-(n-1)=1 op.push_back(position);//把刀插到最底下做翻转reverse(s,s+bottom+1);f(bottom-1,s_sort[bottom-1]);}else{int i=0;while(s[i]!=maxnum) i++;op.push_back(n-i);reverse(s,s+i+1);f(bottom,maxnum);//最大值到了最上面,再直接f一下处理,减少代码重复}return 0;
}
int init()
{n=0;op.clear();return 0;
}
int main()
{//freopen("uva.txt","r",stdin);int x;while(scanf("%d",&x)!=EOF){do{s_sort[n]=x;ans[n]=x;s[n++]=x;if(getchar()=='\n') break;}while(scanf("%d",&x)!=EOF);sort(s_sort,s_sort+n);f(n-1,s_sort[n-1]);for(int i=0;i<n;i++){printf("%d ",ans[i]);}printf("\n");for(int i=0;i<(int)op.size();i++){printf("%d ",op[i]);}printf("0\n");init(); }return 0;
}