तीन वेरिएबल size, max_val, last_element इनपुट के रूप में दिए गए हैं। लक्ष्य विभिन्न सरणियों की संख्या ढूंढना है जिन्हें इस तरह से बनाया जा सकता है कि उनमें size तत्व हों, 1 और max_val के बीच तत्व हों और पहला तत्व हमेशा 1 हो और अंतिम तत्व हमेशा max_val हो। साथ ही सुनिश्चित करें कि कोई दो लगातार तत्व समान न हों।
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - size = 5, max_val = 3, last_element = 3
आउटपुट - लगातार तत्वों के अलग मान वाली सरणियों की संख्या: 5
व्याख्या - सरणियाँ होंगी:-
[ 1, 2, 3, 1, 3 ], [ 1, 2, 3, 2, 3 ], [ 1, 2, 1, 2, 3 ], [ 1, 3, 1, 2, 3 ], [ 1, 3, 2, 1, 3 ]।
इनपुट - size = 3 max_val = 2 last_element = 2
आउटपुट - लगातार तत्वों के अलग मान वाली सरणियों की संख्या: 0
व्याख्या - 3 तत्वों वाली और [ 1, _, 2 ] वाली कोई सरणी संभव नहीं है क्योंकि हम मध्य तत्व के लिए 1 या 2 के अलावा कुछ नहीं भर सकते और यह लगातार अलग तत्वों की शर्त का उल्लंघन करेगा।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- इस दृष्टिकोण में हम ऐसी सरणियों की गिनती खोजने के लिए डायनामिक प्रोग्रामिंग और कॉम्बिनेटोरिक्स का उपयोग करेंगे।
- पहला और अंतिम तत्व 1 और last_element के रूप में तय होंगे। किसी भी आकार की सरणियों के लिए उन्हें भरने के तरीके केवल size-2 तत्वों के लिए होंगे।
- size-2 स्थानों में भरे जाने वाले [1 से max_val] तत्व। तरीके होंगे ways(max_val)= ways(size) / (max_val - 1)
- प्रत्येक रेंज 1 से i के लिए, तरीके होंगे ways(i)=ways(size) / (max_val - 1) [ ways(size) = अंतिम तत्व को 2 से max_val तक की संख्याओं से भरने के तरीकों की संख्या )।
- यदि last_element 1 है तो तरीके ways(size-1) होंगे क्योंकि अंतिम तत्व केवल 1 हो सकता है।
- दूसरा अंतिम तत्व हमेशा 1 और max_val के बीच हो सकता है।
- यदि दूसरा अंतिम तत्व 1 नहीं है तो तरीके (max_val-2)*ways(i-1) होंगे क्योंकि arri </sub> 1 या arri-1 नहीं हो सकता
- यदि दूसरा अंतिम तत्व 1 है तो तरीके (max_val-1)*ways(i-1) होंगे क्योंकि arri-1 1 है और arri-2 1 नहीं है।
- Ways(i) होगा :- (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
- वेरिएबल size, max_val और last_element को इनपुट के रूप में लें।
- फ़ंक्शन diff_val(int size, int max_val, int last_element) सभी इनपुट लेता है और लगातार तत्वों के अलग मान वाली सरणियों की संख्या लौटाता है।
- प्रारंभिक गिनती 0 लें।
- सरणी भरने के तरीकों की गिनती संग्रहीत करने के लिए सरणी arr[Max_N] = { 0 } लें। arr[0] को 0 और arr[1] को 1 से इनिशियलाइज़ करें।
- i=2 से i<size तक पार करें।
- temp_1 = (max_val - 2) * arr[i - 1] और temp_2 = (max_val - 1) * arr[i - 2] लें
- arr[i] = temp_1 + temp_2 सेट करें।
- यदि last_element == 1 तो count = (max_val - 1) * arr[size - 2] सेट करें।
- अन्यथा arr[size - 1] लौटाएं।
- अंत में परिणाम के रूप में count लौटाएं।
उदाहरण
#include <bits/stdc++.h> using namespace std; #define Max_N 109 int diff_val(int size, int max_val, int last_element) { int count = 0; int arr[Max_N] = { 0 }; arr[0] = 0; arr[1] = 1; for (int i = 2; i < size; i++) { int temp_1 = (max_val - 2) * arr[i - 1]; int temp_2 = (max_val - 1) * arr[i - 2]; arr[i] = temp_1 + temp_2; } if (last_element == 1) { count = (max_val - 1) * arr[size - 2]; } else { return arr[size - 1]; } return count; } int main() { int size = 5; int max_val = 3; int last_element = 3; cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element); return 0; } यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
आउटपुट
Count of arrays having consecutive element with different values are: 5
