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

问题描述（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:[e-mail]
 * 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;
}