next up previous contents index
: ユークリッドの互除法とその計算量 : 制御構造とやさしいアルゴリズム : 効率的なプログラムを書くには?   目次   索引

章末の問題

問題 1: 配列にはいったデータのなかで, $i$ 番目に大きいデータを 戻すプログラムを書きなさい. (素朴な方法だと, 配列の大きさが大きくなるとなかなか実行が終らない. 第 14 章を学習してから改めてこの問題を考えてみる とよい. )

問題 2: 数学の本に書いてあることから, 適当な題材をえらび プログラムに書いてみなさい. 外積のような面倒なものの計算をやらせてもいいし, ヤコビ行列式の計算をやらせてみてもいい. 微分は関数 diff で可能. なお Risa/Asir では $\frac{f}{g}$ なる形の有理式の計算もできるが, 通分は 重たい計算なので自動的にはやらない. 関数 red を用いて通分を行う必要がある. たとえば次の例をみよ.

[344] H=(x-1)/(x^2-1); 
(x-1)/(x^2-1)
[345] red(H);
(1)/(x+1)

問題 3:
次のプログラムの出力値を答えよ.

def main() {
   C = 10;
   D = (C > 5? 100 : 200);
   print(D);
}

問題 4:
次のプログラムの出力を書きなさい.

def main() {
  A = newmat(10);
  I=0; J = 0;
  while (I<9) {
     A[++I] = J;
     J++;
  }
  print(A[3]);
}

問題 5:
3 次方程式 $x^3+Ax^2+Bx+C=0$ の実根を Newton 法で求めるプログラムを書け.
ヒント: この問題は本格的なパッケージ関数の開発へのチャレンジである. ささやかながら ``プログラムの開発'' の経験ができる. プログラムの開発は段階をおって進むものである. 次のような順番にしたがい開発をすすめよう.

  1. レベル 1      とりあえず一根を求める. 反復が停止しないなどという失敗も有り得る.

  2. レベル 2      実根の個数をあらかじめ調べ, 場合分けして初期値を適切に設定し, 重根がない場合に全実根を求める.

  3. レベル 3      重根をとりあつかう.

ヒント 2: $f(x) = x^3+Ax^2+Bx+C$ に対し, $f(x)=0$ の解を Newton 法で求める 場合の初期値は次のように決められる.

  1. $\forall x, f'(x) > 0$ の場合

  2. $\exists x, f'(x) = 0$ の場合

    $f'(\alpha) = 0$, $f'(\beta) = 0$ ( $\alpha < \beta$) とすると $f(x)$$x=\alpha$ で極大, $x=\beta$ で極小.

    1. $f(\beta) > 0$ の場合 解は一つ. $x_0 < \alpha$ からスタート.
    2. $f(\alpha) < 0$ の場合 解は一つ. $x_0 > \beta$ からスタート.
    3. $f(\alpha) > 0, f(\beta) < 0$ の場合 解は三つ. $x_0 > \beta$, $x_0 < \alpha$, $x_0 = (\alpha+\beta)/2$ のそれぞれからスタート.

ヒント 3: 前のヒントのように初期値を選べば, 重根 を持たない場合にはちゃんと解が得られる. $f'(x)$ が常に正か どうかは高校数学でおなじみの判別式でわかる. 重根がある かどうかは微妙な問題なので, ない場合に動くプログラムが 書けていればそれでよい.

注意すべき点は, 初期値, 係数全てが有理数の場合, Newton 法の 全ての計算が有理数で行われてしまい, 異常に時間がかかった挙げ句 巨大な分母分子を持つ値が得られることがある. このようなことを避けるために, 初期値は X=eval(A*exp(0)) あるいは X=deval(A) として, 強制的に浮動小数に変えるとよい.

数値計算を多用すると次のようなエラーに出会うことがある.

 ***   the PARI stack overflows !
  current stack size: 65536 (0.062 Mbytes)
  [hint] you can increase GP stack with allocatemem()
このようなエラーが出た場合には,
[295] pari(allocatemem,10^7)$
などを実行して, pari の使用できるメモリを増やすこと.

Nobuki Takayama 平成15年9月12日