C ++中的漂亮排列

假设我们有从1到N的N个整数。如果此数组中的第i个位置（1 <= i <= N）满足以下条件之一，则将定义一个漂亮的排列为完全由这N个数字构成的数组-

• 第i个位置的数字可以除以i。

• 我可以被第i个位置的数字整除。

因此，如果输入为2，则结果也将为2，因为第一个漂亮的排列是[1,2]。此处，第1位置（i = 1）的数字为1，i被i（i = 1）整除。然后，第二个位置（i = 2）的数字为2，而2可被i整除（i = 2）。第二个漂亮的排列是[2，1]：这里第一个位置（i = 1）的数字是2，而2可以被i（i = 1）整除。然后，第二个位置（i = 2）的数字为1，而i（i = 2）可被1整除。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个递归方法solve()，它将采用访问数组，结束符和位置。pos最初是1。

• 如果pos = end + 1，则将ans加1并返回

• 对于我在范围1到结束

• 将我标记为已访问

• 解决（已访问，结束，位置+1）

• 将我标记为未访问

• 如果未访问我并且pos可被0整除或i被0整除，则

• 从主要方法中，执行以下操作-

• ans：= 0，创建一个名为访问的数组

• 调用solve(visited,N,1)r

• 返回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