カードプログラムを記述するための，CardTurtleについて説明します．
このプログラムは、10枚のカードを入れ物１に入れ、１枚ずつ取り出して入れ物２に移すプログラムです。
1: /* 2: * プログラム名：カードをリスト１からリスト２に移動するプログラム 3: * Created on 2012/01/07 4: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 5: */ 6: public class MoveCards extends Turtle { 7: 8: // 起動処理 9: public static void main(String[] args) { 10: Turtle.startTurtle(new MoveCards(), args); 11: } 12: 13: // タートルを動かす処理 14: public void start() { 15: hide(); 16: Turtle.window.size(550,300); 17: ListTurtle<CardTurtle> list1 = new ListTurtle<CardTurtle>(true,"リスト1"); 18: ListTurtle<CardTurtle> list2 = new ListTurtle<CardTurtle>(true,"リスト2"); 19: { //位置を移動する 20: list1.warp(50,40); 21: list2.warp(50,110); 22: } 23: update(); 24: 25: { //カードを入れる 26: int i = 0; 27: while(i < 10){ 28: list1.addLast(new CardTurtle(i * 10)); 29: update(); 30: i++; 31: } 32: } 33: 34: while(true){ 35: sleep(0.025); 36: { //一コマの処理 37: if(list1.getSize() != 0){//移動する 38: list2.addLast(list1.getObjectAtCursor()); 39: } 40: } 41: update(); 42: } 43: } 44: 45: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、MoveCardsプログラムが実行できます。
while文とdo-while文は、両方とも繰り返しを表す文ですが、 条件判断の位置が違います。 while文は、最初に繰り返しを続けるかどうか調べて、続けるならば処理を行い、 続けないならば処理を抜ける、という構造をしています。 do-while文は、はじめに処理を行い、処理を行ったあとで、 繰り返しを続けるかどうか調べて、続けるならば２回目の処理を行い、続けないならば処理を抜ける、 という構造をしています。
このプログラムでは、アニメーションループを抜け出すためにbreak文を使用しています。 break文が繰り返し文（while文、for文、do/while文）の中で実行されると、 プログラムの処理の流れはただちに繰り返し構造から抜け出し、 制御が繰り返し構造の直後にある命令に移ります。
break文は、構造化プログラミング（入り口ひとつ、出口ひとつの処理構造）を破壊するものとして、 プログラミングの作法としてはあまりよくないものだと言われています。 break文を使わなくても、同じ処理の流れを定義することは可能なので、 プログラミングの作法を重んじるプログラマは、break文の代わりに変数を用いて繰り返し構造を制御し、 break文を使わないプログラムを記述します。
カードの内容には、文字列、小数、整数を入れることができます。
デバッガは，プログラムを一気に実行するのではなく，一行目から一行一行，手動で進めることの出来る機能を提供します．「DebugRun」で起動してみましょう．
アルゴリズムとは，何らかを実現する手順のことで，特に，小さい命令を組み合わせて，順序立てて実行することで，より大きな目的を達成する手順のことを指します．
アルゴリズムの初歩としてよく出てくる例として，並替えアルゴリズム（ソートアルゴリズム，ソーティングアルゴリズム）があります． 並び替えとは、ばらばらに並んでいるものを決まったならび（昇順や降順）に並び替えることを指します．このプログラムは，皆さんが習った技術を組み合わせて達成することが出来ます．
並替えアルゴリズムはこれまでにたくさんの種類が提案されていますが， ここでは手作業で考えやすい「最小値選択法」（データ構造とアルゴリズムではセレクションソートと呼ばれている技法です）について学んでみましょう．
以下に，手作業と，Squeakで実装されたプログラムのビデオがあります．
古典的ですが，基本的なアルゴリズムを設計するには有効な方法として，フローチャートを使った設計があります．ここでは，フローチャートで設計していきます．
まず，全体としては，最小値を探して，並替え済みの場所に置いていくという，次のようなフローチャートになります．
「最小値を探す」という命令はありませんので，これもアルゴリズムで記述する必要があります．すでに知っている命令を組み合わせると，次のようになります．
二つのフローチャートの関係は次のようになります．
これを一つに記述すると，全体としては次のようなアルゴリズムになります．
最小値検索を実装したプログラムです．
1: import java.awt.Color; 2: 3: /* 4: * プログラム名：最小値の検索 5: * Created on 2012/01/07 6: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 7: */ 8: public class LinearSearch extends Turtle { 9: 10: // 起動処理 11: public static void main(String[] args) { 12: Turtle.startTurtle(new LinearSearch(), args); 13: } 14: 15: // タートルを動かす処理 16: public void start() { 17: hide(); 18: Turtle.window.size(400,400); 19: ListTurtle<CardTurtle> 最小値候補 = new ListTurtle<CardTurtle>(true,"最小値候補"); 20: ListTurtle<CardTurtle> 未処理束 = new ListTurtle<CardTurtle>(true,"未処理束"); 21: ListTurtle<CardTurtle> 検索済束 = new ListTurtle<CardTurtle>(true,"検索済束"); 22: { //c//初期位置に移動する 23: 最小値候補.warpByTopLeft(50,20); 24: 最小値候補.setBgColor(new Color(255,153,204)); 25: 未処理束.warpByTopLeft(50,90); 26: 未処理束.setBgColor(new Color(51,102,255)); 27: 検索済束.warpByTopLeft(50,160); 28: 検索済束.setBgColor(new Color(0,204,153)); 29: update(); 30: } 31: { //カードを追加する 32: int i = 0; 33: while(i < 8){ 34: 未処理束.addLast(new CardTurtle(random(100))); 35: update(); 36: i++; 37: } 38: } 39: { //検索をする 40: 最小値候補.addLast(未処理束.getObjectAtCursor()); 41: while(未処理束.getSize() > 0){ 42: if(未処理束.getObjectAtCursor().getNumber() < 最小値候補.getObjectAtCursor().getNumber()){ 43: 検索済束.addLast(最小値候補.getObjectAtCursor()); 44: update(); 45: 最小値候補.addLast(未処理束.getObjectAtCursor()); 46: update(); 47: }else { 48: 検索済束.addLast(未処理束.getObjectAtCursor()); 49: update(); 50: } 51: 52: } 53: 検索済束.moveAllTo(未処理束); 54: update(); 55: } 56: } 57: 58: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、LinearSearchプログラムが実行できます。
設計に対して，それを実現するものを作ることを「実装」と呼び，ソフトウェア業界ではよく使われる言葉です．
Javaでは，変数名，メソッド名，クラス名に日本語が使えます．
（ただし，ファイル名の文字コードで問題が生じるため，クラス名に日本語をつけるのはお控えください）
最小値選択法を実装したプログラムです．
1: import java.awt.Color; 2: 3: /* 4: * プログラム名：最小値選択法による並び替え 5: * Created on 2012/01/07 6: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 7: */ 8: public class SelectionSort extends Turtle { 9: 10: // 起動処理 11: public static void main(String[] args) { 12: Turtle.startTurtle(new SelectionSort(), args); 13: } 14: 15: // タートルを動かす処理 16: public void start() { 17: hide(); 18: window.size(400,400); 19: ListTurtle<CardTurtle> 最小値候補 = new ListTurtle<CardTurtle>(true,"最小値候補"); 20: ListTurtle<CardTurtle> 未処理束 = new ListTurtle<CardTurtle>(true,"未処理束"); 21: ListTurtle<CardTurtle> 検索済束 = new ListTurtle<CardTurtle>(true,"検索済束"); 22: ListTurtle<CardTurtle> 並替済束 = new ListTurtle<CardTurtle>(true,"並替済束"); 23: { //c//初期位置に設定する 24: 最小値候補.warpByTopLeft(50,20); 25: 最小値候補.setBgColor(new Color(255,153,204)); 26: 未処理束.warpByTopLeft(50,90); 27: 未処理束.setBgColor(new Color(51,102,255)); 28: 検索済束.warpByTopLeft(50,160); 29: 検索済束.setBgColor(new Color(0,204,153)); 30: 並替済束.warpByTopLeft(50,230); 31: 並替済束.setBgColor(new Color(255,255,0)); 32: update(); 33: } 34: { //カードを追加する 35: int i = 0; 36: while(i < 8){ 37: 未処理束.addLast(new CardTurtle(random(100))); 38: update(); 39: i++; 40: } 41: } 42: { //並び替える 43: while(未処理束.getSize() > 0){ 44: { //最小値を検索する 45: { //未処理束の一番上を最小値候補に 46: 最小値候補.addLast(未処理束.getObjectAtCursor()); 47: update(); 48: } 49: while(未処理束.getSize() > 0){ 50: if(未処理束.getObjectAtCursor().getNumber() < 最小値候補.getObjectAtCursor().getNumber()){ 51: { //最小値候補を引いたカードと入れ替え，古い最小値候補は検索済み束へ 52: 検索済束.addLast(最小値候補.getObjectAtCursor()); 53: update(); 54: 最小値候補.addLast(未処理束.getObjectAtCursor()); 55: update(); 56: } 57: }else { 58: { //引いたカードを検索済み束へ 59: 検索済束.addLast(未処理束.getObjectAtCursor()); 60: update(); 61: } 62: } 63: 64: } 65: { //検索済み束を元に戻す 66: 検索済束.moveAllTo(未処理束); 67: update(); 68: } 69: } 70: { //見つけた最小値を並替済み束へ移動する 71: 並替済束.addLast(最小値候補.getObjectAtCursor()); 72: update(); 73: } 74: } 75: } 76: } 77: 78: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、SelectionSortプログラムが実行できます。
以下の問題はすべて同じファイル（ファイル名は「TenCards.java」）で作業すること．
1から10までの数が書かれたカードが10枚入った入れ物を作ろう。
(1)で作った入れ物に対して，アニメーションで1コマ毎に「カーソルを進める」ことをしてみよう． 1コマ毎に進められていることを，デバッガで確認しよう．
(2)で作った入れ物に対して，１秒に１回かきまぜて、 かきまぜるたびに「先頭にある数は○○です」と表示するプログラムを作ろう。
下の実行例を参考に，挿入法の並べ替えアルゴリズムのフローチャートを書き，プログラムを作りましょう．
ファイル名は「InsertionSort.java」とすること．
以下のテンプレートをダウンロードし，利用して良い．
検索済束を使わずに最小値選択法をプログラムしてみよう．
ファイル名は「ImprovedSort.java」とすること．