Uva 10152 ShellSort - c++编程基础

题目意思：有一堆的乌龟，输出一堆乱序的乌龟，然后输入一个正确的顺序，要求找到一种最小步骤的方法使得第一堆变成第二堆，每一次可以把乌龟移到第一个位置，输出该方法步骤.

解题思路：我们可以用两个char 数组来存储第一和第二堆的乌龟顺序，然后用两个int 数组num和tem来存储乌龟的顺序编号.我们知道只要从后面往前遍历tem数组就可以找到最小的步骤，然后利用栈的先进后出的性质(由上面可知，乌龟最后一个肯定是最先移动的）

代码：
[cpp]
//UVA10152
#include
#include
#include
#include
#include
#include
using namespace std;

char ch[210][100] , temp[210][100];
int num[210] , tem[210];

void output(int n){
int i , j;
memset(tem , 0 ,sizeof(tem));
for(i = 0 ; i < n ;i++){
for(j = 0 ; j < n ; j++){
if(strcmp(temp[i] , ch[j]) == 0)
tem[i] = num[j];
}
}
for(i = n-2 ;i >= 0 ; i--){
if(tem[i] > tem[i+1])
break;
}
stacks;
for(j = 0 ;j <= i ;j++)
s.push(temp[j]);
while(!s.empty()){
cout< s.pop();
}
cout< }
int main(){
int t , n , i , j;
cin>>t;
while(t--){
int n;
cin>>n;
getchar();
memset(num , 0 , sizeof(num));
for(i = 0 ;i < n ; i++){
gets(ch[i]);
num[i] = i;
}
for(i = 0 ; i < n ; i++){
gets(temp[i]);
}
output(n);
}
return 0;
}

作者：cgl1079743846