C/C++プログラムで桁の配列として表現された数値に1を加算する方法

この記事では、少し変わった興味深い問題を取り上げます。ある数値が与えられ、それに1を加算する——これは一見すると非常に簡単なタスクです。しかし、ここでは数値を配列として扱います。つまり、数値の各桁が配列の要素として格納されます。例えば、数値が512であれば、{5, 1, 2}のように保存されます。さらに、この加算処理は再帰的なアプローチを用いて実装します。まずは全体の流れをつかむために、アルゴリズムを見ていきましょう。

アルゴリズム

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
    if index = n, then
        arr[n] := 1
        n := n + 1
    end if
end

このアルゴリズムのポイントは以下の3点です。

• 現在の桁（index の位置）が9未満であれば、その桁に1を足すだけで処理は完了します。
• 現在の桁が9である場合、繰り上がりが発生します。その桁を0にして、次の桁に対して再帰的に同じ関数を呼び出します。
• すべての桁が9だった場合（例：999 → 1000）、最上位に新たな桁として1を追加し、桁数 n を1つ増やします。

実装例

#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; // 最上位に繰り上がりの1を追加
        n++; // 桁数を1増やす
    }
}
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);
}

実行結果

Initial Number: 1782698599
Final Number: 1782698600

このように、数値を整数型として直接保持するのではなく、桁ごとの配列として管理している場合でも、再帰を活用すれば繰り上がり処理を含む「1の加算」をシンプルかつエレガントに実現できます。特に、int型やlong long型の上限を超えるような巨大な数値を扱う場合に、この手法は非常に有効です。