इस समस्या में, हमें दो पूर्णांक मान, k और n दिए गए हैं। और हमें 1 से n तक की लंबाई के सभी अनुक्रमों को क्रमबद्ध क्रम में प्रिंट करना होगा।
आइए विषय को समझने के लिए एक उदाहरण लेते हैं -
Input:k = 2 ; n = 3 Output: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
तो इस समस्या में, हमें ऊपर बताए गए क्रम को प्रिंट करना होगा।
इस समस्या को हल करने का एक आसान तरीका अनुक्रम के पूर्णांकों को तब तक बढ़ाना है जब तक कि वे अधिकतम मान यानी n तक नहीं पहुंच जाते। समाधान का विस्तृत विवरण निम्नलिखित है।
एल्गोरिदम
1) Create an array of size k with all values = 1 i.e. {1, 1, ..ktimes}.
2) Repeat step 3 and 4 till the array becomes {n, n, …, n}.
3) Print the array.
4) Increment the value such that the elements of the array become the next value. For example, {1, 1, 1} incremented to {1, 1, 2} and {1, 3, 3} incremented to {2, 1, 1}. For this we need to check the kth element of the array, if it’s equal to n become update, then check k-1 element in the sequence and so on for the same condition. उदाहरण
निम्नलिखित कार्यक्रम आपको अवधारणा को और स्पष्ट कर देगा।
#include<iostream>
using namespace std;
void printSequence(int arr[], int size){
for(int i = 0; i < size; i++)
cout<<arr[i]<<"\t";
cout<<endl;
return;
}
int nextElement(int arr[], int k, int n){
int s = k - 1;
while (arr[s] == n)
s--;
if (s < 0)
return 0;
arr[s] = arr[s] + 1;
for(int i = s + 1; i < k; i++)
arr[i] = 1;
return 1;
}
void generateSequence(int n, int k){
int *arr = new int[k];
for(int i = 0; i < k; i++)
arr[i] = 1;
while(1){
printSequence(arr, k);
if(nextElement(arr, k, n) == 0)
break;
}
return;
}
int main(){
int n = 3;
int k = 2;
cout<<"The sequence is :\n";
generateSequence(n, k);
return 0;
} आउटपुट
क्रम है -
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
यह विधि समझने में आसान है लेकिन इसे बेहतर और अधिक कुशल बनाया जा सकता है।
यह विधि अनुक्रम ऑफसेट (मान जिसके बाद अनुक्रम फ़्लिप किया जाएगा) की जांच के लिए रिकर्सन और एक अतिरिक्त अनुक्रमणिका का उपयोग करता है। फ़ंक्शन को रिकर्सिवली कॉल किया जाएगा और इंडेक्स तक शर्तों को अपडेट नहीं करेगा। और अनुक्रमणिका के बाद अगले पदों के लिए फ़ंक्शन को पुन:प्राप्त करें।
उदाहरण
#include<iostream>
using namespace std;
void printSequence (int arr[], int size){
for (int i = 0; i < size; i++)
cout << arr[i] << "\t";
cout << endl;
return;
}
void generateSequence (int arr[], int n, int k, int index){
int i;
if (k == 0){
printSequence (arr, index);
}
if (k > 0){
for (i = 1; i <= n; ++i){
arr[index] = i;
generateSequence (arr, n, k - 1, index + 1);
}
}
}
int main (){
int n = 3;
int k = 2;
int *arr = new int[k];
cout<<"The sequence is:\n";
generateSequence (arr, n, k, 0);
return 0;
} आउटपुट
क्रम है -
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3