2 復習

2.1 再帰関数

[問1]

次に示すフィボナッチ数列の値を計算するプログラムを作成せよ．キーボー ドより$k$の値を入力すれば，$F_k$を計算しディスプレイに出力する．

$$F_k=F_{k-1}+F_{k-2} F_0=0 F_1=1$$

[問2]

ハノイの塔のパズルを解くC言語のプログラムを作成せよ．ハノイの塔とは， 図1のように左端にあるドーナッツ状の円盤を右端に移動さ せるパズルである．次のルールがある．

• 円盤は一度に1枚ずつしか移動できない．
• 柱のないところに円盤を置いてはならない．
• 小さい円盤の上に，大きな円盤を重ねてはならない．

次のように考えると，このパズルは解きやすい．塔を便宜上，移動元(from)， 作業用(work), 移動先(to)に分ける．

1. 移動させるべき円盤が一つの場合，移動元(from)から移動先(to)の塔へ直接移動 させる．
2. 移動させるべき円盤が$n$個$(\geq 2)$の場合
   1. 移送先(to)を作業用に使い，$n-1$枚の円盤を移動元(from)から作 業用(work)へ移動させる．
   2. 移動元(from)の一番下にあった円盤を，移動先(to)へ移動させる．
   3. 移動元(form)を作業用に使い，$n-1$枚の円盤を作業用(work)から， 移動先(to)へ移動させる．

図 1: ハノイの塔

2.2 データ構造

[問1]

以下のような50人分の成績のファイルがある．ファイルの各行には，名字， 名前，英語，数学，情報処理の成績が書かれている．

abe shinzou 87 43 21
Yamamoto Masashi 42 25 91
Hamasaki Ayumi 23 92 41
Kimura Takuya 21 34 45
Shimada Masahiko 78 63 46
残り45人分

これらを構造体を使って管理し，平均点の高い順に学生の情報をディスプ レイに表示するプログラムを作成せよ．表示する情報は，順位，平均点， 名字，名前，英語，数学，情報処理の成績とする．

[問2]

キーボードから正の数列を入力する．負の整数を入力したら，データの終 わりとする．入力した数列をリストに格納し，数列を表示するプログラム を作成せよ．

2.3 ソート

ソートのプログラムを作成する．作成するプログラムのメイン関数の一部は次のようにする．

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N (1000000)

//==========================================================
// メイン関数
//==========================================================
int main(void)
{
  int a[N], i;

  srand((unsigned int)time(NULL));
 
  for(i=0; i<N; i++){
    a[i]=rand();
  }

  //ここで，ソートの関数を呼び出して昇順に並べる．

  return 0;
}

このメイン関数により，配列a[]にランダムな100万個の整数(乱数)が格納される． この乱数を昇順に並び替えることが課題である．以下の問いに答えよ．

[問1]

このメイン関数のsrand((unsigned int)time(NULL));の働きを述べ よ．

[問2]

このメイン関数のa[i]=rand();の働きを述べよ．

[問3]

単純挿入ソートのアルゴリズムで昇順に並び替えるプログラムを書け．先 に示したメイン関数とともに完全に動作するプログラムを書くこと．ソー トの関数のみではダメ．以降，同じ．

[問4]

シェルソートのアルゴリズムで昇順に並び替えるプログラムを書け．

[問5]

クイックソートのアルゴリズムで昇順に並び替えるプログラムを書け．

[問6]

バブルソートのアルゴリズムで昇順に並び替えるプログラムを書け．

[問7]

マージソートのアルゴリズムで昇順に並び替えるプログラムを書け．

ホームページ: Yamamoto's laboratory
著者: 山本昌志