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

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

• ith स्थिति पर संख्या i से विभाज्य है।
• i, ith स्थिति पर संख्या से विभाज्य है।

इसलिए यदि इनपुट 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 को अविज़िट किया गया चिह्नित करें
• मुख्य विधि से, निम्नलिखित करें:
  • 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; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.countArrangement(2)); 
}

इनपुट

2

आउटपुट

2