Created
March 2, 2012 14:34
-
-
Save sash-kan/1958739 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/bash | |
instr() { | |
echo "применение: $0 <требуемый объём> <объём сосуда> <объём сосуда>" | |
exit | |
} | |
ravno0() { | |
echo "один из переданных параметров равен нулю" | |
echo "дайте задачу посложнее" | |
exit | |
} | |
ravny() { | |
echo "сосуды одного объёма" | |
echo "дайте задачу посложнее" | |
exit | |
} | |
nevozmozhno() { | |
echo "решения нет, ибо $1" | |
exit | |
} | |
state() { | |
echo "сейчас в первом сосуде: $n1, во втором сосуде: $n2" | |
} | |
itog() { | |
echo -n "шагов: $step " | |
state | |
} | |
n() { # наливаем в $1 | |
local a1=$1 | |
state | |
echo "наливаем в сосуд $a1" | |
eval n$a1=\$v$a1 | |
set $((step++)) | |
} | |
p() { # переливаем из $1 в $2 | |
local vv a1=$1 a2=$2 | |
state | |
echo "переливаем из сосуда $a1 в сосуд $a2" | |
eval vv=$((v$a2-n$a2>n$a1?n$a1:v$a2-n$a2)) | |
eval n$a1=$((n$a1-vv)) | |
eval n$a2=$((n$a2+vv)) | |
set $((step++)) | |
} | |
c() { # проверка, что объём чего-либо соответстует содержимому $v0 | |
[ $n1 -eq $v0 -o $n2 -eq $v0 -o $((n2+n1)) -eq $v0 ] | |
} | |
v() { # выливаем содержимое $1 | |
state | |
echo "выливаем содержимое сосуда $1" | |
eval n$1=0 | |
set $((step++)) | |
} | |
v1() { # выливаем содержимое $1 | |
local a1=$1 | |
eval v=$((v$a1-n$a1)) | |
if [ $v -eq 0 ]; then | |
state | |
echo "выливаем содержимое сосуда $a1" | |
eval n$a1=0 | |
set $((step++)) | |
fi | |
} | |
pk() { # наливаем $1 раз в $2, переливаем $3 раз в $4, проверяем объём $5 | |
local a1=$1 a2=$2 a3=$3 a4=$4 | |
local k=$(($a1<$a3?$a3:$a1)) | |
local vv | |
while [ $k -gt 0 ]; do | |
n $a2 | |
c && return | |
p $a2 $a4 | |
c && return | |
eval vv=$((v$a4-n$a4)) | |
while [ $vv -eq 0 ]; do | |
v $a4 | |
c && return | |
p $a2 $a4 | |
c && return | |
eval vv=$((v$a4-n$a4)) | |
done | |
set $((k--)) | |
done | |
return | |
} | |
[ $# == 3 ] || instr | |
[ $1 != 0 -a $2 != 0 -a $3 != 0 ] || ravno0 | |
[ $2 != $3 ] || ravny | |
v0=$1 | |
if [ $2 -gt $3 ]; then | |
v1=$2 | |
v2=$3 | |
else | |
v1=$3 | |
v2=$2 | |
fi | |
echo "требуемый объём = $v0" | |
echo "объём первого сосуда = $v1" | |
echo "объём второго сосуда = $v2" | |
# v0 <= v1+v2 | |
[ $((v1+v2)) -ge $v0 ] || nevozmozhno "требуемый объём превышает суммарный объём обоих сосудов" | |
# v0 == a*v1-b*v2 a<v1 b<v2 | |
a=0 | |
b=0 | |
for ((i=1;i<v1;i++)); do | |
for ((j=0;j<v2;j++)); do | |
if [ $((i*v1-j*v2)) -eq $v0 ]; then | |
a=$i | |
b=$j | |
break 2 | |
fi | |
done | |
done | |
# v0 == c*v2-d*v1 c<v2 d<v1 | |
c=0 | |
d=0 | |
for ((i=1;i<v2;i++)); do | |
for ((j=0;j<v1;j++)); do | |
if [ $((i*v2-j*v1)) -eq $v0 ]; then | |
c=$i | |
d=$j | |
break 2 | |
fi | |
done | |
done | |
n1=0 | |
n2=0 | |
step=0 | |
if [ $a -gt 0 -o $b -gt 0 ]; then | |
echo a=$a b=$b | |
pk $a 1 $b 2 $v0 | |
itog | |
else | |
if [ $c -gt 0 -o $d -gt 0 ]; then | |
echo c=$c d=$d | |
pk $c 2 $d 1 $v0 | |
itog | |
else | |
if [ $((v1+v2)) -eq $v0 ]; then | |
n 1 | |
n 2 | |
itog | |
else | |
echo "к сожалению, решений не найдено" | |
fi | |
fi | |
fi |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment