SUSE程序设计大赛-人类记数方式与外星人记数方式的转换 - algorithm

问题描述（Problem Description）：

2036年，人类探测器猎豹X到达了木星的第二颗卫星——木卫二。探测器上的防生学智能机器人传达给科学家一个重要情报——它们发现了智能生命...智能生命与人类有着不同的数学计数法，他们用几个数字的排列就可以表达出丰富的数字世界。

其计数的规律如下：

1 代表1

1 2 代表2

2 1 代表3

1 2 3 代表4

1 3 2 代表5

2 1 3 代表6

2 3 1 代表7

3 1 2 代表8

3 2 1 代表9

1 2 3 4 代表10

..............

编程实现人类记数方式与外星人记数方式的转换。

输入（Input）：

提示输入人类数字。

输出（Output）：

输出转换后对应的外星人数字。

输入示例（Sample Input）：

人类计数数字：234

输出示例（Sample Output）：

外星人计数数字：153426

==============================================================

解题思路：

1.计算出对应的ET数组合在n个数字的全排列中，比如人类数234，对应是5位数字组合,

n=5,再算出在5个数字全排列组合中排在第pos个，234，对应pos=81(也就是在12345的全

排列中的第81组，就是我们要求的ET数了，在程序的第二个for计算)

2.确定每一位具体是哪个数，从第一位开始，(有一个规律，每一列的数都是按从小到大排列

的，当然不是全部咯，前一位相同的列，后一列是按从小到大排列的，比如说，第一位是1

时，第二位最开始是2，几组后是3，等等。。。)，这里使用个judge_pos,这是判断第

n-i列的第个数字(在未被使用的数字钟的第judge_pos位),前面定义了一个judge[20],用

来表示每个数字是否被使用,在未使用的数字中找到第judge_pos位，就是第n-i-1列的具

体数字了

NOTE：

1.不计算全排列，根据每一列的从小到大排列规律来确定每位的具体数字。

2.可能说的不是很清楚，哎...确实也不知道怎么说的更通俗一点了，自己慢慢研究吧，中间有一句输出pos和judge_pos的，多研究研究就对了~~~

3.关于执行效率问题，肯定比计算全排列的速度快(当数字很大时)

4.关于计算长度问题，定义了几个long整形，可以计算到由13位数字的组合，再大就装不下了，定义成unsigned long还可以多一倍，但是也没多大意义，long大概可以计算到人类数字的20几亿...

5. 还有什么问题尽量提哦！！！

程序入下：

/* * Convert the human number to E.T number * Author:William Cheung * MAIL:williamzuii@163.com * DATE:2008/06/09 */ #include <stdio.h> int main(int argc,char **argv) { int i,j,k; int et_num[20]; /* the E.T number and */ int n; /* n is the number */ long count,sub_count=1; /* the count of the combination from 1 to n */ int judge[20]; /* To judge the number is used? */ long pos,judge_pos,human_num; /* pos is the position,judge_pos as the sub_position,and the human number */ for(i=0;i<20;i++) judge[i]=0; printf("Input the human number:"); scanf("%ld",&human_num); /* to get the E.T number */ for(i=1;;i++) { /* find out n,and the first position */ for(j=1,count=1;j<=i;j++) count*=j; human_num-=count; if(human_num<=0) { n=i; /* find out the number */ pos=human_num+count; /* the first position */ break; } } /* printf("n=%d,pos=%d\n",n,pos); */ for(i=n-1;i>=0;i--) { /* find out all numbers at each position */ for(j=1,sub_count=1;j<=i;j++) sub_count*=j; judge_pos=pos/sub_count; /* find a sub_position */ if((pos%sub_count)!=0) judge_pos++; /* printf("pos=%ld,judge_pos=%ld\n",pos,judge_pos); */ for(j=0,k=0;j<n;j++) { if(judge[j]==0) k++; else continue; if(k==judge_pos) { et_num[n-i-1]=j+1; /* Find a number at the position (n-i-1)*/ judge[j]=1; /* et_num[j] is in use now */ break; } } pos=pos%sub_count; /* new position */ if(pos==0) pos=sub_count; } printf("The E.T numbe is:"); for(i=0;i<n;i++) /* out put the E.T number */ printf("%d ",et_num[i]); printf("\n"); getch(); /* don't use the function in linux */ return 0; }