1997年度「計算機基礎実験 II」期末試験 (菊地担当) 1997年 1月 23日実施

1. 以下に示した例は 1 から N までの整数の和を求める計算アルゴリズムである。 この例を参考にして以下の問いに答えよ。

   i = 1
   S = 0
   while i < N do
       S = S + i
       i = i + 1
   

   1. 例にならって N の階乗を計算するアルゴリズムを書きなさい。
   2. アルゴリズムに名前をつけることができ、再帰的な記述を許すとしたとき、 階乗を再帰的に計算するアルゴリズム f(n) を書きなさい。
2. ある処理系における実数の精度は、「1 に加えても結果が 1 となる」 最大の数によって推定できる。この数を求めるアルゴリズムを書け。
3. 次のプログラムは配列を用いて LIFOバッファを実現しようとしたものである。 これを読んで以下の問いに答えなさい。

    1: static int stack[100];
    2: static int sp=0;
    3: void push(int);
    4: int  pop(void);
    5: main() {
    6:     int i;
    7:     for ( i = 0; i < 10 ; i++ ) push(i*i);
    8:     for ( i = 0; i < 10 ; i++ ) printf("%d\n",pop());
    9: }
   10: void push(int n) {
   11:     stack[sp] = n;
   12:     sp++;
   13: }
   

   1. pop() 関数を書きなさい。但し、エラーのチェックは必要無い。
   2. push() にはどのようなエラーチェックが必要かを述べよ。
   3. main() の出力を書きなさい。
4. 大小の順に整列したデータから探索をおこなう際に、高速な方法を何と呼ぶか。 またその方法を簡単に説明せよ。