体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

問題のおさらい

9606+91377 という足し算を筆算で行いましょう。下のようになります。

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

この計算では繰り上がりがあります。
例えば、一の位を足すと 6+7=13 です。このとき、十の位に 1 を繰り上げます。
十の位は、繰り上げた 1 を足して、1+0+7=8 と計算します。
同様に、千から一万の位、一万から十万の位でも繰り上がりがあります。
この計算では、計 3 回の繰り上がりがあります。

同様に、71+19 の計算では 1 回、99999+1 の計算では 5 回の繰り上がりがあります。

自然数 n と c に対し、0 以上 10n 未満の整数から 2 つ選び、
この 2 つを足し算したときの繰り上がりの回数がちょうど c 回となるものの個数を F(n, c) と定義します。

例えば F(1, 1)=45 です。0 以上 10 未満の 2 つの整数の足し算で、繰り上がりがちょうど 1 回となるものは以下の 45 個です。

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

同様に、F(1, 0)=55, F(2, 0)=3025, F(2, 1)=4500, F(2, 2)=2475, F(3, 1)=358875 となることが確かめられます。

標準入力から、自然数 n と c (1 ≦ n ≦ 8 かつ 0 ≦ c ≦ n)が空白区切りで与えられます。
標準出力に F(n, c) を出力するプログラムを書いてください。

一つ前の状態に注目して漸化式を導こう

足し算の繰り上がりに関する問題です。素朴に思いつく方法としては、n 桁以下の 2 整数を列挙して、実際に足し算を行ってみるやり方があります。しかし本問では n の上限は 8 です。最大で 108×108=1016 通りの足し算をチェックする必要があり、時間がかかり過ぎてしまいます。

そこで役に立つのが、一つ手前の状態を考えることです。同様の考え方はこれまで何度か登場しました。(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。n 桁の二数の足し算を考えるとき、n-1 桁のときの結果をうまく利用できないか、考えてみましょう。

そこで、関数 G(n, c, k) を新たに定義します。n 桁以下の 2 整数の足し算のうち、繰り上がりの回数が c 回であり、n+1 桁目への繰り上がりが k (0 または 1)であるものの個数を G(n, c, k) とします。

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

この G(n, c, k) を、n-1 桁目までの結果を使って表しましょう。次の桁への繰り上がりが ①ある場合と ②ない場合とに分けて考えます。

① 次の桁への繰り上がりがある場合を考えます。(a) 前の桁からの繰り上がりがあるときは、n 桁目の 2 数の和が 9 以上であれば次への繰り上がりが生じます。そのような可能な 2 数の組み合わせは 55 通りあります。一方、(b) 前の桁からの繰り上がりがないときは、n 桁目の2数の和が 10 以上であれば次への繰り上がりが生じます。そのような 2 数の組み合わせは 45 通りあります。したがって、下記の関係が言えます。

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

② 次の桁への繰り上がりがない場合を考えます。(a) 前の桁からの繰り上がりがあるときは、n 桁目の 2 数の和が 8 以下(45 通り)であれば次への繰り上がりは生じません。(b) 前の桁からの繰り上がりがないときは、n 桁目の2数の和が 9 以下(55 通り)であれば、次への繰り上がりは生じません。したがって、下記の関係が言えます。

1 2次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。