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

履歴一覧
差分を表示
現在との差分を表示
ソースを表示
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)

三角数の和への分解†

三角数の説明†

三角数とは、正三角形の形に点を並べたときに並ぶ点の数で、次のようなものである。米俵を積み上げた時の横から見た図を想像するとよい。

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

　　　　　　　　　　　　　　　　　　　　　●
　 　　　　　　　　　　　　　●　　　　　●●
　　　　　　　　　●　　　　●●　　　　●●●
　 　　　●　　　●●　　　●●●　　　●●●●
　●　　●●　　●●●　　●●●●　　●●●●●
 ① 1   ② 3    ③ 6       ④ 10        ⑤ 15

→http://www.geocities.jp/yasuko8787/z094.htm

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 = 6 + 6
　  12 = 1 + 1 + 10
　  12 = 3 + 3 + 6
```

↑

作りたいプログラム†

自然数のうちで、三角数の和に分解したときに、なるべく分解の種類の多いものを求めたい。以下の指示に従って、順にプログラムを作れ。

(1) n 番目の三角数を計算する関数
```
int tri(int n)
```
を作りなさい。main() 関数は、
```
int main(void)
{
    int i;
    for (i=1; i<10; i++) printf("tri(%d) = %d\n", i, tri(i));
    return 0;
}
```
などとして、動作を確認せよ。

(2) 自然数 p が与えられたときに、ちょうど３つの三角数の和に分解して、その値を表示する関数
```
void sum_of_tri(int p)
```
を作りなさい。分解のしかたは、自由に決めてよい。少なくとも１通りが表示されればよい。 main() 関数は、
```
int main(void)
{
    sum_of_tri(10);
    sum_of_tri(12);
    return 0;
}
```
などとして、動作を確認せよ。

２つの三角数の和に分解することは、まだ考えなくてよい。（つまり、分解に失敗する例があっても構わない。）

ヒント

 for (....) {
     for (....) {
         for (....) {
             sum = tri(i) + tri(j) + tri(k);
             if (sum == p) {

(3) 自然数 p が与えられたときに、次のような動作をする関数
```
int num_of_sum_of_tri(int p)
```
を作りなさい。
- 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 などは、探索しないように工夫すればよい。

(4) 1000 未満の自然数で、分解の種類がもっとも多いものを求め、その自然数と何通りに分解できるかを表示せよ。（具体的な分解のしかたは表示しなくてよい。） (3) で作った関数を繰り返し呼び出すことで実現できるはずである。
```
出力例: 12 は 3 通りに分解できます。
```

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

(5) 同様に 10000 未満の自然数について調べよ。数秒で結果が出るように工夫せよ。

num_of_sum_of_tri() 関数での探索に、無駄がないか検討せよ。

なお、gcc でのコンパイル時にオプションをつけると、同じプログラムのままでも実行速度が早くなる。
gcc -O2 hoge.c
のように、"-O2"（マイナス・大文字オー・に）を付け加えるとよい。

(6) 同様に 100000 未満の自然数について調べよ。数秒で結果が出るように工夫せよ。無駄な計算を繰り返していないか、あるいはアルゴリズムやデータ構造をがらりと変更してみるとどうなるか、などを検討して欲しい。

Cygwin 環境で実行時間を測るには、
./a.exe
を実行する代わりに、
time ./a.exe
と、先頭に "time" を付けて実行すればよい。0.01 秒よりも細かい値が表示されるかもしれないが、かなりの誤差も含んでいる。信頼のおける値は 0.03 秒単位ぐらいである。

↑

解答の一部†

(3) 例えば 30 ならば次の４通りに分解される。

30 = 0 + 15 + 15
30 = 1 + 1 + 28
30 = 3 + 6 + 21
30 = 10 + 10 + 10

(4)

9?2 は 2? 通りに分解できます。

(5)

9??6 は 8? 通りに分解できます。

(6)

9??92 は 3?3 通りに分解できます。

（注意）? は伏字である。実際には数字１桁（０から９のどれか）である。