![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[Cygwinでデバッグ/例題2]] * 三角数の和への分解 [#ha7ce12a] ** 三角数の説明 [#n94a6c7c] - 三角数とは、正三角形の形に点を並べたときに並ぶ点の数である。 三角数は無数にあり、最小のものは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 ** 作りたいプログラム [#i92b803a] 以下の指示に従って、プログラムを作れ。 - (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 秒単位ぐらいである。
