Problem 993 Product of digits，位數的乘積

這題的意思是給你一個數字N，N是另一個數字Q中的所有個別位數的乘積，例如N=10，則Q可以是25，或52，題目要求Q是最小的。所以我就從 9 到 1 ，算他的因數，一次抽一個，按這種方式排列後，其數字會變的最小。需要注意的特殊狀況是，質因數有大於10的情形，這種數字就沒有答案了。這題又用到了遞迴的技巧，遞迴真是好用，只需要注意停止呼叫的條件，遞迴可以省很多事。遞迴函數如下，其中Q[10]是全域變數。

void compFactor(int n, int idx)
{
    int i;
    for (i=9;i>=1;i--)
        if (n%i==0)
        {
            Q[idx] = i;
            n /= i;
            break;
        }
    if (i!=1)
        compFactor(n, idx+1);
    else if (n!=1)
        Q[idx]=-1;
}

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