演習問題 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 までの連続する整数の和 (「基礎プロくん」を使うなら, 課題 5)
   二つの正の整数 i, j を入力する. (i < j としておこう) このとき, i + (i+1) + (i+2) + … + j を求めるプログラムを作ろう. ループの構造(for や while) を使ってもいいし, 数学的に式を求めて計算してもよい(等差数列の和だっけ). i と j として, 1 と 4 を入力してみる. 入力は

   1
   4
   

   出力は

   1
   4
   1 + ... + 4 = 10
   

   (出力結果の「+ ... +」の部分は, 文字通りの「+ ... +」とする)

2. j だけ固定する (「基礎プロくん」を使うなら, 課題 6)
   上の 1. では i, j の両方を入力によって固定して計算していたが, j は入力するとして, i の方を 1 から (j-1) まで変化させるプログラムにしてみよう. j として 4 を入力してみる. 入力は

   4
   

   出力は

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

3. i も j も変化させる (「基礎プロくん」を使うなら, 課題 7)
   今度は, i と j の両方をある値まで変化させて, すべての組み合わせに ついてこの「連続和」を求めるプログラムにする. 入力としては, j の上限となる値を与えてみる. j は 2 から上限までの範囲を取ることにしよう. 上限を 4 としてみると, 入力は

   4
   

   出力は

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

   i, j を独立に変化させるには, 二重ループを使う. その使用例は, 第7回の課題の3 (ピタゴラス) にある. (そのときの解説はこちら) ただ, 今回は i の上限は 「j 未満まで」 となることに注意.

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

   55
   

   出力は

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