Cygwinでデバッグ/例題2

Cygwinでデバッグ/例題2

三角数の和への分解†

三角数の説明†

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

  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

• どんな自然数も、３つ以下の三角数の和に分解することができる。

  例:  9 = 3 + 6
  例: 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" を付けて実行すればよい。出力例は以下のようになる。

real	0m0.020s
user	0m0.008s
sys	0m0.004s

real の欄はバックグラウンドで動くプログラムの影響を受けて長くなることがあるので、user の欄の値で判断すればよい。どの数値も 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 通りに分解できます。

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

最新の20件