Tăng 1 cho số được biểu diễn dưới dạng mảng (Đệ quy)

Trong phần này, chúng ta sẽ xem xét một bài toán thú vị. Giả sử có một số cho trước, ta cần tăng số này lên 1. Đây là một nhiệm vụ cực kỳ đơn giản. Tuy nhiên, ở đây số sẽ được lưu trữ dưới dạng mảng, mỗi chữ số của số đó là một phần tử của mảng. Nếu số là 512, nó sẽ được lưu trữ là {5, 1, 2}. Và chúng ta phải tăng số này bằng cách sử dụng phương pháp đệ quy. Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

increment(arr, n, index)

Giá trị mặc định ban đầu của index là 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

Ví dụ

#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){ //nếu chữ số nhỏ hơn 9, cộng 1
      num_arr[index]++;
    }else{ //ngược lại tăng số đệ quy
      num_arr[index] = 0;
      increment(num_arr, n, index+1);
    }
  }
  if(index == n){
    num_arr[n] = 1; //thêm nhớ dư
    n++; //tăng 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;
}

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

Kết quả

Initial Number: 1782698599
Final Number: 1782698600