C++-এ সুন্দর সাজান

ধরুন আমাদের ১ থেকে N পর্যন্ত Nটি পূর্ণসংখ্যা আছে। আমরা একটি সুন্দর সাজানকে এমন একটি অ্যারে হিসেবে সংজ্ঞায়িত করব যা এই N সংখ্যাগুলি সম্পূর্ণরূপে ব্যবহার করে তৈরি করা হয়েছে যদি ith পজিশনে (1 <= i <= N) এই অ্যারেতে নিম্নলিখিতগুলির মধ্যে একটি সত্য হয় −

• ith পজিশনে থাকা সংখ্যা i দ্বারা বিভাজ্য।
• i ith পজিশনে থাকা সংখ্যা দ্বারা বিভাজ্য।

তাই যদি ইনপুট 2 হয়, তবে ফলাফলও ২ হবে, কারণ প্রথম সুন্দর সাজান হল [1,2]। এখানে ১ম পজিশনে (i=1) থাকা সংখ্যা ১, এবং ১, i (i=1) দ্বারা বিভাজ্য। তারপর ২য় পজিশনে (i=2) থাকা সংখ্যা ২, এবং ২, i (i=2) দ্বারা বিভাজ্য। দ্বিতীয় সুন্দর সাজান হল [2, 1]: এখানে ১ম পজিশনে (i=1) থাকা সংখ্যা ২, এবং ২, i (i=1) দ্বারা বিভাজ্য। তারপর ২য় পজিশনে (i=2) থাকা সংখ্যা ১, এবং i (i=2), ১ দ্বারা বিভাজ্য।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −

• একটি রিকার্সিভ মেথড solve() সংজ্ঞায়িত করুন, যা visited অ্যারে, end এবং pos নেবে। pos প্রাথমিকভাবে ১।
• যদি pos = end + 1 হয়, তবে ans ১ বৃদ্ধি করুন এবং ফেরত যান
• i = 1 থেকে end পর্যন্ত
  • যদি i visited না হয় এবং pos, i দ্বারা বিভাজ্য হয় বা i, pos দ্বারা বিভাজ্য হয়, তবে
    • i কে visited চিহ্নিত করুন
    • solve(visited, end, pos + 1)
    • i কে unvisited চিহ্নিত করুন
• মূল মেথড থেকে, নিম্নলিখিত কাজ করুন −
• ans := ০, একটি 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;    } }; main(){    Solution ob;    cout << (ob.countArrangement(2)); }

ইনপুট

2

আউটপুট

2