a524 - 手機之謎

🔗 前往 ZeroJudge 原題

題目描述

題目要求產生一個 n 位數的密碼，其中密碼的每個數字都不重複，並且按照字典順序的反向排列輸出所有可能的密碼。輸入 n 代表密碼的位數。

解題思路

這題的核心是產生所有可能的 n 位數排列，且數字不重複。由於題目要求按照字典順序的反向排列輸出，因此可以使用 std::prev_permutation 函數來產生排列。首先，建立一個包含 n 個元素的陣列，元素的值為 n, n-1, ..., 1。然後，使用 prev_permutation 函數產生所有可能的排列，並輸出每個排列。

複雜度分析

• 時間複雜度: O(n!)，因為需要產生所有 n 的排列。
• 空間複雜度: O(n)，因為需要儲存 n 個元素的陣列。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a,c;
	while(cin>>a){
		int b[a];
		for(c=0;c<a;c++)
			b[c]=a-c;
		do{
			for(c=0;c<a;c++)
				cout<<b[c];
			cout<<endl;
		}while(prev_permutation(b,b+a));
	}
}