In tất cả các chuỗi có độ dài nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp hai giá trị nguyên, k và n. Và chúng ta phải in tất cả các dãy có độ dài k từ các số từ 1 đến n theo thứ tự đã sắp xếp.

Hãy lấy một ví dụ để hiểu chủ đề -

Input:k = 2 ; n = 3
Output:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Vì vậy, trong bài toán này, chúng ta phải in trình tự như đã nêu ở trên.

Một cách đơn giản để giải quyết vấn đề này là tăng số nguyên của dãy số cho đến khi chúng đạt đến giá trị lớn nhất, tức là n. Sau đây là mô tả chi tiết về giải pháp.

Thuật toá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.

Ví dụ

Chương trình sau đây sẽ giúp bạn hiểu rõ hơn về khái niệm này.

#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;
}

Đầu ra

Trình tự là -

Phương pháp này dễ hiểu nhưng có thể được thực hiện tốt hơn và hiệu quả hơn.

Phương pháp này sử dụng đệ quy và một chỉ mục bổ sung để kiểm tra độ lệch của chuỗi (giá trị mà sau đó chuỗi sẽ được lật). Hàm sẽ được gọi một cách đệ quy và sẽ không cập nhật các điều khoản cho đến khi lập chỉ mục. Và lặp lại hàm cho các điều khoản tiếp theo sau chỉ mục.

Ví dụ

#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;
}

Đầu ra

Trình tự là -