Sắp xếp đẹp trong C ++

Giả sử chúng ta có N số nguyên từ 1 đến N. Chúng ta sẽ xác định một sắp xếp đẹp là một mảng được xây dựng bởi N số này hoàn toàn nếu một trong những điều sau đây đúng với vị trí thứ i (1 <=i <=N) trong mảng này -

Số ở vị trí thứ i có thể chia cho i.
i chia hết cho số ở vị trí thứ i.

Vì vậy, nếu đầu vào là 2, thì kết quả cũng sẽ là 2, như cách sắp xếp đẹp đầu tiên là [1,2]. Ở đây số ở vị trí đầu tiên (i =1) là 1 và 1 chia hết cho i (i =1). Khi đó số ở vị trí thứ 2 (i =2) là 2 và 2 chia hết cho i (i =2). Cách sắp xếp đẹp thứ hai là [2, 1]:Ở đây số ở vị trí thứ nhất (i =1) là 2, và số 2 chia hết cho i (i =1). Khi đó số ở vị trí thứ 2 (i =2) là 1 và i (i =2) chia hết cho 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một phương thức đệ quy giải quyết (), phương thức này sẽ nhận mảng, kết thúc và vị trí đã truy cập. Vị trí ban đầu là 1.
nếu pos =end + 1, sau đó tăng ans lên 1 và trả về
cho tôi trong phạm vi 1 đến hết
- nếu tôi không được truy cập và pos chia hết cho 0 hoặc tôi chia hết cho 0, thì
  - đánh dấu tôi là đã ghé thăm
  - giải quyết (đã truy cập, kết thúc, vị trí + 1)
  - đánh dấu tôi là không mời
từ phương thức chính, hãy thực hiện như sau -
ans:=0, tạo một mảng được gọi là đã thăm
cuộc gọi giải quyết (đã thăm, N, 1) r
trả về ans.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Sắp xếp đẹp trong C ++

Ví dụ

Đầu vào

Đầu ra