[[Cygwinでデバッグ/例題2]] * 三角数の和への分解 [#ha7ce12a] ** 三角数の説明 [#n94a6c7c] - 三角数とは、正三角形の形に点を並べたときに並ぶ点の数である。米俵を積み上げた時の横から見た図を想像するとよい。 →http://www.geocities.jp/yasuko8787/z094.htm 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105,... - n 番目の三角数は次の公式で求められる。→http://kotobank.jp/word/%E4%B8%89%E8%A7%92%E6%95%B0 n * (n+1) / 2 - どんな自然数も、3つ以下の三角数の和に分解することができる。 例: 10 = 1 + 3 + 6 例: 18 = 6 + 6 + 6 > 同じ三角数を何度も使って分解してよい。 > この定理はガウスによって証明された。 - このような「和への分解」は、自然数によっては2通り以上あるものもある。 例:12 = 1 + 1 + 10 12 = 3 + 3 + 6 ** 作りたいプログラム [#i92b803a] 以下の指示に従って、順にプログラムを作れ。 ~ - (1) n 番目の三角数を計算する関数 int tri(int n) を作りなさい。そして、自然数 a が与えられたときに、3つの三角数の和に分解して、その値を表示する関数 void sum_of_tri(int a) を作りなさい。分解のしかたは、自由に決めてよい。 main() 関数は、 int main(void) { sum_of_tri(10); sum_of_tri(12); return 0; } などとして、動作を確認せよ。 ~ - (2) 自然数 a が与えられたときに、次のような動作をする関数 int num_of_sum_of_tri(int a) を作りなさい。 -- a を3つ以下の三角数の和に分解する。 -- 分解のバリエーションをすべて調べあげる。 -- 関数の戻り値としては、その分解のバリエーションの種類の数を返す。 -- 具体的な分解のしかたは(関数の戻り値としては)返さなくてよいが、動作確認の意味で表示させるとよい。 > ヒント1:「3つ以下」の部分を、「ちょうど3つ、ただし0が混じってもよい」と解釈すると、プログラムが簡単になる。「tri(0) = 0」 なので都合がよい。 例: 6 = 0 + 0 + 6 6 = 0 + 3 + 3 > ヒント2:重複する分解は、うまくループを回すことで、候補から除外できる。 例: 10 = 1 + 3 + 6 で1通りと数えるとすると、 10 = 1 + 6 + 3 や、 10 = 3 + 1 + 6 などは、探索しないように工夫すればよい。 ~ - (3) 10000 未満の自然数で、分解の種類がもっとも多いものを求め、その自然数と何通りに分解できるかを表示せよ。(具体的な分解のしかたは表示しなくてよい。) (2) で作った関数を繰り返し呼び出すことで実現できるはずである。 出力例: 12 は 2 通りに分解できます。 > num_of_sum_of_tri() 関数が、画面表示をしていると、時間がかかりすぎる。画面表示をやめれば、数秒で結果が出るようになるはずである。 ~ - (4) (3) の方法では、結果が出るまでに時間がかかる。もっと早く結果を出す方法を考えよ。 > コンパイル時にオプションをつけると、同じプログラムのままでも実行速度が早くなる。 gcc -O2 hoge.c のように、"-O2"(マイナス・オー・に)を付け加えるとよい。 ここでは、プログラム上の工夫を期待している。無駄なループを回していないか、無駄な計算を繰り返していないか、あるいはアルゴリズムをがらりと変更してみるとどうなるか、などを検討して欲しい。 > 実行時間を測るには、 ./a.exe を実行する代わりに、 time ./a.exe と、先頭に "time" を付けて実行すればよい。0.01 秒よりも細かい値が表示されるかもしれないが、かなりの誤差も含んでいる。信頼のおける値は 0.03 秒単位ぐらいである。