14 集合データ構造とアルゴリズム

14.1 学習目標

• 入れ物を使ったプログラムが書けるようになる
• ソートプログラムが作れるようになる

14.2 入れ物を使ったプログラム

14.2.1 カードを出し入れするプログラム

このプログラムは、１０枚のカードを入れ物１に入れ、１枚ずつ取り出して入れ物２に移すプログラムです。

ここをクリックすると、以下のプログラムをダウンロードできます。

  1: ※プログラム名：カードを入れ物Ａから入れ物Ｂに移動するプログラム
  2: ※作成者：岡田健
  3: ※作成日：2010/6/6
  4: 
  5: ※授業に必要なライブラリを取り込む。
  6: TurtleLibraryを参照する。
  7: 
  8: ※環境を初期化する。
  9: ウィンドウを初期化する。
 10: 
 11: 入れ物を新規作成して、箱Ａと名付ける。
 12: 入れ物を新規作成して、箱Ｂと名付ける。
 13: ウィンドウに箱Ａを追加する。
 14: ウィンドウに箱Ｂを追加する。
 15: 
 16: 初期化するとは｛
 17: 
 18: 	ウィンドウの横幅を550に設定する。
 19: 	ウィンドウの縦幅を300に設定する。
 20: 
 21: 	箱Ａのｘ座標を５０に設定する。
 22: 	箱Ａのｙ座標を５０に設定する。
 23: 	箱Ｂのｘ座標を５０に設定する。
 24: 	箱Ｂのｙ座標を１００に設定する。
 25: 
 26: 	整数型を新規作成して、ｘと名付ける。
 27: 	ｘに０を入れる。
 28: 	ｘ＜１０である限り｛
 29: 		カードを新規作成して、カードＡと名付ける。
 30: 		カードＡにｘ×１０を設定する。
 31: 		箱Ａの最後にカードＡを追加する。
 32: 		ｘにｘ＋１を入れる。
 33: 	｝を繰り返す。
 34: 
 35: 	ウィンドウを再描画する。
 36: 
 37: ｝と定義する。
 38: 
 39: カード移動するとは｛
 40: 
 41: 	無条件で…
 42: 
 43: 		ウィンドウが0.5秒待機する。
 44: 
 45: 		箱Ａに入っている物の個数を取得して、個数と名付ける。
 46: 		個数≠０ならば…
 47: 			箱Ａのカーソル位置の物を取得して、箱Ｂの最後にそれを追加する。
 48: 		…をして、個数＝０ならば…
 49: 			コンソールに「カード移動を終了します。」を出力する。
 50: 			繰り返しを脱出する。
 51: 		…をする。
 52: 
 53: 		ウィンドウを再描画する。
 54: 
 55: 	…を繰り返す。
 56: 
 57: ｝と定義する。
 58: 
 59: 初期化する。
 60: カード移動する。

14.2.1.1 break文

このプログラムでは、アニメーションループを抜け出すために繰り返し脱出文を使用しています。 繰り返し脱出文が繰り返し文（while文、for文、do/while文）の中で実行されると、 プログラムの処理の流れはただちに繰り返し構造から抜け出し、 制御が繰り返し構造の直後にある命令に移ります。

						
 41: 	無条件で…
 42: 
 43: 		ウィンドウが0.5秒待機する。
 44: 
 45: 		箱Ａに入っている物の個数を取得して、個数と名付ける。
 46: 		個数≠０ならば…
 47: 			箱Ａのカーソル位置の物を取得して、箱Ｂの最後にそれを追加する。
 48: 		…をして"TurtleCafe/chapter13/src/カード移動.dama"、個数＝０ならば…
 49: 			コンソールに「カード移動を終了します。」を出力する。
 50: 			繰り返しを脱出する。
 51: 		…をする。
 52: 
 53: 		ウィンドウを再描画する。
 54: 
 55: 	…を繰り返す。



					

このプログラムでは、箱Ａに入っている物の個数が0になると、 41行目から55行目までのアニメーションループを脱出して、制御がその次の行に移ります。

繰り返し脱出文は、構造化プログラミング（入り口ひとつ、出口ひとつの処理構造）を破壊するものとして、 プログラミングの作法としてはあまりよくないものだと言われています。 繰り返し脱出文を使わなくても、同じ処理の流れを定義することは可能なので、 プログラミングの作法を重んじるプログラマは、繰り返し脱出文の代わりに変数を用いて繰り返し構造を制御し、 繰り返し脱出文を使わないプログラムを記述します。

ここでは、「繰り返しを抜ける」ということを変数を使わず表現し、分かりやすくするため、繰り返し脱出文を使っています。

繰り返し脱出文は繰り返しを脱出する。と書きます。

14.2.2 入れ物に関する新しい命令

この章では、「入れ物」を使ったプログラミングを行います。 以下に、入れ物タートルに関する命令の一覧を示します。

14.2.2.1 入れ物を作る命令

入れ物を新規作成して、[変数名]と名付ける。

入れ物を作成します。

14.2.2.2 追加と削除

[入れ物]の最後に[カード]を追加する。

入れ物の最後にタートル型のものを追加します。

[入れ物]の先頭に[カード]を追加する。

入れ物の先頭にカードを追加します。

[入れ物]のカーソル位置に[カード]を追加する。

入れ物のカーソル位置にカードを追加します。

[入れ物]のカーソル位置の物を削除する。

カーソル位置にあるものを削除します

[入れ物]に入っている物を全て捨てる。

入れ物に入っているものを全て捨てます。

14.2.2.3 カーソルに関する命令

[入れ物]のカーソル位置を取得する。

現在のカーソル位置を取得します。

[入れ物]のカーソル位置を[整数型]に変える。

カーソル位置を、指定したカーソル番号に変えます

[入れ物]のカーソルを進める。

カーソルを１進めます

[入れ物]のカーソルを戻す。

カーソルを１戻します

[入れ物]のカーソル位置の物を取得する。

カーソル位置にあるものを取得します。

[入れ物]のカーソル位置の物の数値を取得する。

カーソル位置にあるカードの数値を取得します。カーソル位置にあるものが数字の書かれたカードでない場合は、-1を返します。

[入れ物]のカーソル位置にある物の内容を取得する。

カーソル位置にあるカードの内容を文字列型で取得します。内容が取得できない場合はNULLという文字列を返します。

14.2.2.4 その他の命令

[入れ物]をかきまぜる。

入れ物の中身をかきまぜます。

[入れ物]に入っている物の個数を取得する。

入っているものの個数を取得します

14.2.3 カードに関する新しい命令

以下に、カードに関する新しい命令の一覧を示します

14.2.3.1 カードを作る命令

カードを新規作成して、[変数名]と名付ける。

カードの変数を作成します。

14.2.3.2 その他の命令

[カード]の内容を取得する。

カードの内容を文字列型で取得します

[カード]に[番号]を設定する。

カードの内容を、指定した番号に変えます

[カード]のフォントサイズを取得する。

カードの内容のフォントサイズを取得します

[カード]のフォントサイズを[サイズ]に設定する。

カードの内容のフォントサイズを指定します

							
カードを新規作成して、カードＡと名付ける。
カードＡに１０を設定する。
箱Ａの最後にカードＡを追加する。

						

14.3 ソートアルゴリズム

14.3.1 ソートアルゴリズムとは

ソートアルゴリズムとは、ばらばらに並んでいるものを決まったならびに並び替える手順のことです。

本節では実際のカード並び替えで学んだ最小値選択法を、プログラムで作成します。

14.3.2 最小値選択法

それでは、１重ループのプログラムを見ていきましょう。

14.3.2.1 最小値選択法のフローチャート

このフローチャートでは、全体が１つのループの中に入っています。

14.3.2.2 最小値選択法を作る準備

このプログラムは、最小値選択法を行うために４種類の入れ物を用意したプログラムです。

ここをクリックすると、以下のプログラムをダウンロードできます。

  1: ※プログラム名：最小値選択法による並び替えをするプログラム１
  2: ※　　　　　　　（まずは入れ物を並べるだけ）
  3: ※作成者：
  4: ※作成日：
  5: 
  6: ※授業に必要なライブラリを取り込む。
  7: TurtleLibraryを参照する。
  8: 
  9: ※環境を初期化する。
 10: ウィンドウを初期化する。
 11: 
 12: ※入れ物を準備する
 13: 入れ物を新規作成して、未処理束と名付ける。
 14: 入れ物を新規作成して、最小値候補と名付ける。
 15: 入れ物を新規作成して、ソート済束と名付ける。
 16: 入れ物を新規作成して、検索済束と名付ける。
 17: ウィンドウに未処理束を追加する。
 18: ウィンドウに最小値候補を追加する。
 19: ウィンドウにソート済束を追加する。
 20: ウィンドウに検索済束を追加する。
 21: 
 22: 初期化するとは…
 23: 
 24: 	※ウィンドウの縦横幅を変える
 25: 	ウィンドウの横幅を550に設定する。
 26: 	ウィンドウの縦幅を400に設定する。
 27: 
 28: 	※未処理束の位置を設定する
 29: 	未処理束のｘ座標を５０に設定する。
 30: 	未処理束のｙ座標を１２０に設定する。
 31: 	テキストを新規作成して、未処理済束タイトルと名付ける。
 32: 	未処理済束タイトルの文字列を「未処理束」と設定する。
 33: 	未処理済束タイトルのフォントサイズを１２と設定する。
 34: 	未処理済束タイトルのｘ座標を５０に設定する。
 35: 	未処理済束タイトルのｙ座標を１００に設定する。
 36: 	ウィンドウに未処理済束タイトルを追加する。
 37: 
 38: 	※最小値候補の位置を設定する
 39: 	最小値候補のｘ座標を５０に設定する。
 40: 	最小値候補のｙ座標を５０に設定する。
 41: 	テキストを新規作成して、最小値候補タイトルと名付ける。
 42: 	最小値候補タイトルの文字列を「最小値候補」と設定する。
 43: 	最小値候補タイトルのフォントサイズを１２と設定する。
 44: 	最小値候補タイトルのｘ座標を５０に設定する。
 45: 	最小値候補タイトルのｙ座標を３０に設定する。
 46: 	ウィンドウに最小値候補タイトルを追加する。
 47: 
 48: 	※検索済束の位置を設定する
 49: 	検索済束のｘ座標を５０に設定する。
 50: 	検索済束のｙ座標を１９０に設定する。
 51: 	テキストを新規作成して、検索済束タイトルと名付ける。
 52: 	検索済束タイトルの文字列を「検索済束」と設定する。
 53: 	検索済束タイトルのフォントサイズを１２と設定する。
 54: 	検索済束タイトルのｘ座標を５０に設定する。
 55: 	検索済束タイトルのｙ座標を１７０に設定する。
 56: 	ウィンドウに検索済束タイトルを追加する。
 57: 
 58: 	※ソート済束の位置を設定する
 59: 	ソート済束のｘ座標を５０に設定する。
 60: 	ソート済束のｙ座標を２６０に設定する。
 61: 	テキストを新規作成して、ソート済束タイトルと名付ける。
 62: 	ソート済束タイトルの文字列を「ソート済束」と設定する。
 63: 	ソート済束タイトルのフォントサイズを１２と設定する。
 64: 	ソート済束タイトルのｘ座標を５０に設定する。
 65: 	ソート済束タイトルのｙ座標を２４０に設定する。
 66: 	ウィンドウにソート済束タイトルを追加する。
 67: 	
 68: 	※検索するカードを追加する
 69: 	
 70: 	※未処理束のカードを１枚、最小値候補にセットする
 71: 
 72: 	ウィンドウを再描画する。
 73: 
 74: …ことと定義する。
 75: 
 76: 並び替えするとは｛
 77: 
 78: 　無条件で…
 79: 
 80: 		ウィンドウを再描画する。
 81: 
 82: 	…を繰り返す。
 83: 
 84: ｝と定義する。
 85: 
 86: 
 87: 初期化する。
 88: 並び替えする。

14.3.2.3 問題1：カードの準備

最小値選択法.damaを改造して、カードを１０枚入れましょう。 カードはランダム数をセットするようにして下さい。

実行すると、以下のようになるように作りましょう（カード番号はランダムなので、以下の図と全く同じである必要はありません）。

14.3.2.4 問題２：カードの並び替え　その１

最小値選択法をいきなり全て作るのは大変ですから、まずはフローチャートの中で以下の部分だけを作成してみましょう。

作成すると、以下のような状態で止まるはずです。

14.3.2.5 問題３：カードの並び替え　その２

次に、フローチャートの中で以下を追加してみましょう。

作成すると、以下のように並び替え一歩手前の状態で止まるはずです。

14.3.2.6 問題４：カードの並び替え　その３

最後に、フローチャートの残りの箇所を追加しましょう。

作成すると、以下のように並び替えが完了するはずです。