Problem 10905 Children's Game，最大的數字排序

這題就是給你多個數值，將這些數值排序成最大的數。

這題最大的關鍵就是數值的比較，首先，舉兩個例子：9898989、 98 怎麼比較誰大誰小? 234、 2345 怎麼比較誰大誰小? 重點在於讓它化成類似循環小數，再去比較誰大誰小。做法如下：

98      →  98989898989898
9898989 →  98989899898989
---------------------------
                  ↑
                 此處可以看出 9898989 較大。

再來，是 234、 2345 的例子：
234  →  23423423
2341 →  23412341
---------------------------
           ↑
        此處可以看出 234 較大。

所以，寫一函式比較兩個字串的大小，順便找出兩字串長度的最小公倍數，這是兩字串比較的最大次數，若比到最小公倍數的次數還比較不出大小，這就代表兩字串相等。函式的 C 語言程式碼如下：

int gcd(int x, int y) {
    int tmp;
    
    while (x % y != 0) {
        tmp = y;
        y = x % y;
        x = tmp;
    }
    return y;
}

int lcm(int x, int y) {
    return x * y / gcd(x,y);
}


int numcmp(char c1[], char c2[])
{
    int c1len = strlen(c1); 
    int c2len = strlen(c2);
    int c1Index = 0, c2Index = 0;
    int count = 0, maxCount = lcm(c1len, c2len);
    while (count != maxCount)
    {
        if (c1Index == c1len) c1Index -= c1len;
        if (c2Index == c2len) c2Index -= c2len;
        if (c1[c1Index] - '0' < c2[c2Index] - '0') return 0;
        if (c1[c1Index] - '0' > c2[c2Index] - '0') return 1;
        c1Index ++, c2Index ++, count ++; 
    }
    return 0;
}

最後，只需將每個字串加入一個結構陣列，並且排序，最後印出就可以了。C 語言程式碼如下：

struct num
{
    char num[90];
};
struct num allNum[50];
int index;

主程式內...
index = 0;  
for (i = 0; i < n; i ++)
{
    scanf("%s", allNum[index ++].num);
    for (j = index - 1; j >= 1; j --)
        if (numcmp(allNum[j].num, allNum[j - 1].num)) 
        {
            strcpy(a.num, allNum[j].num);
            strcpy(allNum[j].num, allNum[j - 1].num);
            strcpy(allNum[j - 1].num, a.num);
        }
        else
            break;    
}
for (i = 0; i < index; i ++)
    printf("%s", allNum[i].num);
printf("\n");
...

By David.K

p10905題目連結
回ACM題庫目錄
回首頁