水瓶問題 (Water Jug Problem)

ユークリッド法による解き方

(L, S) = (7, 5)

N = 4

water_2_jugs.pl

#!/usr/local/bin/perl -w

############################################################
# Program: water_2_jugs.pl
# Comment: Euclidean Algorithm for The Water 2-Jug Problem
# Perl Version: v5.10.0
# Run It 1: ./water_2_jugs.pl
# Run It 2: perl water_2_jugs.pl
# Runtime Environment: Snow Leopard 10.6.4
# Date: Oct 22nd, 2010
# Author: Fei Zhao
# Warnning: All Rights Reserved
############################################################

# About This Program:
# We are given two jugs named L and S, a 7-gallon (L jug) one and 5-gallon (S jug) one. Neither has any measuring marks on it. There is a pump that can be used to fill the jugs with  water. How can you get exactly 4 gallons of water into the 7-gallon jug?

use strict;
use warnings;

sub gcd{
    $_[0] == 0 ? $_[1] : &gcd($_[1] % $_[0], $_[0]);
}


my $l = 7; # 容量 L の容積
my $s = 5; # 容量 S の容積
my $n = 4; # 測りたい容積 N

my $x = 0; # 容器 L の初期状態
my $y = 0; # 容器 S の初期化状態


if( ($n > $l) && ($n > $s) || ($n % &gcd($l, $s) != 0) ){
    print "測れない\n";
    exit -1;
}

do{
    if($x == 0){
	print "L に水を満たす\n";
	$x = $l;
    }
    elsif($y == $s){
	print "S を空きにする\n";
	$y = 0;
    }
    elsif($x < $s - $y){
	print "L の水をすべて S に移す\n";
	$y += $x;
	$x = 0;
    }
    else{
	print "L の水を S がいっぱいになるまで, S に移す\n";
	$x -= $s - $y;
	$y = $s;
    }
}while( ($x != $n) && ($y != $n));

if($x == $n){
    print "L に測れた\n";
}

if($y == $n){
    print "S に測れた\n";
}

water_2_jugs.pl の実行結果は:

[cactus:~/code_perl/ai/water_2_jugs]% ./water_2_jugs.pl
L に水を満たす
L の水を S がいっぱいになるまで, S に移す
S を空きにする
L の水をすべて S に移す
L に水を満たす
L の水を S がいっぱいになるまで, S に移す
L に測れた

ユークリッド法による解き方 (計算時間を測る)

2_jugs_time.pl

#!/usr/local/bin/perl -w

############################################################
# Program: 2_jugs_time.pl
# Comment: Euclidean Algorithm for The Water 2-Jug Problem
# Perl Version: v5.10.0
# Run It 1: ./2_jugs_time.pl
# Run It 2: perl 2_jugs_time.pl
# Runtime Environment: Snow Leopard 10.6.4
# Date: Oct 22nd, 2010
# Author: Fei Zhao
# Warnning: All Rights Reserved
############################################################

# About This Program:
# We are given two jugs named L and S, a 7-gallon (L jug) one and 5-gallon (S jug) one. Neither has any measuring marks on it. There is a pump that can be used to fill the jugs with  water. How can you get exactly 4 gallons of water into the 7-gallon jug?

use strict;
use warnings;
use Time::HiRes qw/gettimeofday tv_interval/;

sub gcd{
    $_[0] == 0 ? $_[1] : &gcd($_[1] % $_[0], $_[0]);
}

print "容量 L の容積: ";
my $l = <STDIN>; # 容量 L の容積

print "容量 S の容積: ";
my $s = <STDIN>; # 容量 S の容積

print "測りたい容積 N: ";
my $n = <STDIN>; # 測りたい容積 N

my $x = 0; # 容器 L の初期状態
my $y = 0; # 容器 S の初期化状態

if( ($n > $l) && ($n > $s) || ($n % &gcd($l, $s) != 0) ){
    print "測れない\n";
    exit -1;
}

my $start = [gettimeofday]; # 計算時間を測るために, スタート時点を用意しておく
do{
    if($x == 0){
	print "L に水を満たす\n";
	$x = $l;
    }
    elsif($y == $s){
	print "S を空きにする\n";
	$y = 0;
    }
    elsif($x < $s - $y){
	print "L の水をすべて S に移す\n";
	$y += $x;
	$x = 0;
    }
    else{
	print "L の水を S がいっぱいになるまで, S に移す\n";
	$x -= $s - $y;
	$y = $s;
    }
}while( ($x != $n) && ($y != $n));

my $end = [gettimeofday]; # 終了時点

if($x == $n){
    print "L に測れた\n";
}

if($y == $n){
    print "S に測れた\n";
}

printf "使用した時間: %.6f 秒\n", tv_interval($start, $end);

2_jugs_time.pl の実行結果は:

[cactus:~/code_perl/ai/water_2_jugs]% ./2_jugs_time.pl
容量 L の容積: 9
容量 S の容積: 5
測りたい容積 N: 2
L に水を満たす
L の水を S がいっぱいになるまで, S に移す
S を空きにする
L の水をすべて S に移す
L に水を満たす
L の水を S がいっぱいになるまで, S に移す
S を空きにする
L の水を S がいっぱいになるまで, S に移す
S を空きにする
L の水をすべて S に移す
L に水を満たす
L の水を S がいっぱいになるまで, S に移す
S を空きにする
L の水を S がいっぱいになるまで, S に移す
L に測れた
使用した時間: 0.000307 秒