情報1 2006.10.16 第5回：アルゴリズムその2 1 2学期の授業内容 • 状態遷移の設計・実装 – 状態遷移図を使ったプログラムの設計方法 – 状態変数を使ったプログラムの実装方法 • 複数の要素を扱うアルゴリズムの設計・実装 – 並び替え（ソート） – 検索（サーチ） • ミニプロジェクト – 複数メンバーによる協調作業 – スケジューリングとProject Management 2 本日の授業内容 • 課題1「オリジナルアルゴリズム」の実験 – ペアでアルゴリズムを交換する – 各々，30枚の並び替えの実験をする – ワークシートに実験結果を記入する • 課題2「最小値検索法」の実装 – 最小値検索法をSqueak上に実装する – ペアで1つ実装すればよい • 課題1と2は同時並行で進めること（カードは一組しかないので，余っている人は実装に挑戦する） • 時間内に課題1と課題2の両方を提出すること 3 アルゴリズムとは？ • 「なんらかの問題を解くための手順」のことをアルゴリズムという – 今回の問題は「数字の書かれた30枚のカードを順番に並び替える」こと – 他の問題の例「数字の書かれた100枚のカードの最大値を検索する」 4 前回欠席した人 • 最小値検索法の実験をして，Squeak上で実装する • 課題1（オリジナルアルゴリズムの実験）は不要 5 課題1「オリジナルアルゴリズム」の実験 • ペアでワークシートを交換する • 相手が考案したオリジナルアルゴリズムでカードを並び替え，結果を記録する • 相手が考案したオリジナルアルゴリズムに関する考察を行う（最小値検索法，自分の考えたとの比較等） • カードはペアに一組しかないので，順番に実験を行うこと • 余っている人は課題2の最小値検索法の実装に挑戦すること 6 課題2「最小値検索法」の実装 • 別紙「最小値検索法実装シート」を参照のこと • この課題は，オリジナルアルゴリズムの考案とあわせて，中間試験と同じ比率で採点します 7 実装のヒント１ • 処理済束から未処理束へカードを移動するためのスクリプト（リセットスクリプト）を作っておくと，実験がしやすいですよ 8 実装のヒント２ • 「最小値検索法実装シート」の裏にある，フローチャートを1ステップずつ実装していきましょう • 落ち着いてください 9 実装のヒント３ • 全ての並び替えが終わって，スクリプトが自動停止できなくてもOKです 10 実装のヒント４ • フローチャートのはじめの部分を以下のように書き換えることができますねはじめ未処理束の一番上のカードを最小値スペースに移動いいえはい未処理束の全てのカードを調べたか未処理束の一番上のカードをめくる最小値スペースにあるカードを処理済み束に重ねるめくったカードの数値が最小値スペースにあるカードの数値より小さいか等しい 11 今日の授業はおしまいお疲れ様でした 12