เพิ่ม 1 ให้กับตัวเลขที่แสดงในรูปแบบอาร์เรย์ (วิธีการเรียกซ้ำ)

ในส่วนนี้เราจะดูปัญหาที่น่าสนใจหนึ่งปัญหา สมมติว่ามีตัวเลขหนึ่งตัว เราต้องเพิ่มตัวเลขนี้ขึ้น 1 งานนี้ดูง่ายมาก แต่ที่นี่เราจะเก็บตัวเลขในรูปแบบอาร์เรย์ โดยแต่ละหลักของตัวเลขจะเป็นสมาชิกของอาร์เรย์ ถ้าตัวเลขคือ 512 จะเก็บเป็น {5, 1, 2} และเราต้องเพิ่มตัวเลขโดยใช้วิธีการเรียกซ้ำ (Recursive Approach) มาดูอัลกอริทึมเพื่อความเข้าใจที่ชัดเจน

อัลกอริทึม

increment(arr, n, index)

ค่าเริ่มต้นของ index คือ 0

begin
    if index < n then
        if arr[index] < 9 then
            arr[index] := arr[index] + 1
        else
            arr[index] := 0
            increment(arr, n, index + 1)
        end if
    end if
    if index = n then
        arr[n] := 1
        n := n + 1
    end if
end

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;

void increment(int num_arr[], int &n, int index = 0) {
    if (index < n) {
        if (num_arr[index] < 9) { // ถ้าหลักน้อยกว่า 9 ให้บวก 1
            num_arr[index]++;
        } else { // มิฉะนั้นเพิ่มตัวเลขแบบเรียกซ้ำ
            num_arr[index] = 0;
            increment(num_arr, n, index + 1);
        }
    }
    if (index == n) {
        num_arr[n] = 1; // เพิ่ม carry ที่เหลือ
        n++; // เพิ่มขนาด n
    }
}

void dispNumber(int num_arr[], int n) {
    for (int i = n - 1; i >= 0; i--) {
        cout << num_arr[i];
    }
    cout << endl;
}

int numToArr(int num_arr[], int number) {
    int i = 0;
    int n = log10(number) + 1;
    for (int i = i; i < n; i++) {
        num_arr[i] = number % 10;
        number /= 10;
    }
    return n;
}

int main() {
    int number = 1782698599;
    int num_arr[MAX];
    int n = numToArr(num_arr, number);
    cout << "Initial Number: ";
    dispNumber(num_arr, n);
    increment(num_arr, n);
    cout << "Final Number: ";
    dispNumber(num_arr, n);
}

ผลลัพธ์

Initial Number: 1782698599
Final Number: 1782698600

begin
    if index < n then
        if arr[index] < 9 then
            arr[index] := arr[index] + 1
        else
            arr[index] := 0
            increment(arr, n, index + 1)
        end if
    end if
    if index = n then
        arr[n] := 1
        n := n + 1
    end if
end

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;

void increment(int num_arr[], int &n, int index = 0) {
    if (index < n) {
        if (num_arr[index] < 9) { // ถ้าหลักน้อยกว่า 9 ให้บวก 1
            num_arr[index]++;
        } else { // มิฉะนั้นเพิ่มตัวเลขแบบเรียกซ้ำ
            num_arr[index] = 0;
            increment(num_arr, n, index + 1);
        }
    }
    if (index == n) {
        num_arr[n] = 1; // เพิ่ม carry ที่เหลือ
        n++; // เพิ่มขนาด n
    }
}

void dispNumber(int num_arr[], int n) {
    for (int i = n - 1; i >= 0; i--) {
        cout << num_arr[i];
    }
    cout << endl;
}

int numToArr(int num_arr[], int number) {
    int i = 0;
    int n = log10(number) + 1;
    for (int i = i; i < n; i++) {
        num_arr[i] = number % 10;
        number /= 10;
    }
    return n;
}

int main() {
    int number = 1782698599;
    int num_arr[MAX];
    int n = numToArr(num_arr, number);
    cout << "Initial Number: ";
    dispNumber(num_arr, n);
    increment(num_arr, n);
    cout << "Final Number: ";
    dispNumber(num_arr, n);
}

Initial Number: 1782698599
Final Number: 1782698600