科目Bの桁ごとの足し算問題の解き方｜繰り上がりを表で追う

筆算なら簡単なのに、配列になったとたん、どこから足しているのか分からない。

科目Bで、数を1桁ずつ配列に入れて足し算するコードを見て、手が止まったことはありませんか？

小学校で習った筆算と同じことをしているはずなのに、添字と mod と商が一度に出てくると、急に難しく見えてしまいます。繰り上がりの変数がどこで使われているのかを見失い、最後の桁で答えがずれてしまう人も多いのではないでしょうか。

大丈夫です。桁ごとの足し算の問題は、1桁ぶんの計算を1行として表に書いていけば、筆算とまったく同じ手順で答えにたどり着けます。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。金額やポイントの集計を扱う機能では、桁あふれや端数の扱いを確かめるテストを何度も書いてきました。

あるとき、集計結果の一番上の桁だけが表示されない不具合に出会いました。原因は、最後に残った繰り上がりを結果に書き込む処理が抜けていたことで、1桁ずつ値を書き出して初めて気づけました。

この記事では、桁ごとの足し算の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

桁ごとの足し算の問題は何を聞いているのか¶

最初に、なぜ数をわざわざ配列に分けるのかを押さえておきましょう。整数型の変数には入れられる大きさに上限があるので、とても大きな数は1桁ずつ配列に入れて計算する、という考え方がこの問題の出発点です。

こうした表し方は、多倍長整数と呼ばれることもあります。名前は難しそうですが、やっていることは紙の上の筆算を、配列の上で再現しているだけです。

筆算では、一の位から順に足し、10を超えたら1を上の桁へ運びました。プログラムでも同じで、各桁の和を10で割った余りをその桁に書き、商を次の桁へ運びます。

この余りと商の関係があいまいな場合は、先にこちらの記事で確かめておくと、あとのトレースが楽になります。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

筆算とプログラムの対応を表で確かめる¶

まずは、筆算でやっていることと、プログラムの行がどう対応するのかを並べてみます。言葉が違うだけで、手順は同じだと分かるはずです。

表の最後の行は、とても忘れやすい手順です。筆算でも、999 ＋ 1 のように桁が1つ増えるときは、左端に1を書き足しましたよね。

設問のパターンを表で整理する¶

桁ごとの足し算の設問は、聞かれ方がいくつかの型に分かれます。どの型なのかを最初に見極めると、表のどの列を見ればよいかがはっきりします。

この記事では、出題されやすい計算の結果と空欄の穴埋めを中心に追います。途中の値を問う型は、同じトレース表の途中の行を読むだけで答えられます。

まず目を付ける場所¶

足し算の考え方がつかめたら、次はコードのどこから読むかを決めます。この問題で目を付ける場所は3つです。

ひとつ目は配列のどちらの端が一の位なのか、ふたつ目は結果の配列の要素数と書き込む位置、みっつ目は carry の初期値と最後の扱いです。この3か所が決まれば、あとは1桁ずつ表に書くだけです。

どちらの端が一の位なのか¶

最初に確かめたいのが、配列の要素番号1が一番上の桁なのか、一の位なのかです。問題文には、たとえば要素番号1に最上位の桁を格納する、のような説明が必ず書かれています。

最上位が先頭なら、ループは末尾から先頭へ向かって減っていきます。逆に一の位が先頭なら、ループは1から増えていく形になります。

ループの向きと一の位の場所がかみ合っていないと、筆算を左の桁から始めてしまうのと同じことになります。for 文の から と まで を見たら、その向きが一の位から始まっているかを必ず確かめてください。

結果の配列は1つ長い¶

次に見るのが、結果を入れる配列の要素数です。n 桁どうしを足すと、答えは最大で n ＋ 1 桁になります。

結果の配列が1つ長いと、入力の i 番目の桁は、結果の i ＋ 1 番目に書き込むことになります。この1つのずれが、空欄の穴埋めでいちばんよく狙われる場所です。

配列の添字が1つずれる感覚に不安がある場合は、こちらの記事で添字の追い方を確かめておくと安心です。

【関連記事】科目Bの配列問題の解き方｜添字を表にして追う方法

carry の初期値と最後の行¶

みっつ目は、繰り上がりを表す変数 carry です。ループに入る前は 0 から始まり、ループの中で毎回書き換えられます。

そして、ループを抜けたあとに carry を結果の先頭へ書き込む行があるかどうかを確かめましょう。この1行があるかないかで、答えが1桁ぶん変わります。

例題：2つの数を桁ごとに足す関数¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、同じ桁数 n の2つの数を、1桁ずつ整数型の配列 a と b に受け取り、和を配列で返す関数です。配列の要素番号は1から始まり、要素番号1には最上位の桁が入っています。

○整数型の配列: addDigits(整数型の配列: a, 整数型の配列: b)
  整数型: n ← a の要素数
  整数型の配列: c ← {(n ＋ 1)個の 0}
  整数型: i, s
  整数型: carry ← 0
  for (i を n から 1 まで 1 ずつ減らす)
    s ← a[i] ＋ b[i] ＋ carry
    c[i ＋ 1] ← s mod 10
    carry ← s ÷ 10 の商
  endfor
  c[1] ← carry
  return c

addDigits は、末尾の一の位から順に、2つの桁と繰り上がりを足していきます。和の一の位を結果に書き、十の位を次の桁へ運ぶ、という筆算そのままの動きです。

では、a が {4, 7, 8}、b が {5, 6, 9} のとき、つまり 478 ＋ 569 を計算するとき、addDigits の戻り値はどうなるでしょうか？

トレース表で和と繰り上がりを追う¶

頭の中だけで3桁を処理すると、どの carry がどの桁に足されたのかがすぐに分からなくなります。そこで、1桁ぶんの処理を1行として、i、足す前の carry、s、書き込む位置と値、新しい carry をトレース表に書きます。

ポイントは、足す前の carry と足したあとの carry を別の列に分けることです。1つの列で上書きしてしまうと、どの値で s を計算したのかが後から読めなくなります。

すべての桁を処理し終えると、c は {1, 0, 4, 7} になります。先頭から読めば 1047 で、478 ＋ 569 の答えと一致します。

3行目を見てください。4 ＋ 5 だけなら 9 で繰り上がりは出ませんが、下の桁から運ばれた 1 が加わって 10 になり、ここでも繰り上がりが生まれています。

このように、繰り上がりは次の桁の計算に入り込み、さらに次の繰り上がりを生むことがあります。1行ずつ表に書いておけば、こうした連鎖も見落としません。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

途中の値を問われたら行で止める¶

設問によっては、i が 2 の処理を終えた直後の carry の値を聞かれることがあります。そのときは、トレース表の i が 2 の行で止めて、新しい carry の列を読むだけです。

この例なら答えは 1 です。最後まで計算してから戻る必要はありません。

桁数の違う数を足すときの考え方¶

問題によっては、桁数の違う2つの数を足す形も出てきます。そのときは、短いほうの数の上の桁に 0 を補って、同じ桁数にそろえてから足すのが基本です。

コードの中では、足りない桁を 0 として扱う条件分岐が入っていることが多くなります。その if 文が、どちらの配列の長さで判定しているかを確かめれば、桁数が違っても同じ表で追えます。

間違いやすい選択肢の見分け方¶

桁ごとの足し算の問題では、添字やループの向きを少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の 478 ＋ 569 を使って、よくある誤りを表にまとめました。どれも、実際にそのとおりに動かすと出てくる値です。

2行目の誤りは、s の式に carry が入っていないときに起きます。繰り上がりは計算されているのに、どこにも使われていない状態です。

3行目は、空欄の穴埋めで特によく狙われます。c[i] と c[i ＋ 1] のどちらが入るかを問われたら、結果の配列が入力より1つ長いことを思い出してください。

和が最大になる場合で検算する¶

選択肢で迷ったら、999 ＋ 999 のように、すべての桁で繰り上がりが出る小さな例を代入してみるのが近道です。答えが 1998 になるかどうかで、carry の扱いが正しいかをまとめて確かめられます。

このとき s の最大値は 9 ＋ 9 ＋ 1 で 19 です。つまり carry は必ず 0 か 1 にしかならず、2 以上になる選択肢は、どこかで式を取り違えています。

余りと商の役割を言葉で確かめる¶

mod と商のどちらを書き込み、どちらを運ぶのかで迷ったら、言葉に直してみましょう。余りはその桁に残る数、商は上の桁へ運ぶ数です。

17 なら、残るのは 7 で、運ぶのは 1 です。逆に書くと、c に 1 が並び、carry が 7 になるという、筆算ではありえない動きになるので、すぐに気づけます。

数を1桁ずつ取り出す考え方は、基数変換の問題でもまったく同じ形で使われます。あわせて読んでおくと、mod と商の使い分けがさらに身につきます。

【関連記事】科目Bの基数変換問題の解き方｜n進数への変換を余りと商で追う

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。配列の中身と変数が同時に変わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの桁で予想とずれたのかがすぐに分かります。

試すときは、まず例題の 478 ＋ 569 を動かして、i が 1 の行で 4 ＋ 5 ＋ 1 が 10 になる瞬間を確かめてください。そのあと最後の c[1] ← carry の行を消して動かすと、一番上の桁が消える様子が見え、この1行の意味が体で分かります。

慣れてきたら、999 ＋ 999 や 100 ＋ 200 のように、繰り上がりの多い例と少ない例を自分で用意して試しましょう。結果を予想してから動かし、表と同じ値が出るかを確かめる練習がおすすめです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、和が10を超えるたびに1が隣の桁へ運ばれていく流れを確かめてみてください。

まとめ¶

科目Bの桁ごとの足し算の問題は、特別な知識を問うものではありません。一の位から順に足し、余りを書いて商を運ぶ、という筆算の手順を表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、3桁どうしくらいの短い足し算で十分です。何度か表を書くうちに、コードを見ただけで、どの行が筆算のどの手順にあたるのかが分かるようになります。

余りはその桁に書き、商は上の桁へ運ぶ。最後に残った繰り上がりも忘れずに書く。 この2つを習慣にしておけば、桁ごとの足し算の問題にも自信を持って向き合えます。次に配列で数を表すコードを見かけたら、まずは一の位がどちらの端にあるかから確かめてみてください。