_ProgII2007/wakame
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[takataka]] | [[ProgII2007]] | [[ProgII2007/1116]]
*わけわかめ？ [#t9f78554]
#contents
**まずは [#i6255d89]
[[ProgII2007/1116]]を良く読んで課題をちゃんと把握しよう．
**そして早速 [#ad566f84]
プログラム書き始めよう．
ヒープソートやクイックソートの関数どう書いたらいいか分からへんとしても，そんなのは後回し．
まずは，キーボードからいくつか数値を入力したら，それらをそのまま（並べかえもせずに）出力するだけのプログラムを作ってみよう．そこからだんだん追加してって最終的にちゃんとしたプログラムになればそれでよいのです．
いろいろ追加していったらそのまま完成版にできるように，hsort.cという名前のソースファイルを作り，以下のようにしてみよう．
http://tortoise1.math.ryukoku.ac.jp/~takataka/course2007/prog2/hogesort2.c.png
このプログラムを入力／コンパイル／バグ取りできたら，実行して，キーボードから
1 2 3 4 5 a
と入力して[Enter]を押してみよう．こんな出力になるはず．
[ 1] [ 2] [ 3] [ 4] [ 5]
最後の英字は無視して5個の数値だけが配列に格納され（この辺のちゃんとした説明は[[ProgII2007/1019]]の課題Fにあります），PrintData() を呼ぶことでそれらが出力されていることが分かります．
これでもう「キーボードから数値を入力したらそれらをそのまま出力する」プログラムできちゃいました．ということは，後は，以下のことをすれば完成です．
-ソートを実行する関数の定義を書く（このソースの31行目以降に書き足す）
-main()中でその関数を呼ぶ（16行目）
-関数のプロトタイプ宣言を書く（2 or 4行目）（プロトタイプ宣言については，10月25日の講義資料に解説があります）
**ひぷ〜 [#e1025096]
まずはヒープソートを考えてみよう．
***「ひぷ」のまえに「だひ」 [#ya71edb7]
今回考えているプログラムでは，ヒープソートは次の二つの関数によって実現します．
-DownHeap() 「root番目の値を下ろしていく」処理を行う関数
-HeapSort() ヒープソート全体の処理を行う関数．中で何度も DownHeap() を呼ぶ
いきなり全部完成させようとするのは無謀です．
ちょっとずつこつこつ完成させましょう．
ということは，まず目標にするのは，「キーボードから数値を入力したらそれらに対してDownHeap()を一度行い，結果を出力する」プログラムです．
つまり，[[ProgII2007/1026]]の課題Bをやりなさい，ということです．次のようにしてみよう．
上で作った hsort.c を次のように改造してみよう．
-31行目以降に DownHeap() の定義を書く（●注）
-16行目で DownHeap() を呼ぶ．次のようにしてみよう
DownHeap(a, 0, 4);
-2 or 4行目にプロトタイプ宣言を書く
できたら，[[ProgII2007/1026]]に示しているのと同じ例
99 50 87 71 63 41
を入力に使って実行してみよう．正しい結果が得られましたか？
念のために言っておきますが，DownHeap() 一度やっただけで配列全体が並べかえられたりしませんよ．
どうなると正しいのかは，講義ちゃんと聞いてた人はokですね．
さらに確認したい人は，[[ProgII2007/1026]]に示してあるもう一つの例も試してみて下さい．
16行目を DownHeap(a, 0, 3); に変えて，
99 63 87 71 50 41
を使って実行してみる，ということです．
●注 さすがに「DownHeap()ってどう書いたらいいの？」ってとこまでは解説しませんので，そこは講義資料を復習するなりTAさんに尋ねるなりオフィスアワーに高橋に助けを求めるなりして下さい．
***「ひぷ」 [#qaf28354]
上記ができたら，きっと DownHeap() はok，ってことでしょうから，次に進みましょう．
次は，このソースにさらに関数 HeapSort() を追加します．
ここは，いきなり HeapSort() の完成型を考えるのではなく，次のようにしてみましょう．
-次のような関数 HeapSort() の定義を DownHeap() の定義の下（別に上でも構いません）に書く
#pre{{
void HeapSort(int data[], int n)
{
DownHeap(data, 2, n-1);
DownHeap(data, 1, n-1);
DownHeap(data, 0, n-1);
}
}}
-16行目で HeapSort() を呼ぶ．DownHeap(a, ...); を削除して，かわりに次のようにする
HeapSort(a, n);
-HeapSort()のプロトタイプ宣言を追加する
できたら，5個か6個の適当な数値を入力して実行してみて下さい．
数値の並びがどのようになっていても，数値の個数が5 or 6個であれば，出力は必ずヒープになっているはずです．
またもや念のために言っておきますが，上記の HeapSort() の定義は，この関数の完成型ではありません．
ここでやってることは，[[ProgII2007/1026]]課題Cの変形バージョンです．
上記のことができたら，HeapSort() の定義を正しいものに書き換えましょう．
これまたさすがに「HeapSort()ってどう書いたらいいの？」ってとこまでは解説しませんので，そこは講義資料を復習するなりTAさんに尋ねるなりオフィスアワーに高橋に助けを求めるなりして下さい．
***仕上げ [#jf6e6792]
ここまでで，hsort.c は，入力された値をヒープソートした結果を出力するプログラムになっているはずです．
ただし，[[ProgII2007/1116]]の課題Aの実行例を見るとわかるように，この課題では，ただソート結果を出力するだけでなく，途中経過も表示することを求めています（プログラムを作ってる人がバグ取りしやすいように／動作を理解しやすいようにするため）．
したがって，HeapSort() 中の適当な場所で PrintData() を呼ぶようにしたりして，同様の出力が得られるように改造してみて下さい．
**919 [#e755441d]
次はクイックソートです．
まずは [[ProgII2007/1109]]の課題Bのプログラムを作りましょう．
それができたら，ちょいちょいっと直したらクイックソートの出来上がり．あとは，[[ProgII2007/1116]]の課題Bの実行例を確認しておきましょう．
終了行:
[[takataka]] | [[ProgII2007]] | [[ProgII2007/1116]]
*わけわかめ？ [#t9f78554]
#contents
**まずは [#i6255d89]
[[ProgII2007/1116]]を良く読んで課題をちゃんと把握しよう．
**そして早速 [#ad566f84]
プログラム書き始めよう．
ヒープソートやクイックソートの関数どう書いたらいいか分からへんとしても，そんなのは後回し．
まずは，キーボードからいくつか数値を入力したら，それらをそのまま（並べかえもせずに）出力するだけのプログラムを作ってみよう．そこからだんだん追加してって最終的にちゃんとしたプログラムになればそれでよいのです．
いろいろ追加していったらそのまま完成版にできるように，hsort.cという名前のソースファイルを作り，以下のようにしてみよう．
http://tortoise1.math.ryukoku.ac.jp/~takataka/course2007/prog2/hogesort2.c.png
このプログラムを入力／コンパイル／バグ取りできたら，実行して，キーボードから
1 2 3 4 5 a
と入力して[Enter]を押してみよう．こんな出力になるはず．
[ 1] [ 2] [ 3] [ 4] [ 5]
最後の英字は無視して5個の数値だけが配列に格納され（この辺のちゃんとした説明は[[ProgII2007/1019]]の課題Fにあります），PrintData() を呼ぶことでそれらが出力されていることが分かります．
これでもう「キーボードから数値を入力したらそれらをそのまま出力する」プログラムできちゃいました．ということは，後は，以下のことをすれば完成です．
-ソートを実行する関数の定義を書く（このソースの31行目以降に書き足す）
-main()中でその関数を呼ぶ（16行目）
-関数のプロトタイプ宣言を書く（2 or 4行目）（プロトタイプ宣言については，10月25日の講義資料に解説があります）
**ひぷ〜 [#e1025096]
まずはヒープソートを考えてみよう．
***「ひぷ」のまえに「だひ」 [#ya71edb7]
今回考えているプログラムでは，ヒープソートは次の二つの関数によって実現します．
-DownHeap() 「root番目の値を下ろしていく」処理を行う関数
-HeapSort() ヒープソート全体の処理を行う関数．中で何度も DownHeap() を呼ぶ
いきなり全部完成させようとするのは無謀です．
ちょっとずつこつこつ完成させましょう．
ということは，まず目標にするのは，「キーボードから数値を入力したらそれらに対してDownHeap()を一度行い，結果を出力する」プログラムです．
つまり，[[ProgII2007/1026]]の課題Bをやりなさい，ということです．次のようにしてみよう．
上で作った hsort.c を次のように改造してみよう．
-31行目以降に DownHeap() の定義を書く（●注）
-16行目で DownHeap() を呼ぶ．次のようにしてみよう
DownHeap(a, 0, 4);
-2 or 4行目にプロトタイプ宣言を書く
できたら，[[ProgII2007/1026]]に示しているのと同じ例
99 50 87 71 63 41
を入力に使って実行してみよう．正しい結果が得られましたか？
念のために言っておきますが，DownHeap() 一度やっただけで配列全体が並べかえられたりしませんよ．
どうなると正しいのかは，講義ちゃんと聞いてた人はokですね．
さらに確認したい人は，[[ProgII2007/1026]]に示してあるもう一つの例も試してみて下さい．
16行目を DownHeap(a, 0, 3); に変えて，
99 63 87 71 50 41
を使って実行してみる，ということです．
●注 さすがに「DownHeap()ってどう書いたらいいの？」ってとこまでは解説しませんので，そこは講義資料を復習するなりTAさんに尋ねるなりオフィスアワーに高橋に助けを求めるなりして下さい．
***「ひぷ」 [#qaf28354]
上記ができたら，きっと DownHeap() はok，ってことでしょうから，次に進みましょう．
次は，このソースにさらに関数 HeapSort() を追加します．
ここは，いきなり HeapSort() の完成型を考えるのではなく，次のようにしてみましょう．
-次のような関数 HeapSort() の定義を DownHeap() の定義の下（別に上でも構いません）に書く
#pre{{
void HeapSort(int data[], int n)
{
DownHeap(data, 2, n-1);
DownHeap(data, 1, n-1);
DownHeap(data, 0, n-1);
}
}}
-16行目で HeapSort() を呼ぶ．DownHeap(a, ...); を削除して，かわりに次のようにする
HeapSort(a, n);
-HeapSort()のプロトタイプ宣言を追加する
できたら，5個か6個の適当な数値を入力して実行してみて下さい．
数値の並びがどのようになっていても，数値の個数が5 or 6個であれば，出力は必ずヒープになっているはずです．
またもや念のために言っておきますが，上記の HeapSort() の定義は，この関数の完成型ではありません．
ここでやってることは，[[ProgII2007/1026]]課題Cの変形バージョンです．
上記のことができたら，HeapSort() の定義を正しいものに書き換えましょう．
これまたさすがに「HeapSort()ってどう書いたらいいの？」ってとこまでは解説しませんので，そこは講義資料を復習するなりTAさんに尋ねるなりオフィスアワーに高橋に助けを求めるなりして下さい．
***仕上げ [#jf6e6792]
ここまでで，hsort.c は，入力された値をヒープソートした結果を出力するプログラムになっているはずです．
ただし，[[ProgII2007/1116]]の課題Aの実行例を見るとわかるように，この課題では，ただソート結果を出力するだけでなく，途中経過も表示することを求めています（プログラムを作ってる人がバグ取りしやすいように／動作を理解しやすいようにするため）．
したがって，HeapSort() 中の適当な場所で PrintData() を呼ぶようにしたりして，同様の出力が得られるように改造してみて下さい．
**919 [#e755441d]
次はクイックソートです．
まずは [[ProgII2007/1109]]の課題Bのプログラムを作りましょう．
それができたら，ちょいちょいっと直したらクイックソートの出来上がり．あとは，[[ProgII2007/1116]]の課題Bの実行例を確認しておきましょう．
ページ名:
![[PukiWiki]](image/blackuni3-80x80.png "[PukiWiki]")
