C++ 中的优美排列
c++server side programmingprogramming更新于 2024/9/1 3:09:00
假设我们有 N 个从 1 到 N 的整数。如果以下条件之一对于此数组中的第 i 个位置 (1 <= i <= N) 为真，我们将把优美排列定义为完全由这 N 个数字构成的数组 −
- 第 i 个位置的数字可以被 i 整除。
- i 可以被第 i 个位置的数字整除。
因此，如果输入为 2，则结果也将为 2，因为第一个优美排列是 [1,2]。这里第 1 个位置 (i=1) 的数字为 1，1 可以被 i 整除 (i=1)。然后第 2 个位置 (i=2) 的数字为 2，2 可以被 i 整除 (i=2)。第二个漂亮的排列是 [2, 1]:这里第一个位置(i=1)的数字是 2，2 可以被 i(i=1)整除。然后第二个位置(i=2)的数字是 1，i(i=2)可以被 1 整除。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个递归方法solve()，它将接受访问过的数组、end 和 pos。 pos 最初为 1。
- 如果 pos = end + 1，则将 ans 增加 1 并返回
- 对于 i，范围从 1 到 end
- 如果 i 未被访问且 pos 可被 0 整除或 i 可被 0 整除，则
- 将 i 标记为已访问
- solve(visited, end, pos + 1)
- 将 i 标记为未访问
- 如果 i 未被访问且 pos 可被 0 整除或 i 可被 0 整除，则
- 从 main 方法中，执行以下操作 −
- ans := 0，创建一个名为 accessed 的数组
- call solve(visited, N, 1)r
- return ans.
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ans;
void solve(vector <bool>& visited, int end, int pos = 1){
if(pos == end + 1){
ans++;
return;
}
for(int i = 1; i <= end; i++){
if(!visited[i] && (pos % i == 0 || i % pos == 0)){
visited[i] = true;
solve(visited, end, pos + 1);
visited[i] = false;
}
}
}
int countArrangement(int N) {
ans = 0;
vector <bool> visited(N);
solve(visited, N);
return ans;
}
};
main(){
Solution ob;
cout << (ob.countArrangement(2));
}
输入
2
输出
2
