* 練習問題(アルゴリズム編) [#ie6e4d2a]
#contents
* これは何？ [#m9215c91]
[[練習問題(通常編)>練習問題]]もご覧ください。~
練習問題を集めてみました。~
言語は問いません。入力出力は特に問いません。~
キー入力でもファイルでもソースにべた書きでもいいです。
答えは誰かが書いてくれます。それまではスレで聞いてください。
問題が増えてきたのである程度汎用性のあるものはこちらに書くようにしてみてはどうでしょう
** 問題一覧 [#b29311d7]
***二分探索木 [#gee8e444]
二分探索木とは二つの枝を持つ木構造で、あるノードの値よりその左の枝のノードの値の方が小さく、右の枝のノードの値の方が大きいという規則からなるものです。
例
[5]
[3] [8]
[2] [4] [7] [9]
参考
[[2分探索木-wikipedia:http://ja.wikipedia.org/wiki/2%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8]]
課題1 整数を保持するノードからなる二分探索木を生成するプログラム作って下さい。指定の値をもつノードを追加するadd, 探索するsearch, 削除するdeleteの3つの関数（メソッド）を作りましょう。
ヒント：C言語であれば構造体を、Javaであればクラスを1つのノードと考えましょう。
課題2 線形リストと二分探索木を比較し、二分探索木のメリットを答えて下さい。（線形リストとは配列のように一列で値を保持するものです。）
課題3 1から7の値を二分探索木に登録する場合、二分探索木が最も機能する登録の順序と最も機能しない登録の順序を答えて下さい。
物足りない人はどのようにすれば2文探索木としての構造を壊さずに登録の順序による差を解消できるかを答えて下さい。
***赤黒木 [#j0c1e4de]
課題1 赤黒木について調べ、整数を保持するノードからなる赤黒木を生成するプログラム作って下さい。指定の値をもつノードを追加するadd, 探索するsearch, 削除するdeleteの3つの関数（メソッド）を作りましょう。
ちなみに俺もパッとはできません
***クイックソート [#q8e0119e]
課題1 クイックソートを行う関数を書きなさい~
ただしピボット（分割基準となる要素）は先頭要素とします~
[[参考:http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88]]
- 解答例
--[[Python>プログラミング言語/Python/コードスニペット#bf7d68a1]]
--[[Haskell>/練習問題/解答例/Haskell/練習問題解答例#w101147e]]
課題2 1〜10の数字に対してクイックソートを行った場合、最もソートに手間のかかる並びを答えなさい。可能であればその場合計算時間のオーダーを求めなさい
***スタック [#f8a64b49]
スタックを用いて後置記法で書かれた数式を計算するプログラムを書きなさい。~
なお、入力は整数, +, -, *, /, %からなる式とし、出力は浮動小数点数にすること。~
入力は下記のようにコマンドライン引数として受け取る形でも良い物とする。
$ ./a.out 1 2 + 3 * 4 5 + -
また、0による割算は考慮しなくても良い物とする。
-解答例
--[[Ruby版>プログラミング言語/Ruby/初心者用課題解答例#g581d449]]←リンク切れ
--[[Ruby版>./解答例/後置記法/Ruby]]
--[[Python版>./解答例/後置記法/Python]]
--[[Perl版>http://vipprog.net/wiki/prog_lang/perl.html#d2cf07b1]]
**解答例 [#y3e7a186]
[[別ページ>練習問題/解答例]]に記載
