Computer >> Máy Tính >  >> Lập trình >> lập trình C

Thêm 1 vào số được biểu diễn dưới dạng mảng (Phương pháp đệ quy)?

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