Cygwinでデバッグ/例題2 の履歴(No.1)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Cygwinでデバッグ/例題2 へ行く。
  • 1 (2012-12-18 (火) 04:25:17)
  • 2 (2012-12-18 (火) 05:51:46)
  • 3 (2012-12-18 (火) 14:18:31)
  • 4 (2012-12-19 (水) 12:10:09)
  • 5 (2012-12-20 (木) 12:30:05)
  • 6 (2012-12-20 (木) 12:30:05)
  • 7 (2013-10-23 (水) 02:08:12)
  • 8 (2013-12-10 (火) 23:48:40)

Cygwinでデバッグ/例題2

三角数の和への分解†

三角数の説明†

• 三角数とは、正三角形の形に点を並べたときに並ぶ点の数である。 三角数は無数にあり、最小のものは1である。

  1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105,...

• n 番目の三角数は次の公式で求められる。

  n * (n+1) / 2

• どんな自然数も、３つ以下の三角数の和に分解することができる。

  例: 10 = 1 + 3 + 6

  この定理はオイラーによって証明された。

• このような「和への分解」は、自然数によっては何通りもある。

  例:12 = 1 + 1 + 10
  　 12 = 3 + 3 + 6

作りたいプログラム†

以下の指示に従って、プログラムを作れ。

• (1) n 番目の三角数を計算する関数

  int tri(int n)

  を作りなさい。そして、自然数 a が与えられたときに、３つの三角数の和に分解して、その値を表示する関数

  void sum_of_tri(int a)

  を作りなさい。分解の仕方は、自由にしてよい。

• (2) 自然数 a が与えられたときに、次のような動作をする関数

  int num_of_sum_of_tri(int a)

  を作りなさい。
  • a を３つ以下の三角数の和に分解する。
  • 分解のバリエーションをすべて調べあげる。
  • 関数の戻り値としては、その分解のバリエーションの種類の数を返す。
  • 具体的な分解のしかたは（関数の戻り値としては）返さなくてよいが、動作確認の意味で表示させるとよい。

ヒント１：「３つ以下」の部分を、「0が混じってもよい」と解釈すると、プログラムが簡単になる。「tri(0) = 0」 なので都合がよい。

例: 6 = 0 + 0 + 6
　  6 = 0 + 3 + 3

ヒント２：重複する分解は、うまくループを回すことで、候補から除外できる。

例: 10 = 1 + 3 + 6 で１通りと数えるとすると、
　  10 = 1 + 6 + 3 や、
　  10 = 3 + 1 + 6 などは、探索しないように工夫する。

• (3) 10000 未満の自然数で、分解の種類がもっとも多いものを求めよ。 (2) で作った関数を繰り返し呼び出すことで実現できるはずである。

  num_of_sum_of_tri() 関数が、画面表示をしていると、時間がかかりすぎる。画面表示をやめれば、数秒で結果が出るようになるはずである。

• (4) (3) の方法では、結果が出るまでに時間がかかる。もっと早く結果を出す方法を考えよ。

コンパイル時にオプションをつけると、同じプログラムのままでも実行速度が早くなる。

gcc -O2 hoge.c

のように、"-O2"（マイナス・オー・に）を付け加えるとよい。

実行時間を測るには、

./a.exe

を実行する代わりに、

time ./a.exe

と、先頭に "time" を付けて実行すればよい。0.01 秒よりも細かい値が表示されるかもしれないが、かなりの誤差も含んでいる。実用上あてにできる値は 0.03 秒単位ぐらいである。