C++で2つの数を加算する際に必要な繰り上がり操作の回数を数える方法

2つの数値 num_1 と num_2 が与えられます。目的は、これらの数を加算する際に必要な繰り上がり(キャリー)操作の回数を数えることです。例えば、123 と 157 を加算する場合、繰り上がり操作は1回発生します(7+3=10、1+2+5=8、1+1=2)。

具体例を使って理解していきましょう。

入力 − num_1=432、num_2=638

出力 − 2つの数を加算する際に必要な繰り上がり操作の回数:2

説明 − 右から左へ各桁を足し合わせながら、繰り上がりを数えます。

(2+8=10、繰り上がり1)count=1、
(1+3+3=7、繰り上がり0)count=1、
(4+6=10、繰り上がり1)count=2

入力 − num_1=9999、num_2=111

出力 − 2つの数を加算する際に必要な繰り上がり操作の回数:4

説明 − 右から左へ各桁を足し合わせながら、繰り上がりを数えます。

(9+1=10、繰り上がり1)count=1、
(1+9+1=11、繰り上がり1)count=2、
(1+9+1=11、繰り上がり1)count=3、
(1+9=10、繰り上がり1)count=4

プログラムで使用するアプローチ

まず、両方の数を文字列に変換します。続いて、文字列を末尾から走査し、各文字を整数に変換して2つの数を加算します。その際、前回の繰り上がり(1回目の反復では0)も一緒に加えます。合計値が10以上であれば繰り上がりを1に設定し、繰り上がりが発生するたびにカウントを1増やします。

• 2つの数を num_1 と num_2 として受け取ります。

• 関数 carry_add_two_numbers(num_1, num_2) が両方の数を受け取り、加算時に必要な繰り上がりの回数を返します。

• to_string(x) を使って両方の数を文字列に変換し、str_1 と str_2 に格納します。

• length() を使って両方の文字列の長さを length_str_1 と length_str_2 として取得します。

• カウントの初期値を0、繰り上がりの初期値も0に設定します。

• どちらかの文字列の長さが0でなくなるまでループを続けます。

• 末尾の文字を整数に変換し、変数 i と j に格納します。

• 両方の文字列の長さを1ずつ減らします。

• 加算用の変数として i+j+繰り上がり を計算します。

• add が10以上であれば、繰り上がりが発生するためカウントを1増やし、繰り上がりを1に設定します。そうでなければ、次の反復に備えて繰り上がりを0に設定します。

• すべての反復が終了した時点で、カウントには繰り上がりの総回数が格納されています。

• 結果としてカウントを返します。

このアルゴリズムの時間計算量は O(max(桁数1, 桁数2))、空間計算量は文字列変換を含めて O(桁数) となります。桁数に比例して処理されるため、非常に大きな数同士の加算でも効率的に繰り上がりを数えられます。

例

#include <bits/stdc++.h>
using namespace std;
int carry_add_two_numbers(int num_1, int num_2){
   string str_1 = to_string(num_1);
   int length_str_1 = str_1.length();
   string str_2 = to_string(num_2);
   int length_str_2 = str_2.length();
   int count = 0, carr = 0;
   while(length_str_1 != 0 || length_str_2 != 0){
      int i = 0, j = 0;
      if (length_str_1 > 0){
         i = str_1[length_str_1 - 1] - '0';
         length_str_1--;
      }
      if (length_str_2 > 0){
         j = str_2[length_str_2 - 1] - '0';
         length_str_2--;
      }
      int add = i + j + carr;
      if (add >= 10){
         carr = 1;
         count++;
      }
      else{
         carr = 0;
      }
   }
   return count;
}
int main(){
   int num_1 = 234578;
   int num_2 = 1234;
   int count = carry_add_two_numbers(num_1, num_2);
   cout<<"2つの数を加算する際に必要な繰り上がり操作の回数: "<<count;
   return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

2つの数を加算する際に必要な繰り上がり操作の回数: 2