Question

一道ACM题帮忙解答一下！！！

哈哈，大家对地球上的排序规则都比较清楚了吧！可是火星上的规则跟地球上的不一样。地球上的十个数字的顺序是{0,1,2,3,4,5,6,7,8,9}，火星上的却是{0,8,1,5,2,3,9,4,7,6}。好在火星上基本数字也是十个，也是十进制，因此，很容易推得9<80<88<81<… 请根据火星上的规则对火星数进行从小到大的排序。
Input:

第一行为Case，表明接下来有Case组输入数据,每组数据的开头为N，表明该行接下来有N个数,然后是N个火星数中间以一个空格隔开。
Output:

每组输出只占一行，为N个经过火星排序的数。
Sample Input:

4
4 1 2 3 4
2 21 88
3 756 12 3
3 1 98 46
Sample Output:

1 2 3 4
88 21
3 12 756
1 98 46

Answer 1

/*
程序已经在浙江工业大学OJ上通过：
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1077

题目：
哈哈，大家对地球上的排序规则都比较清楚了吧！
可是火星上的规则跟地球上的不一样。
地球上的十个数字的顺序是{0,1,2,3,4,5,6,7,8,9}，
火星上的却是{0,8,1,5,2,3,9,4,7,6}。
好在火星上基本数字也是十个，也是十进制，
因此，很容易推得9<80<88<81<…
请根据火星上的规则对火星数进行从小到大的排序。

分析：

提供一种思路：【映射】

将【火星上的数字】映射到一个对应的【地球上的数字】，得到一个【数值对】。如：
11（火星）->22（地球）， 88（火星）->11（地球）都是这样的数值对。

对这些【数值对】进行【排序】时，我们根据数值对中的【地球上的数字】用【地球上的排序规则】。
【输出排序结果】时，我们输出【排序后的数值对】中的【火星上的数字】。

这样做的效果，和直接应用【火星上的排序规则】，对【火星上的数子】进行排序并输出，结果是等效的。

上面算法的巧妙之处是在应用【相对陌生火星规则】处理【火星上的事务】时，
避开了理解 【相对陌生火星规则】的过程，将 【火星上的事务】转换为等价的 【地球上的事务】，
应用我们【相对熟悉地球规则】处理转换得到的【地球上的事务】，
最后将【地球上的事务】还原为等价的【火星上的事务】，从而间接的处理了【火星上的事务】。

想一想，我们生活中是不是有很多这样的例子呢？^_^
*/

#include <stdio.h>
#include <stdlib.h>
//保存【火星上的数字】-【地球上的数字】的【映射关系】
struct Map
{
int mars;
int earth;
};

//【火星上的数字】-【地球上的数字】的【映射关系表】
int _map_table[]={0,8,1,5,2,3,9,4,7,6};

//保存【火星上的数字】-【地球上的数字】的【映射关系】
struct Map _data[10000];

//将【火星上的数字】映射为【地球上的数字】
int Trans(int mars)
{
int buffer[32],buffer_p=0;
int i=0,j=0;
int earth=0;

//分离 【火星上的数字】中【各位数字】
do
{
buffer[buffer_p++]=mars%10;
mars/=10;
}while(mars>0);

//【火星上的数字】中【各位数字】映射到【地球上的数字】的【各位数字】
for(i=0;i<buffer_p;i++)
{
for(j=0;;j++)
{
if(_map_table[j] == buffer[i]) break;
}
buffer[i]= j;
}

//用【地球上的数字】的【各位数字】合成【地球上的数字】
for(i=buffer_p-1;i>=0;i--)
{
earth = earth*10 + buffer[i];
}

return earth;

}

//建立两个 struct Map 元素的比较规则（这里为根据 int Map.earth 升序）
int cmp(const void * a,const void * b)
{
return ((struct Map*)a)->earth - ((struct Map*)b)->earth;
}

int main(int argc, char *argv[])
{

int T,N,i;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&_data[i].mars);
//根据火星上的数字得到对应的地球上的数字
_data[i].earth=Trans(_data[i].mars);
// printf("mars:%d earth:%d\n",_data[i].mars,_data[i].earth);
}

//调用快速排序算法，不懂的话可以参考函数的帮助文档
qsort(_data,N,sizeof(struct Map),cmp);

for(i=0;i<N-1;i++)
{
printf("%d ",_data[i].mars);
}
printf("%d\n",_data[i].mars);
}
return 0;
}

/*
Sample Input:

4
4 1 2 3 4
2 21 88
3 756 12 3
3 1 98 46

Sample Output:

1 2 3 4
88 21
3 12 756
1 98 46

*/

Answer 2

#include <stdio.h>
#include <stdlib.h>
char exchange(char ch)
{
switch ch
{
case 0:
return 0;
case 1:
return 8;
case 2:
return 1;
case 3:
return 5;
case 4:
return 2;
case 5:
return 3;
case 6:
return 9;
case 7:
return 4;
case 8:
return 7;
case 9:
return 6;
}
}

int exchange(int earth)
{
char str[100];
sprintf_s(str, sizeof(str) "%d", earth);
while(*str)
{
*str++ = exchange(*str);
}
int retv;
sscanf_s(str, "%d", &retv);
return retv;
}

int main()
{
int input[100]
printf("please input some number\n0--end\n");
int i;
for(i=0; i<100; i++)
{
scanf_s("%d", &input[i]);
if(!input[i])
break;
}
int output[100];
for(int i=0; i<100; i++)
{
if(!input[i])
break;
output[i] = exchange(input[i]);
}
for(int i=0; i<100 && input[i]; i++)
{
printf("%s\t", output[i]);
}

printf("Press any key to exit\n");

fflush(stdin);
getc(stdin);

return 0;
}

没有验证过。不过大致思想已经有了^_^
其他的功能可以把代码随便修改一下^_^

Answer 3

/*
* 经过编译和测试的代码，请参考。
*/
#include <iostream>
#include <algorithm>
using namespace std;
//{0,8,1,5,2,3,9,4,7,6};
unsigned int seq[10] = {0,2,4,5,7,3,9,8,1,6};

unsigned int buffer[1024];

unsigned E2T(unsigned int eight)
{
unsigned int tmp = 0;
while(eight)
{
tmp = tmp*10 + seq[eight%10];
eight = eight/10;
}
return tmp;
}

bool cmp(unsigned int a, unsigned int b)
{
unsigned int tmpa = E2T(a);
unsigned int tmpb = E2T(b);
if (tmpa > tmpb)
{
return false;
}
else
{
return true;
}
}
int main()
{
freopen("input.txt","r",stdin);
unsigned int cases = 0;
unsigned int num = 0;
scanf("%d", &cases);
while(cases)
{
scanf("%d", &num);
for (unsigned int i = 0; i < num; i++)
{
scanf("%d", buffer + i);
}
sort(buffer, buffer + num, cmp);
for (unsigned int i = 0; i < num; i++)
{
printf("%d", buffer[i]);
if (i == num -1)
{
printf("\n");
}
else
{
printf(" ");
}
}
cases--;
}
return 0;
}