(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 秒