关于倒水的智力题
feifei
AsahiC
三个水桶，10升，7升，3升,初始10升的那个桶满的，想办法倒腾成两个5升，不能浪费水。
--
*************************************************
* 天无私意 伐无私刑 罪剑问生 天谴判死
* Q Q: 370581772
* MSN: px...@hotmail.com
*************************************************
孙涛
三个水桶，10升，7升，3升,初始10升的那个桶满的，想办法倒腾成两个5升，不能浪费水。
--
Regards！
孙涛
手机：13482892784
email：suntao1...@gmail.com
email2：ts...@abeam.com
msn：suntao1...@hotmail.com
龙宇军
3*4+7*(-1)=5
其实只要是能3*x+7*y= 5的方案都是可行的
比方说少复杂一点的：3*(-3)+7*2=5
On 11月28日, 上午11时35分, "孙涛" <suntao19830...@gmail.com> wrote:
> （1）：10往3里倒
> （2）：3往7里倒
> （3）：重复（1）（2）
> （4）：重复（1）
> （5）：3往7里倒，直至7满。此时3剩2L
> （6）：7全部倒入10
> （7）：3倒入7，此时7里是2L
> （8）：10倒入3
> （9）：3再倒入7，此时7里是5L。10里也是5L
>
> 2008/11/28 feifei <dongfei...@gmail.com>
>
> > 三个水桶，10升，7升，3升,初始10升的那个桶满的，想办法倒腾成两个5升，不能浪费水。
>
> --
> Regards！
>
> 孙涛
> 手机：13482892784
> email：suntao19830...@gmail.com
> email2：t...@abeam.com
> msn：suntao19830...@hotmail.com
夜弓
分支太少，根本不能算智力题
基本上每一步都只有一种行为可选，其他的行为直接导致形成3/7的原始布局
大致上就是10 -> 7, 7 -> 3, 3 -> 10
太易
Changsheng Jiang
Changsheng Jiang
2008/11/28 夜弓 <a...@yegong.net>:
AsahiC
龙宇军
（1）：10往7里倒
（2）：7往3里倒
（3）：重复（2）
（4）：重复（2）
（5）：10往7里倒
（6）：重复（2）
（7）：7中剩余为5
On 11月28日, 下午1时00分, AsahiC <asah...@gmail.com> wrote:
> 其实只要是能3*x+7*y= 5的方案都是可行的
> 比方说少复杂一点的：3*(-3)+7*2=5 这个没明白啊
>
> 2008/11/28 龙宇军 <yujunlong2...@yahoo.com.cn>
> * MSN: p...@hotmail.com
> *************************************************- 隐藏被引用文字 -
>
> - 显示引用的文字 -
龙宇军
On 11月28日, 下午1时00分, AsahiC <asah...@gmail.com> wrote:
> 其实只要是能3*x+7*y= 5的方案都是可行的
> 比方说少复杂一点的：3*(-3)+7*2=5 这个没明白啊
>
> 2008/11/28 龙宇军 <yujunlong2...@yahoo.com.cn>
taodm
DaiZW
就本题来说, 共有39个满足"三个桶中水的总体积为10"这个条件的状态.
本题就是求(10, 0 , 0)和(5, 5, 0)两个状态间的路径
不知道最短路径的长度是多少?
realfun
如果定义每一次倒水为一步的话，
那么对于(10, 0, 0)这样的开局，最终的结果是9步
代码如下：
# -*- coding: utf-8 -*-
#水桶问题求解
#三个水桶，10升，7升，3升,初始10升的那个桶满的，想办法倒腾成两个5升，不能浪费水
#宽度优先遍历一遍就行了，比求解华容道的问题要简单一些
#定义每一次倒水为一步的话
LIMITS = (10, 7, 3)
INIT = (10, 0, 0)
WIN = (5, 5, 0)
from copy import copy
class State:
def __init__(self, init_value):
self.parent = -1
self.value = init_value
self.move = (0, 0, 0) #(from, to, amount)
#spawn by put water around
def spawn(self):
for i in range(len(LIMITS)): #for each cup
if not self.value[i]: continue #if empty cup then next
for k in range(len(LIMITS)): #otherwise try put water to other cups
if i == k: continue
val_i = self.value[i]
val_k = self.value[k]
#1. move all in i to k
#2. move i to make k full
#so the minimum of the 2 actions is the target
min_ik = min(val_i, LIMITS[k] - val_k)
new_value = list(copy(self.value))
new_value[i] -= min_ik
new_value[k] += min_ik
new_value = tuple(new_value)
if new_value in g_state_map: #already exists?
continue
new_state = State(new_value)
new_state.parent = g_index
new_state.move = (i, k, min_ik)
g_states.append(new_state)
g_state_map[new_value] = True
if new_value == WIN:
return True
return False
def print_solution(state):
states = []
while state.parent != -1:
states.append(state)
state = g_states[state.parent]
states.reverse()
print "At least:", len(states), "steps:"
print "(Cup0, Cup1, Cup2) (from, to, amount)"
print INIT
for state in states:
print state.value, state.move
#solve the problem here!
g_states = [State(INIT)] #initially we have (10, 0, 0)
g_state_map = {} #sate:true/false, avoid duplicate states
g_index = 0
while g_index < len(g_states):
state = g_states[g_index]
if state.spawn():
print_solution(g_states[-1])
break
g_index += 1
result = """
At least: 9 steps:
(Cup0, Cup1, Cup2) (from, to, amount)
(10, 0, 0)
(3, 7, 0) (0, 1, 7)
(3, 4, 3) (1, 2, 3)
(6, 4, 0) (2, 0, 3)
(6, 1, 3) (1, 2, 3)
(9, 1, 0) (2, 0, 3)
(9, 0, 1) (1, 2, 1)
(2, 7, 1) (0, 1, 7)
(2, 5, 3) (1, 2, 2)
(5, 5, 0) (2, 0, 3)
"""
写段代码自动算哈。100行足够搞定的问题。
On 11月28日, 上午11时21分, feifei <dongfei...@gmail.com> wrote:
> 三个水桶，10升，7升，3升,初始10升的那个桶满的，想办法倒腾成两个5升，不能浪费水。
--
代码发芽网： http://www.fayaa.com/code/ （无需插件支持blog代码高亮，100+种语言，30+种高亮主题）
游戏发芽网： http://www.fayaa.com/youxi/ （华容道等在线小游戏）
我的Blog: 半瓶墨水(http://www.2maomao.com/blog)
feifei
还有一道题跟水桶相关的，有两组桶，一组红桶和一组黑桶，大小不一，各n个，但是能一一对应（同一个集合），不能同种颜色的桶的比，但是可以黑桶和红桶
的比较大小，但只能知道大于，等于，小于这3种关系，如何找出所以的一一对应。 求最少的比较次数（算法复杂度）。
On Nov 28, 3:41 pm, realfun <real...@gmail.com> wrote:
> 宽度优先遍历一遍就行了，比求解华容道的问题要简单一些
> 如果定义每一次倒水为一步的话，
> 那么对于(10, 0, 0)这样的开局，最终的结果是9步
> 代码如下：
>
> *Python语言*: 水桶倒水问题求解 <http://www.fayaa.com/code/view/508/>
> 2008/11/28 taodm <tao.dongm...@zte.com.cn>
feifei
有两个set , s1 = {r1,r2...rn}, s2={b1,b2...bn}, s1== s2, r1!=r2!=...rn ,
b1!=b2!=..bn
找出
r1==bj1,
r2==bj2
...
rn==bjn
。
DaiZW
DaiZW
取一个红桶(R1), 和所有黑桶(B)比较, 一轮下来, 能够找到一个对应, 并且可以把所有其余黑桶分为两个部分--大的(S1)和小的(S2).
然后取R2, 先和R1比较, 然后根据比较结果来决定和S1比较还是S2比较.
这样直到找到所有的对应.
最坏情况下应该是n+n+(n-1)+(n-2)+...+3=O(n^2)
最佳情况下是n+2+2+...+2=O(n)
平均是O(n^2)
抛砖引玉, 期待更好的算法.
star23
如果有O(1)的hash算法的话 就可以在O(n)的时间内搞定了
On 11月28日, 下午6时49分, DaiZW <shinysky1...@gmail.com> wrote:
> 只想到一个最笨的方法:
> 取一个红桶(R1), 和所有黑桶(B)比较, 一轮下来, 能够找到一个对应, 并且可以把所有其余黑桶分为两个部分--大的(S1)和小的(S2).
> 然后取R2, 先和R1比较, 然后根据比较结果来决定和S1比较还是S2比较.
> 这样直到找到所有的对应.
>
> 最坏情况下应该是n+n+(n-1)+(n-2)+...+3=O(n^2)
> 最佳情况下是n+2+2+...+2=O(n)
> 平均是O(n^2)
>
> 抛砖引玉, 期待更好的算法.
>
> 2008/11/28 feifei <dongfei...@gmail.com>
DaiZW
张沈鹏
问题描述：有A，B，C三个桶，容量分别为3L，7L，10L。现C桶有10L水。要求在水只能在桶间转移的前提下，使得C桶与B桶平分10L水。求最简洁操作。
program BFS;
const
v:array[1..3] of integer= (3,7,10); //三种桶的容量。
type
node=record
l:array[1..3] of longint;//三个水桶。
p:longint;//每个结点的父结点。
end;
var
i,j,head,tail:longint;
t:boolean; //找到目标的标志。
a:array[0..100] of node;
procedure init;
var
i,j:longint;
begin
fillchar(a,sizeof(a),0);
t:=false;
a[0].l[3]:=10;
head:=-1;
tail:=0;
end;
procedure pour(x,y:longint);
var
i,j:longint;
begin
if (a[head].l[x]=0) or t then exit;
inc(tail);
a[tail]:=a[head];
a[tail].p:=head;
if a[tail].l[x]>v[y]-a[tail].l[y] then
begin
dec(a[tail].l[x],v[y]-a[tail].l[y]);
a[tail].l[y]:=v[y];
end else
begin
inc(a[tail].l[y],a[tail].l[x]);
a[tail].l[x]:=0;
end;
for i:=0 to tail-1 do //检查该状态是否出现过，是的话删除。
begin
if a[i]=a[tail] then
begin
dec(tail);
exit;
end;
end;
if a[tail].l[3]=5 then t:=true;
end;
procedure main;
var
i,j:longint;
begin
repeat
inc(head);
pour(1,2); //pour函数的作用是尝试把x桶里的水倒入y桶，看能不能产生新的状态。
pour(2,1);
pour(1,3);
pour(3,1);
pour(2,3);
pour(3,2);
until (a[tail].l[3]=5) or (tail=100); //当找到目标或者已经超出预定的搜索范围的时候退出。
end;
procedure print;
var
c:array[1..100] of longint;
i,j:longint;
begin
i:=0;
while a[tail].p<>0 do
begin
inc(i);
c[i]:=tail;
tail:=a[tail].p;
end;
for j:=i downto 1 do writeln(a[c[j]].l[1],' ',a[c[j]].l[2],' ',a[c[j]].l[3]);
end;
begin
init;
main;
print;
end.
张沈鹏
整理人: jeter(2000-07-27 00:20:45), 站内信件
倒水问题
——经典智力题推而广之一
倒水问题的经典形式是这样的：
"假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为
5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。"
当然题外是有一些合理的限制的，比如从池塘里灌水的时候，不管壶
里是不是已经有水了，壶一定要灌满，不能和另一个壶里的水位比照
一下"毛估估"（我们可以假设壶是不透明的，而且形状也不同）；
同样的，如果要把水从壶里倒进池塘里，一定要都倒光；如果要把水
从一个壶里倒进另一个壶里，也要都倒光，除非在倒的过程中另一个
壶已经满了；倒水的时候水没有损失（蒸发溢出什么的）等等等等。
事实上，要解决上面这题，你只要用两个壶中的其中一个从池塘里灌
水，不断地倒到另一个壶里，当第二个壶满了的时候，把其中的水倒
回池塘里，反复几次，就得到答案了。以5升壶(A)灌6升壶(B)为例：
A B
0 0
5 0 A->B
0 5
5 5 A->B
4 6
4 0 A->B
0 4
5 4 A->B
3 6
现在我们问，如果是多于2只壶的情况怎么办（这样一来就不能用上面
的循环倒水法了）？如何在倒水之前就知道靠这些壶是一定能（或一
定不能）倒出若干升水来的？试举数例：
1)两个壶：65升和78升，倒38升和39升。
2)三个壶：6升，10升和45升，倒31升。
我们可以看到，在1)中，65=5*13，78=6*13，而39=3*13。所以如果把
13升水看作一个单位的话（原题中的"升"是没有什么重要意义的，
你可以把它换成任何容积单位，毫升，加仑——或者"13升"），这
题和最初的题目是一样的。而38升呢？显然是不可能的，它不是13的
倍数，而65升和78升的壶怎么也只能倒出13升的倍数来。也可以这样
理解：这相当于在原题中要求用5升和6升的壶倒出38/39升来。
那么2)呢？你会发现，只用任何其中两个壶是倒不出31升水的，理由
就是上面所说的，(6,10)=2，(6,45)=3，(10,45)=5，（这里(a,b)是
a和b的最大公约数），而2，3，5均不整除31。可是用三个壶就可以倒
出31升：用10升壶四次，6升壶一次灌45升壶，得到1升水，然后灌满
10升壶三次得30升水，加起来为31升。
一般地我们有"灌水定理"：
"如果有n个壶容积分别为A1，A2，……，An（Ai均为大于0的整数）
设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为：
1)w小于等于A1+A2+……+An；
2)w可被(A1,A2,……,An)（这n个数的最大公约数）整除。"
这两个条件都显然是必要条件，如果1)不被满足的话，你连放这么多
水的地方都没有。2)的道理和上面两个壶的情况完全一样，因为在任
何步骤中，任何壶中永远只有(A1,A2,……,An)的倍数的水。
现在我们来看一下充分性。在中学里我们学过，如果两个整数a和b互
素的话，那么存在两个整数u和v，使得ua+vb=1。证明的方法很简单：
在对a和b做欧几里德辗转相除时，所有中间的结果，包括最后得到的
结果显然都有ua+vb的形式（比如第一步，假设a小于b，记a除b的结果
为s，余数为t，即b=sa+t，则t=(-s)a+b，即u=-s，v=1）。而两个数
互素意味着欧几里德辗转相除法的最后一步的结果是1，所以1也可以
记作ua+vb的形式。稍微推广一点，如果(a,b)=c，那么存在u和v使得
ua+vb=c（两边都除以c就回到原来的命题）。
再推广一点，如果A1，A2，……，An是n个整数，(A1,A2,……,An)=s，
那么存在整数U1，U2，……，Un，使得
U1A1 + U2A2 + …… + UnAn = s. (*)
在代数学上称此结果为"整数环是主理想环"。这也不难证，只要看
到
(A1,A2,A3,A4,……,An)=((((A1,A2),A3),A4),……,An).
也就是说，可以反复应用上一段中的公式：比如三个数a，b，c，它
们的最大公约数是d。假设(a,b)=e，那么(e,c)=((a,b),c)=d。现在
有u1，u2使得u1a+u2b=e，又有v1，v2使得v1e+v2c=d，那么
(v1u1)a+(v1u2)b+(v2)c=d.
好，让我们回头看"灌水定理"。w是(A1,A2,……,An)的倍数，根据
上节的公式(*)，两边乘以这个倍数，我们就有整数V1，V2，……，Vn
使得
V1A1 + V2A2 + …… + VnAn = w.
注意到Vi是有正有负的。
这就说明，只要分别把A1，A2，……，An壶，灌上V1，V2，……，Vn
次（如果Vi是负的话，"灌上Vi次"要理解成"倒空-Vi次"），就可
以得到w升水了。具体操作上，先求出各Vi，然后先往Vi是正数的壶里
灌水，灌1次就把Vi减1。再把这些水到进Vi是负数的壶里，等某个壶
灌满了，就把它倒空，然后给这个负的Vi加1，壶之间倒来倒去不变更
各Vi的值。要注意的是要从池塘里灌水，一定要用空壶灌，要倒进池
塘里的水，一定要是整壶的。这样一直到所有Vi都是0为止。
会不会发生卡住了，既不能灌水又不能倒掉的情况？不会的。如果有
Vi仍旧是负数，而Ai壶却没满：那么如果有其它Vi是正的壶里有水的
话，就都倒给它；如果有其它Vi是正的壶里没水，那么就拿那个壶打
水来灌（别忘了给打水的壶的Vi减1）；如果根本没有任何Vi是正的壶
了——这是不可能的，这意味着w是负的。有Vi仍旧是正数，而Ai壶却
没满的情况和这类似，你会发现你要用到定理中的条件1)。
这样"灌水定理"彻底得证。当然，实际解题当中如果壶的数目和容
积都比较大的话，手工来找(*)中的各Ui比较困难，不过可以写个程序，
连倒水的步骤都算出来。最后要指出的一点是，(*)中的Ui不是唯一的，
所以倒水的方式也不是唯一的。
张沈鹏
?
你的这个问题叫做量水问题，虽然宽度优先搜索可以做，但是那样做太蠢了：）复杂度太高。这个问题以前有人问过我，我把答案贴出来：）
[量水问题]：
有三个分别装有a升水，b升水，c升水的量筒，其中a,b互质，c>b>a>0，现在c筒装满水，问能否在c筒中量出d升水(c>d>0)。若可以，给出方案。
解答：
所谓模数方程，就是模线性方程，即形如 ax ≡ b (mod c) 形式的方程，其中a,b,c是常数，x是自变量，这个方程表示ax mod
c = b mod c，即ax和b模c同余。
这个量水问题，用模数方程解比较方便，具体算法分析如下。
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个特点：
1。总有一个筒中的水没有变动；
2。不是一个筒被倒满酒是另一个筒被倒光；
3。c筒仅起到中转作用，而本身的容积除了必须足够装下a筒和b筒全部的水以外，别无其他的限制；
这样，假设整个倒水过程中对a筒倒满了x次，对b筒倒满了y次，则：
ax + by = d， （1）
上式的x,y为整数，而且既可以是正整数（表示该筒（a或b）被c筒的水倒满的次数），也可以是负整数（表示该筒（a或b）被倒满后又倒回到c筒的次数）。
一般可以用穷举法来解方程（1），但是这种方法局限性很大。我们可以将方程转化为：
ax = -by + d，
进一步变为
ax ≡ d (mod b)， （20
这样问题就变成了求解模数方程（2）的解的问题。解x的个数就是可行方案的总数。其中xi表示第i种方案中a筒倒满的次数，xi代入方程（1）后求出来的yi表示b筒倒满的次数。
例如：有三个量筒，a=3,b=7,c=10,求c筒中量出5升水的所有方案。
解方程 ： 3x ≡ 5 (mod 7) 得到 x1 = 4, y1=-1 和x2=-3, y2=2，
这两个解对应的倒水方案如下：
方案一： x1=4, y1=-1
次数 a b c 说明
1 0 0 10 初始状态
2 3 0 7 从c倒水到a中，把a倒满
3 0 3 7 从a倒水到b中，把a倒空
4 3 3 4 从c倒水到a中，把a倒满
5 0 6 4 从a倒水到b中，把a倒空
6 3 6 1 从c倒水到a中，把a倒满
7 2 7 1 从a倒水到b中，把b倒满
8 2 0 8 从b倒水到c中，把b倒空
9 0 2 8 从a倒水到b中，把a倒空
10 3 2 5 从c倒水到a中，把a倒满
11 0 5 5 从a倒水到b中，把a倒空
整个过程中，一共有4次"从c倒水到a中，把a倒满"，有1次"从b倒水到c中，把b倒空"；
方案二： x2=-3, y2=2
次数 a b c 说明
1 0 0 10 初始状态
2 0 7 3 从c倒水到b中，把b倒满
3 3 4 3 从b倒水到a中，把a倒满
4 0 4 6 从a倒水到c中，把a倒空
5 3 1 6 从b倒水到a中，把a倒满
6 0 1 9 从a倒水到c中，把a倒空
7 1 0 9 从b倒水到a中，把b倒空
8 1 7 2 从c倒水到b中，把b倒满
9 3 5 2 从b倒水到a中，把a倒满
10 0 5 5 从a倒水到c中，把a倒空
整个过程中，一共有3次"从a倒水到c中，把a倒空"，有2次"从c倒水到b中，把b倒满"；
至于其中解模数方程的方法，一些关于数论的书上有介绍，说起来也比较麻烦，有很多的定理公式，我直接给出一个程序吧：
==========================================================
c 语言的程序：
==========================================================
/********************************************
求解模线性方程 ax=b (mod n) ,n>0
copyright starfish
2000/10/24
*********************************************/
void modular_linear_equation_solver(int a, int b, int n)
{
int e,i,d;
int x,y;
d = ext_euclid(a, n, x, y);
if (b%d>0) {
printf("No answer!\n");
} else {
e=(x*(b/d))%n;
for (i=0; i<d; i++) //notice! Here x maybe less than zero!
printf("The %dth answer is : %ld\n",i+1,(e+i*(n/d))%n);
}
}
其中用到的ext_euclid 函数如下：
/*********************************************
扩展欧几里德算法求gcd(a,b)=ax+by
copyright starfish
2000/10/24
*********************************************/
int ext_euclid(int a,int b,int &x,int &y)
{
int t,d;
if (b==0) {x=1;y=0;return a;}
d=ext_euclid(b,a %b,x,y);
t=x;
x=y;
y=t-a/b*y;
return d;
}
==========================================================
pascal语言的程序：
==========================================================
{=== 扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y ===}
function extended_euclid(a,b:longint;var x,y:longint):longint;
var
t:longint;
begin
if b=0 then
begin
result:=a;
x:=1;
y:=0;
end
else
begin
result:=extended_euclid(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
{=== 求解模线性方程 ax ≡ b (mod n) 其中n>0 ===}
procedure modular_linear_equation_solver(a,b,n:longint);
var
d,x,y,e,i:longint;
begin
d:=extended_euclid(a,n,x,y);
if b mod d>0 then
writeln('No answer!') {输出无解信息}
else
begin
e:=x*(b div d)mod n;
for i:=0 to d-1 do
writeln( (e+i*(n div d)) mod n ); {输出第i个解 }
end;
end;
Eric
realfun
Lee MaRS
2008/11/29 realfun <rea...@gmail.com>:
--
一堆南极熊聚在一起做计算, 大家都不累. 恩.
Blog : http://leemars.ycool.com
MSN & Gtalk : leemars at gmail.com