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

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

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

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

課題1110-A（締切： 今日の実習開始後すぐ，締切後チェック対象外） †[edit]

11月9日の演習問題のプリントを提出し，チェックを受けてください．

課題1110-B（締切： 今日の実習終了時） †[edit]

ヒープソートのプログラムを完成させ，動作確認ができたらチェックをうけてください． ただし，ソースは，課題1020-Aを参考にして，以下の仕様にしたがって作成して下さい．

• 関数HeapSort()とDownHeap()を定義した（main()は含まない）ソースファイル hsort.c を作成する
• グローバル変数nswapを用いて，交換回数をカウントする
• hsort.cと，以前作成した printdata.c, sortmain.c を分割コンパイル／リンクして，ヒープソートプログラムの実行形式をつくる
• DownHeap()を呼ぶ度に（直後に）PrintData()を呼んで途中経過を表示させる．こんな感じの出力になるようにするとよいかも

  得点は何件ありますか？ : 6
  0番目の得点を入力してください : 33
  1番目の得点を入力してください : 59
  2番目の得点を入力してください : 60
  3番目の得点を入力してください : 60
  4番目の得点を入力してください : 77
  5番目の得点を入力してください : 100
  
  ##### 元のデータ #####
   [ 33] [ 59] [ 60] [ 60] [ 77] [100]
  
  ##### 並べかえ中 #####
  ヒープつくってます♪
   [ 33] [ 59] [100] [ 60] [ 77] [ 60]
                 （中略）
   [100] [ 77] [ 60] [ 60] [ 59] [ 33]
  
  ならべかえてます♪
   [ 77] [ 60] [ 60] [ 33] [ 59] [100]
                 （中略）
   [ 33] [ 59] [ 60] [ 60] [ 77] [100]
  
  ##### 並べかえ結果 #####
   [ 33] [ 59] [ 60] [ 60] [ 77] [100]
  交換回数 = 14
  

課題1110-C（締切： 来週の実習終了時，締切後チェック対象外） †[edit]

void hoge(int x[], int first, int last)
{
  int i;

  i = (first+last)/2;
  if(first <= i-1) hoge(x, first, i-1);
  printf(" %d", x[i]);
  if(i+1  <= last) hoge(x, i+1, last);
}

上記の関数hoge()が，x[0] = 0, x[1] = 11, x[2] = 22, x[3] = 33, first = 0, last = 3 として呼び出されたとすると，どのような出力が得られるか答えなさい．