演習問題 2 (連続する整数の和)

たとえば, 55 という整数を考えると, これは 1 から 10までの連続した整数の和になる ことはよく知られている. しかし同時に, 55 は 9 から 13 の和でもあり, またさらに 27 から 28 までの和にもなっている.

55 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
55 = 9 + 10 + 11 + 12 + 13
55 = 27 + 28

このように, 与えられた整数 n が, 連続する(2個以上の)整数の和として何通りに 表されるかを求めてみよう.

前の問題同様, 段階的に考えてみる.

1. i から j までの連続する整数の和
   二つの整数 i, j を入力する. (i < j としておこう) このとき, i + (i+1) + (i+2) + … + j を求めるプログラムを作ろう. ループの構造(for や while) を使ってもいいし, 数学的に式を求めて計算してもよい(等差数列の和だっけ). 実行例はこんな感じ:

   i? 1
   j? 4
   1 + ... + 4 = 10
   

   (出力結果の「+ ... +」の部分は, 本当に数を連続して出力しても良いが, めんどうだから文字通りの「+ ... +」でいいことにしよう)

2. 上の 1. では i, j の両方を入力によって固定して計算していたが, j は入力するとして, i の方を 1 から (j-1) まで変化させるプログラムにしてみよう.

   j? 4
   1 + ... + 4 = 10
   2 + ... + 4 = 9
   3 + ... + 4 = 7
   

3. 今度は, i と j の両方をある値まで変化させて, すべての組み合わせに ついてこの「連続和」を求めるプログラムにする. 入力としては, j の上限となる値を与えてみる.

   max_j? 4
   1 + ... + 2 = 3
   1 + ... + 3 = 6
   2 + ... + 3 = 5
   1 + ... + 4 = 10
   2 + ... + 4 = 9
   3 + ... + 4 = 7
   

   i, j を独立に変化させるやりかたは, 第7回でやったかけ算九九の表を思い出そう.

4. そもそもの問題をとくプログラム. 入力として n を与え, i と j を条件を満たす範囲で独立に変化させて, その連続和がちょうど n となる場合だけ出力させればできあがり.

   n? 55
   1 + ... + 10 = 55
   9 + ... + 13 = 55
   27 + ... + 28 = 55
   

5. (余裕があれば) 計算の手間を改善
   この問題も, 考えればいろいろと効率を改善する方法があろう.