数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中的美丽排列
假设我们有 N 个从 1 到 N 的整数。我们将定义一个美丽的排列为一个数组，如果该数组完全由这 N 个数字构成，并且对于该数组中的第 i 个位置（1 <= i <= 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]：此处第 1 个位置（i=1）上的数字为 2，并且 2 可以被 i（i=1）整除。然后第 2 个位置（i=2）上的数字为 1，并且 i（i=2）可以被 1 整除。
为了解决这个问题，我们将遵循以下步骤：-
- 定义一个递归方法 solve()，它将接收 visited 数组、end 和 pos。pos 最初为 1。
- 如果 pos = end + 1，则将 ans 加 1 并返回。
- 对于 i 的范围从 1 到 end
- 如果 i 未被访问并且 pos 可以被 i 整除或 i 可以被 pos 整除，则
- 标记 i 为已访问
- solve(visited, end, pos + 1)
- 标记 i 为未访问
- 如果 i 未被访问并且 pos 可以被 i 整除或 i 可以被 pos 整除，则
- 从主方法中执行以下操作：-
- ans := 0，创建一个名为 visited 的数组
- 调用 solve(visited, N, 1)
- 返回 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
更新于： 2020年5月2日
811 次查看
广告