พิมพ์ลำดับทั้งหมดของความยาวที่กำหนดใน C++

ในปัญหานี้ เราจะได้รับค่าจำนวนเต็ม 2 ค่า คือ k และ n และต้องพิมพ์ลำดับทั้งหมดที่มีความยาว k จากตัวเลข 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) สร้าง array ขนาด k โดยค่าเริ่มต้นทั้งหมด = 1 เช่น {1, 1, ..k ครั้ง}
2) ทำซ้ำขั้นตอน 3 และ 4 จนกว่า array จะกลายเป็น {n, n, ..., n}
3) พิมพ์ array
4) เพิ่มค่าให้องค์ประกอบของ array กลายเป็นค่าถัดไป
   เช่น {1, 1, 1} เพิ่มเป็น {1, 1, 2} และ {1, 3, 3} เพิ่มเป็น {2, 1, 1}
   สำหรับนี้ ต้องตรวจสอบองค์ประกอบตัวที่ k ของ array ถ้าเท่ากับ n ให้อัปเดต
   จากนั้นตรวจสอบองค์ประกอบตัวที่ k-1 ในลำดับ และทำต่อไปด้วยเงื่อนไขเดียวกัน

โปรแกรมตัวอย่าง (วิธีที่ 1)

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

ผลลัพธ์

The sequence is -

1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3

วิธีนี้เข้าใจง่ายแต่สามารถปรับปรุงให้ดีและมีประสิทธิภาพมากขึ้นได้

วิธีที่ 2 ใช้ recursion และ index เพิ่มเติมเพื่อตรวจสอบ sequence offset (ค่าหลังจากที่ลำดับจะพลิก) ฟังก์ชันจะถูกเรียกซ้ำ และจะไม่อัปเดตพจน์จนถึง index และเรียกฟังก์ชันซ้ำสำหรับพจน์ถัดไปหลัง index

โปรแกรมตัวอย่าง (วิธีที่ 2 - Recursion)

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

ผลลัพธ์

The sequence is -

1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3