アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2005年7月8日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html
ハノイの塔
• 一回に一枚の円盤しか動かしてはいけない。
• 移動の途中で円盤の大小を逆に積んではいけない。
常に大きい方の円盤が下になるようにする。
• 棒以外のところに円盤を置いてはいけない。
円盤数5のとき、手数は31
nのときは手数2n－1
分割統治法
クイックソート
分割
統合
基準値を用いて、基準より
大きい値からなる部分問題
と基準より小さい値からな
る部分問題に分割し解く
部分問題がソート済みで
あれば、基準値とそれぞ
れの部分問題との大小
関係は分割のときに決定
していることから、結合す
るだけでよいことになる。
マージソート
問題を空間的に2分割し、
各々の部分問題を解く
部分問題の解どおしを比較し
ながら順に併合することで、部
分問題の解の大小関係は維
持したまま元の問題の解を得
ることができる
をRPNで書く
b neg b b * 4 a * c * － sqrt ＋ 2 a * ÷
b neg b b * 4 a * c * － sqrt － 2 a * ÷
あるいは
b neg b b * c 4 a * * － sqrt ＋ 2 a * ÷
b neg b b * c 4 a * * － sqrt － 2 a * ÷
他にあるかもしれないけど、意味があってればOK
二分探索木
二分木を次のルールで作成
•親よりも小さい値を持つ子は左
•親よりも大きい値を持つ子は右
29
20
14
7
24
19
21
32
30
48
31
プログラムの例では、数値のほかにObjectを置けるようにする
public class MyData implements Comparable
{
private MyData()
{
}
public MyData(int anId, Object aData)
{
this.id = anId;
this.data = aData;
}
interface Comparableには、
compareTo()というメソッドが存在する。
public int compareTo(Object o)；
thisオブジェクトを指定されたオブジェ
クトと比較し、
小さい場合は負の整数、
等しい場合はゼロ、
大きい場合は正の整数、
をそれぞれ返す。
}
二分探索木のノードに置くデータを表すクラス
public int compareTo(Object aTarget)
{
int targetId = ((MyData)aTarget).getId();
if(this.id == targetId){
return 0;
}
if(this.id > targetId){
return 1;
}
return -1;
}
public Object getData()
{
return this.data;
}
public int getId()
{
return (this.id);
}
public String toString()
{
return "(" + this.id + "'" + this.data + ")";
}
private Object data;
// 木に保持したいデータ
private int id;
// 順序付けのための数値
public class MyNode
{
private MyNode()
{
}
public MyNode(MyData aData)
{
this.data = aData;
}
public MyData getData()
{
return this.data;
}
public MyNode getLeft()
{
return this.left;
}
public MyNode getRight()
{
return this.right;
}
ノードに関する操作
二分探索木のノードを表すクラス
}
public void setLeft(MyNode aNode)
{
this.left = aNode;
}
public void setRight(MyNode aNode)
{
this.right = aNode;
}
public String toString()
{
MyData leftdata = null;
MyData rightdata = null;
if(null != this.left){
leftdata = this.left.getData();
}
if(null != this.right){
rightdata = this.right.getData();
}
return
("{"+leftdata+","+this.data+","+rightdata+"}");
}
private MyData data;
private MyNode left;
private MyNode right;
public class BinarySearchTree
{
public BinarySearchTree()
{
this.root = null;
}
private MyNode root;
}
二分探索木を表すクラス
二分探索木へ挿入するメソッド
public void insert(MyData aData)
{
MyNode newNode = new MyNode(aData);
if(null == this.root){
this.root = newNode;
return;
}
MyNode currentNode = this.root;
while(true){
if(0 < currentNode.getData().compareTo(aData)){
if(null == currentNode.getLeft()){
currentNode.setLeft(newNode);
return;
}
currentNode = currentNode.getLeft();
}else{
if(null == currentNode.getRight()){
currentNode.setRight(newNode);
return;
}
currentNode = currentNode.getRight();
}
}
}
public MyNode search(MyData aData)
{
if(null == this.root){
return null;
}
MyNode currentNode = this.root;
while(true){
if(0 == currentNode.getData().compareTo(aData)){ ループの終了条件
return currentNode;
•末端に達した
}
•一致するデータを発見
if(0 < currentNode.getData().compareTo(aData)){
if(null == currentNode.getLeft()){
return null;
}
currentNode = currentNode.getLeft();
}else{
if(null == currentNode.getRight()){
return null;
}
currentNode = currentNode.getRight();
}
}
}
ループによる二分探索
Tail Recursion
(末尾再帰)
public MyNode searchRecursive(MyData aData)
{
return searchR(aData, this.root);
}
private MyNode searchR(MyData aData, MyNode aRoot)
{
if(null == aRoot){ // 再帰を終了できるかどうか(末端に到達？)の判定
return null;
}
int result = aRoot.getData().compareTo(aData);
if(0 == result){
// 一致するデータを見つけたかどうかの判定
return aRoot;
}
return searchR(aData, (0 < result)? aRoot.getLeft(): aRoot.getRight());
}
このような再帰呼び出しはループと相互に変換可能
public boolean remove(MyData aData)
{
if(null == this.root){
return false;
}
MyNode parentNode = this.root;
MyNode currentNode = this.root;
boolean inLeftSubTree = false;
while(0 != currentNode.getData().compareTo(aData)){
parentNode = currentNode;
if(0 < currentNode.getData().compareTo(aData)){
currentNode = currentNode.getLeft();
inLeftSubTree = true;
}else{
currentNode = currentNode.getRight();
inLeftSubTree = false;
}
if(null == currentNode){
return false;
}
}
/* 削除処理本体は次以降のページで */
}
currentNode.setLeft(null);
currentNode.setRight(null);
return true;
削除対象を探す
if((null == currentNode.getLeft())
&& (null == currentNode.getRight())){
if(currentNode == this.root){
this.root = null;
}else if(inLeftSubTree){
parentNode.setLeft(null);
}else{
parentNode.setRight(null);
}
}else if(null == currentNode.getRight()){
if(currentNode == this.root){
this.root = currentNode.getLeft();
}else if(inLeftSubTree){
parentNode.setLeft(currentNode.getLeft());
}else{
parentNode.setRight(currentNode.getLeft());
}
}else if(null == currentNode.getLeft()){
if(currentNode == this.root){
this.root = currentNode.getRight();
}else if(inLeftSubTree){
parentNode.setLeft(currentNode.getRight());
}else{
parentNode.setRight(currentNode.getRight());
}
}
/* 続く… */
親
親
親
子
子
親
子
親
子
}
else{
MyNode minimumNode
= this.getMinimumNode(currentNode.getRight());
this.remove(minimumNode.getData());
minimumNode.setLeft(currentNode.getLeft());
minimumNode.setRight(currentNode.getRight());
if(currentNode == this.root){
this.root = minimumNode;
}else if(inLeftSubTree){
parentNode.setLeft(minimumNode);
1. 右部分木から最小の(最左)
}else{
のノードを取り出す
parentNode.setRight(minimumNode);
2. 削除対象と付け替え
}
親
子
子
孫
親
子
子
孫
private MyNode getMinimumNode(MyNode aLocalRootNode)
{
if(null == aLocalRootNode){
return null;
}
MyNode currentNode = aLocalRootNode;
while(true){
if(null == currentNode.getLeft()){
return currentNode;
}
currentNode = currentNode.getLeft();
}
}
public void printTreeInOrder()
{
System.out.println(this.traverseInOrder(this.root));
}
private String traverseInOrder(MyNode aLocalRootNode)
{
if(null == aLocalRootNode){
return "";
}
StringBuffer treeRepresentation = new StringBuffer();
treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(aLocalRootNode +System.getProperty("line.separator"));
treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getRight()));
return treeRepresentation.toString();
}
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分を訪ねる
3. 自分の右部分木をたどる
二分探索木を走査すると
整列済みデータが得られる
public void printTreePostOrder()
{
System.out.println(this.traversePostOrder(this.root));
}
private String traversePostOrder(MyNode aLocalRootNode)
{
if(null == aLocalRootNode){
return "";
}
StringBuffer treeRepresentation = new StringBuffer();
treeRepresentation.append(this.traversePostOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(this.traversePostOrder(aLocalRootNode.getRight()));
treeRepresentation.append(aLocalRootNode + System.getProperty("line.separator"));
}
return treeRepresentation.toString();
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分の右部分木をたどる
3. 自分を訪ねる
public void printTreePreOrder()
{
System.out.println(this.traversePreOrder(this.root));
}
private String traversePreOrder(MyNode aLocalRootNode)
{
if(null == aLocalRootNode){
return "";
}
StringBuffer treeRepresentation = new StringBuffer();
treeRepresentation.append(aLocalRootNode + System.getProperty("line.separator"));
treeRepresentation.append(this.traversePreOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(this.traversePreOrder(aLocalRootNode.getRight()));
}
return treeRepresentation.toString();
二分木を次のルールで走査
1. 自分を訪ねる
2. 自分の左部分木をたどる
3. 自分の右部分木をたどる
public class BinarySearchTreeTest
{
public static void main(String[] anyArguments)
{
BinarySearchTree tree = new BinarySearchTree();
System.out.println("果物の名前を追加");
tree.printTree();
tree.insert(data01);
MyData data01 = new MyData(29, "リンゴ");
tree.insert(data02);
MyData data02 = new MyData(20, "ミカン");
tree.insert(data03);
System.out.println("木を行きがけ順で表示");
MyData data03 = new
MyData(14, "サクランボ");
tree.insert(data04);
tree.printTreePreOrder();
MyData data04 = new
MyData(32, "バナナ");
tree.insert(data05);
System.out.println("木を通りがけ順で表示");
MyData data05 = new
MyData(30, "イチゴ");
tree.insert(data06);
MyData data06 = new
MyData(24, "ブルーベリー");
tree.printTreeInOrder();
tree.insert(data07);
MyData data07 = new
MyData( 7, "グレープフルーツ");
System.out.println("木を帰りがけ順で表示");
tree.insert(data08);
MyData data08 = new
MyData(21, "レモン");
tree.printTreePostOrder();
tree.insert(data09);
MyData data09 = new MyData(48, "メロン");
tree.insert(data10);
MyData data10 = new MyData(31, "スイカ");
tree.insert(data11);
tree.remove(data10);
MyData data11 = new
MyData(19, "ナシ");
tree.insert(data12);
tree.remove(data11);
MyData data12 = new
MyData(17, "モモ");
tree.insert(data13);
tree.remove(data02);
MyData data13 = new
MyData(23, "マンゴー");
tree.insert(data14);
MyData data14 = new MyData(28, "ブドウ");
tree.printTree();
System.out.println("木を通りがけ順で表示");
tree.printTreeInOrder();
}
}
System.out.println("30, イチゴを探す");
System.out.println(tree.search(data05).toString());
System.out.println(tree.searchRecursive(data05).toString());
果物の名前を追加
(7'グレープフルーツ)
(14'サクランボ)
(17'モモ)
(19'ナシ)
木を行きがけ順で表示
(7'グレープフルーツ)
(20'ミカン)
{(20'ミカン),(29'リンゴ),(32'バナナ)}
(14'サクランボ)
(21'レモン)
{(14'サクランボ),(20'ミカン),(24'ブルーベリー)}
(17'モモ)
(23'マンゴー)
ミカン・スイカ・ナシを削除
{(7'グレープフルーツ),(14'サクランボ),(19'ナシ)}
(21'レモン)
(24'ブルーベリー)
{null,(7'グレープフルーツ),null}
(23'マンゴー)
(28'ブドウ)
木を通りがけ順で表示
{(17'モモ),(19'ナシ),null}
(24'ブルーベリー)
(29'リンゴ)
{null,(7'グレープフルーツ),null}
{null,(17'モモ),null}
(28'ブドウ)
(30'イチゴ)
{(7'グレープフルーツ),(14'サクランボ),(19'ナシ)}
{(21'レモン),(24'ブルーベリー),(28'ブドウ)}
(29'リンゴ)
(31'スイカ)
{null,(17'モモ),null}
{null,(21'レモン),(23'マンゴー)}
(30'イチゴ)
(32'バナナ)
{(17'モモ),(19'ナシ),null}
{null,(23'マンゴー),null}
(32'バナナ)
(48'メロン)
{(14'サクランボ),(20'ミカン),(24'ブルーベリー)}
{null,(28'ブドウ),null}
(48'メロン)
{null,(21'レモン),(23'マンゴー)}
{(30'イチゴ),(32'バナナ),(48'メロン)}
木を通りがけ順で表示
木を通りがけ順で表示
{null,(23'マンゴー),null}
{null,(30'イチゴ),(31'スイカ)}
木を帰りがけ順で表示
{null,(7'グレープフルーツ),null}
{null,(7'グレープフルーツ),null}
{(21'レモン),(24'ブルーベリー),(28'ブドウ)}
{null,(31'スイカ),null}
{null,(7'グレープフルーツ),null}
{(7'グレープフルーツ),(14'サクランボ),(19'ナシ)}
{(7'グレープフルーツ),(14'サクランボ),(17'モモ)}
{null,(28'ブドウ),null}
{null,(48'メロン),null}
{null,(17'モモ),null}
{null,(17'モモ),null}
{(20'ミカン),(29'リンゴ),(32'バナナ)}
{(17'モモ),(19'ナシ),null}
{(17'モモ),(19'ナシ),null}
{(14'サクランボ),(21'レモン),(24'ブルーベリー)}
{null,(30'イチゴ),(31'スイカ)}
{(7'グレープフルーツ),(14'サクランボ),(19'ナシ)}
{(14'サクランボ),(20'ミカン),(24'ブルーベリー)}
{null,(23'マンゴー),null}
{null,(31'スイカ),null}
{null,(23'マンゴー),null}
{null,(21'レモン),(23'マンゴー)}
{(23'マンゴー),(24'ブルーベリー),(28'ブドウ)}
{(30'イチゴ),(32'バナナ),(48'メロン)}
{null,(21'レモン),(23'マンゴー)}
{null,(23'マンゴー),null}
{null,(28'ブドウ),null}
{null,(48'メロン),null}
{null,(28'ブドウ),null}
{(21'レモン),(24'ブルーベリー),(28'ブドウ)}
{(21'レモン),(29'リンゴ),(32'バナナ)}
{(21'レモン),(24'ブルーベリー),(28'ブドウ)}
{null,(28'ブドウ),null}
{null,(30'イチゴ),null}
{(14'サクランボ),(20'ミカン),(24'ブルーベリー)}
{(20'ミカン),(29'リンゴ),(32'バナナ)}
{(30'イチゴ),(32'バナナ),(48'メロン)}
{null,(31'スイカ),null}
{null,(30'イチゴ),(31'スイカ)}
{null,(48'メロン),null}
{null,(30'イチゴ),(31'スイカ)}
{null,(31'スイカ),null}
{null,(48'メロン),null}
{(30'イチゴ),(32'バナナ),(48'メロン)}
30, イチゴを探す
{(30'イチゴ),(32'バナナ),(48'メロン)}
{null,(48'メロン),null}
{null,(30'イチゴ),null}
{(20'ミカン),(29'リンゴ),(32'バナナ)}
{null,(30'イチゴ),null}

Download Report