Problem 725 Division

輸入一 n 值，要找出所有 abcde / fghij = n 的數，條件是，abcde 和 fghij 的每個位數不能重複出現，如果不滿五位數，則補 0。此題與 Problem 471 Magic Numbers 相同，如果解了此題，不仿可以解解 471。

找尋此數，因 abcde > fghij，所以 fghij >= 1234，因為如果小於 1234 的數，都會違反條件。

首先，寫一判斷兩數符合條件之函式：

int check(int i, int j)
{
    int tmp, k, repeat[10] = {0};
    for (k = 0 ; k < 5; k ++)
    {
        tmp = i % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        i /= 10;
        tmp = j % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
        j /= 10;
    }
    return 1;
}

主程式則是要從 fghij = 1234，持續判斷到 abcde >= 100000 為止。 C 語言程式碼如下：

abcde = 1234 * n, fghij = 1234;
count = 0;
if (caseNum ++ != 0) printf("\n");
for (; abcde < 100000; abcde += n, fghij ++)
    if (check(abcde, fghij)) 
        printf("%05d / %05d = %d\n", abcde, fghij, n), count ++;
if (count == 0) printf("There are no solutions for %d.\n", n);

By David.K

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