Trong phần này, chúng ta sẽ thấy một vấn đề thú vị. Giả sử một số được đưa ra. Chúng ta phải tăng con số này lên 1. Đây là nhiệm vụ cực kỳ đơn giản. Nhưng ở đây chúng ta sẽ đặt số dưới dạng một mảng. mỗi chữ số của số đó được đặt như một phần tử của mảng. Nếu số là 512, thì nó sẽ được lưu trữ dưới dạng {5, 1, 2}. Và chúng ta cũng phải tăng số lượng bằng cách sử dụng phương pháp đệ quy. Hãy để chúng tôi xem thuật toán để có được ý tưởng rõ ràng.
Thuật toán
tăng (arr, n, index)
Ban đầu giá trị mặc định của chỉ mục 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 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){ //if digit is less than 9, add 1
num_arr[index]++;
}else{ //otherwise increase number recursively
num_arr[index] = 0;
increment(num_arr, n, index+1);
}
}
if(index == n){
num_arr[n] = 1; //add extra carry
n++; //increase 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);
} Đầu ra
Initial Number: 1782698599 Final Number: 1782698600