プログラミングおよび実習II/20051110

[ 高橋のページ ] [ プログラミングおよび実習II? ]

プログラミングおよび実習II 2005年11月10日[edit]

今日の課題: ヒープソート[edit]

解答例?

課題1110-A （締切:11月10日，延長不可）[edit]

11月9日の演習問題を提出しチェックを受けて下さい．

課題1110-B （締切:11月17日）[edit]

整数のデータが与えられたときに，

1. それを配列に格納する
2. それらをヒープソートで並べかえる
3. できた配列の内容を表示する

というプログラムを作りましよう．名前は heapsort.c としてください． これまでの selectionsort.c などと同様に，

• データの数は最大100個
• まずデータの数を入力し，次に各データを順番に入力する

こととします．ただし，以下のことに気をつけて作成して下さい．

• データの並べかえには，課題1110-Aで紙に書いた関数 HeapSort() と11月2日に書いた関数 DownHeap() を使う
• HeapSort() の中では，関数 DownHeap() を呼び出した直後に PrintData2() を呼ぶようにして，並べかえの途中経過がわかるようにして下さい．こんな感じでいい感じ

  printf("ヒープ作ってます♪\n");
  for(...){
    DownHeap(...);
    PrintData2(...);
  }
  printf("\n");
  
  printf("ならべかえてます♪\n");
  for(...){
    交換
    DownHeap(...);
    PrintData2(...);
  }

課題1110-C （締切:11月17日，1110-A,Bを11月10日に提出した人のみ対象のボーナス課題）[edit]

以下の二つのプログラムを作成し動作確認して下さい．

1. フィボナッチ数(Fibonacci number)を計算するプログラム fibonacci.c
   • 自然数nの値を入力するとフィボナッチ数F(n)を計算して表示する
   • F(n)の計算には，「int型の引数を一つ渡すとフィボナッチ数F(n)をint型で返す関数 Fibonacci() 」を使う
   • Fibonacci()は，再帰呼び出しを使って定義する
   • F(n)の定義は，
     • F(n) = F(n-1) + F(n-2) 　　　nが3以上の自然数のとき
     • F(2) = 1
     • F(1) = 1
   • ちなみに，F(10) = 55, F(20) = 6765
2. 二つの自然数の最大公約数(Greatest Common Divisor: GCD)を求めるプログラム gcd.c
   • 二つの自然数aとbを入力するとその最大公約数を計算して表示する
   • 最大公約数の計算には，「int型の引数を二つ渡すとそれらの最大公約数をint型で返す関数 GCD()」を使う
   • GCD()は，ユークリッドの互除法に基づき再帰呼び出しを使って定義する

ユークリッドの互除法のアルゴリズムについては解説しません（検索エンジンで「互除法」「再帰」をキーワードに検索してみるとよいでせう）が，

GCD(a, b) = a　　　　　　　　　　　　　bが0のとき
GCD(a, b) = GCD(b, aをbで割った余り) 　上記以外のとき

です．