キーワード辞典
コップの果汁を入れ替える３つの方法
登録日 １３/０６/２３ 更新日 １３/０６/２３
教科「情報」の教科書で、よくアルゴリズムの一例として使われる、 ２つのコップの果汁の入れ替えを別のコップを介して行う表現、 あれって、イラストが、 何故同じ大きさのコップでは無いのだろうとか、 何故同じ果汁ではないのだろうとか、 以前からずぅっと漠然とした違和感を持っていたので、その話。
コップの果汁を入れ替える３つの方法
同じ大きさのコップ、Ａ、Ｂ、が有る。 コップＡには、500mlの、 コップＢには、350mlの、同じオレンジジュースが入っている。 この２つのコップのジュースの量を入れ替え、 コップＡには、350mlの、 コップＢには、500mlの、オレンジジュースが入っている状態にしたい。 どうしたら良いだろうか。 コップには目盛りが付いている。
その１
もう一つ、同じ大きさのコップＣを用意し、これを介して入れ替える。 すなわち、(1). コップＡのジュースをコップＣへ移す。
(2). コップＢのジュースをコップＡへ移す。
(3). コップＣのジュースをコップＢへ移す。
プログラムの例。 ｉｎｔサイズのコップＡ、Ｂ、Ｃを用意する。
シンプル、判り易い、確実、な方法。
プログラムの場合は、 移動では無くて、複写なんですけどね。
// Swap_1.java 2013.6.23 by Ryn
public class Swap_1 {
public static void main(String[] args) {
int a = 500, b = 350, c;
System.out.println("a = " + a + ", b = "+ b);
c = a; // ←(1)
a = b; // ←(2)
b = c; // ←(3)
System.out.println("a = " + a + ", b = "+ b);
}
}
その２
コップＡからコップＢへ150ml移す。 すなわち、(1). コップＡとコップＢの差を求める。
(2). コップＡから差の分のジュースを、
(3). コップＢへ移す。
プログラムの例。 ズルいけど発想は同じだと思う。
ｉｎｔサイズのコップＡ、Ｂを用意する。
プログラムの場合は、差が負であっても可能だが、果汁に拘りたい人は大小関係を比較して処理をすれば良い。
差分を使っているのでオーバーフロー（コップから溢れる）はしないが、 コップのサイズがfloatなどの場合に誤差が生じる可能性が有る。
// Swap_2.java 2013.6.23 by Ryn
public class Swap_2 {
public static void main(String[] args) {
int a = 500, b = 350;
System.out.println("a = " + a + ", b = "+ b);
b = a - b; // b = 500 - 350 = 150
a -= b; // a = 500 - 150 = 350
b += a; // b = 150 + 350 = 500
System.out.println("a = " + a + ", b = "+ b);
}
}
その３
加算、減算では無く、排他的論理和でも出来る。 これをＸＯＲ交換アルゴリズムと言う。 この方法はアセンブラで数の少ないレジスタを直接操作して行うには効果が有るが、 高級言語では「その１」の方法よりも処理速度が遅くなる傾向にある。
// Swap_3.java 2013.6.23 by Ryn
public class Swap_3 {
public static void main(String[] args) {
int a = 500, b = 350;
System.out.println("a = " + a + ", b = "+ b);
b ^= a;
a ^= b;
b ^= a;
System.out.println("a = " + a + ", b = "+ b);
}
}
確かに実務的には「その１」の方法が、 シンプル、判り易い、確実、なのは間違いがないのですが、 アルゴリズムとしては、違う形のコップ、違う種類のジュースの例にしてしまうと、 「その２」や「その３」への発想にはつながらないだろうなぁ、 と、思うのです。 こだわり過ぎでしょうか。
![[ 赤い玉の画像 ]](../Gif/RedBall.gif)
![[ 黒板消しとチョーク受けの画像 ]](../Gif/BlackBoardEnd.gif)