सी++ में सुंदर व्यवस्था

मान लीजिए कि हमारे पास 1 से N तक N पूर्णांक हैं। हम एक सुंदर व्यवस्था को एक सरणी के रूप में परिभाषित करेंगे जो इन N संख्याओं द्वारा पूरी तरह से बनाई गई है यदि निम्न में से एक इस सरणी में ith स्थिति (1 <=i <=N) के लिए सही है। -

• वें स्थान की संख्या को i से विभाजित किया जा सकता है।
• i वें स्थान पर संख्या से विभाज्य है।

तो अगर इनपुट 2 है, तो परिणाम भी 2 होगा, क्योंकि पहली सुंदर व्यवस्था [1,2] है। यहाँ पहली स्थिति (i=1) की संख्या 1 है, और 1 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 से विभाज्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक पुनरावर्ती विधि हल () को परिभाषित करें, जो विज़िट की गई सरणी, अंत और स्थिति लेगी। स्थिति शुरू में 1 है।
• अगर pos =end + 1 है, तो ans को 1 से बढ़ा दें और वापस आ जाएं
• मैं श्रेणी 1 से अंत तक के लिए
  • यदि मैं विज़िट नहीं किया गया है और पॉज़ 0 से विभाज्य है या मैं 0 से विभाज्य है, तो
    • देखे गए के रूप में चिह्नित करें
    • समाधान (विज़िट, एंड, पॉज़ + 1)
    • मैं नहीं देखा के रूप में चिह्नित करें
• मुख्य विधि से, निम्न कार्य करें -
• उत्तर:=0, विज़िट की गई एक सरणी बनाएं
• कॉल सॉल्व (विज़िट, N, 1)r
• उत्तर दें।

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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