- 追加された行はこの色です。
- 削除された行はこの色です。
[[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
- どんな自然数も、３つ以下の三角数の和に分解することができる。
例: 10 = 1 + 3 + 6
例: 18 = 6 + 6 + 6
> 同じ三角数を何度も使って分解してよい。
> この定理はガウスによって証明された。
- このような「和への分解」は、自然数によっては２通り以上あるものもある。
例:12 = 1 + 1 + 10
12 = 3 + 3 + 6
例: 12 = 1 + 1 + 10
12 = 3 + 3 + 6
** 作りたいプログラム [#i92b803a]
自然数のうちで、三角数の和に分解したときに、なるべく分解の種類の多いものを求めたい。
以下の指示に従って、順にプログラムを作れ。
~
- (1) n 番目の三角数を計算する関数
int tri(int n)
を作りなさい。そして、自然数 a が与えられたときに、３つの三角数の和に分解して、その値を表示する関数
void sum_of_tri(int a)
を作りなさい。そして、自然数 p が与えられたときに、３つの三角数の和に分解して、その値を表示する関数
void sum_of_tri(int p)
を作りなさい。分解のしかたは、自由に決めてよい。
main() 関数は、
int main(void)
{
sum_of_tri(10);
sum_of_tri(12);
return 0;
}
などとして、動作を確認せよ。
ヒント
for (i=....) {
for (...) {
for (...) {
sum = tri(i) + tri(j) + tri(k);
if (sum == p) {
~
- (2) 自然数 a が与えられたときに、次のような動作をする関数
int num_of_sum_of_tri(int a)
- (2) 自然数 p が与えられたときに、次のような動作をする関数
int num_of_sum_of_tri(int p)
を作りなさい。
-- a を３つ以下の三角数の和に分解する。
-- p を３つ以下の三角数の和に分解する。
-- 分解のバリエーションをすべて調べあげる。
-- 関数の戻り値としては、その分解のバリエーションの種類の数を返す。
-- 具体的な分解のしかたは（関数の戻り値としては）返さなくてよいが、動作確認の意味で表示させるとよい。
> ヒント１：「３つ以下」の部分を、「ちょうど３つ、ただし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) で作った関数を繰り返し呼び出すことで実現できるはずである。
出力例: 12 は 2 通りに分解できます。
出力例: 12 は 3 通りに分解できます。
> num_of_sum_of_tri() 関数が、画面表示をしていると、時間がかかりすぎる。画面表示をやめれば、数秒で結果が出るようになるはずである。
~
- (4) (3) の方法では、結果が出るまでに時間がかかる。もっと早く結果を出す方法を考えよ。
> コンパイル時にオプションをつけると、同じプログラムのままでも実行速度が早くなる。
gcc -O2 hoge.c
のように、"-O2"（マイナス・オー・に）を付け加えるとよい。
ここでは、プログラム上の工夫を期待している。無駄なループを回していないか、無駄な計算を繰り返していないか、あるいはアルゴリズムをがらりと変更してみるとどうなるか、などを検討して欲しい。
> 実行時間を測るには、
./a.exe
を実行する代わりに、
time ./a.exe
と、先頭に "time" を付けて実行すればよい。0.01 秒よりも細かい値が表示されるかもしれないが、かなりの誤差も含んでいる。信頼のおける値は 0.03 秒単位ぐらいである。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
