a524: 手機之謎

2019-08-13

內容

鄭學長的手機裡有不可告人的秘密，為了不被發現那些照片和簡訊，他小心翼翼地把手機上鎖了。
幸好，你是個會寫程式的天才，你能夠產生所有的密碼去嘗試，現在趕快動手吧！
噢！還有一件事，基於某些理由，你知道鄭學長的密碼沒有重覆的字。

輸入

輸入為一個 n (n<=8)，代表鄭學長的密碼位數。

3
2

輸出

輸出所有可能的密碼，依字典順序反向排列（因為你覺得他的密碼應該在後半段）。

321
312
231
213
132
123
21
12

解題思路

經典遞迴題目，先宣告一個 unUse 陣列，在數字被使用後就把 unUse[i] 設成 0 代表 i 被使用過，並在使用結束在復原回去。

接下來用遞迴遍歷從 333 到 111 (假設 n = 3) 的所有可能，在遍歷時如果遇到 unUse[i] == 0 的情況代表 i 在之前已經被使用過了，因為題目說數字不會重複，所以直接跳過該分支。

由於在遍歷時已經排除了數字重複的情況，所以答案直接輸出即可。

完整程式碼

AC (6ms, 96KB)

#include <stdio.h>

int n;
char unUse[10] = "012345678", output[10];

void dfs(int now, char* oTop)
{
    if (now == n)
    {
        puts(output);
        return;
    }
    for (int i = n; i; i--)
    {
        if (unUse[i])
        {
            *oTop = unUse[i] , unUse[i] = 0;
            dfs(now + 1 , oTop + 1);
            unUse[i] = *oTop;
        }
    }
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        output[n] = '\0';
        dfs(0, output);
    }
    return 0;
}