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