![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105,...
n * (n+1) / 2
例: 10 = 1 + 3 + 6 例: 18 = 6 + 6 + 6
同じ三角数を何度も使って分解してよい。
この定理はガウスによって証明された。
例:12 = 1 + 1 + 10 12 = 3 + 3 + 6
以下の指示に従って、順にプログラムを作れ。
int tri(int n)を作りなさい。そして、自然数 a が与えられたときに、３つの三角数の和に分解して、その値を表示する関数
void sum_of_tri(int a)を作りなさい。分解のしかたは、自由に決めてよい。 main() 関数は、
int main(void)
{
sum_of_tri(10);
sum_of_tri(12);
return 0;
}
などとして、動作を確認せよ。int num_of_sum_of_tri(int 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 などは、探索しないように工夫すればよい。
出力例: 12 は 2 通りに分解できます。
num_of_sum_of_tri() 関数が、画面表示をしていると、時間がかかりすぎる。画面表示をやめれば、数秒で結果が出るようになるはずである。
コンパイル時にオプションをつけると、同じプログラムのままでも実行速度が早くなる。
gcc -O2 hoge.cのように、"-O2"（マイナス・オー・に）を付け加えるとよい。
ここでは、プログラム上の工夫を期待している。無駄なループを回していないか、無駄な計算を繰り返していないか、あるいはアルゴリズムをがらりと変更してみるとどうなるか、などを検討して欲しい。
実行時間を測るには、
./a.exeを実行する代わりに、
time ./a.exeと、先頭に "time" を付けて実行すればよい。0.01 秒よりも細かい値が表示されるかもしれないが、かなりの誤差も含んでいる。信頼のおける値は 0.03 秒単位ぐらいである。
