- 浏览: 1290147 次
- 性别:
- 来自: 江苏
最新评论
-
honey_fansy:
的确,不要自己的支持就说完美支持,我的就不行,别说我的不是fi ...
无js实现text-overflow: ellipsis; 完美支持Firefox -
fanchengfei:
事件长微博,欢迎转发:http://weibo.com/332 ...
《在路上 …》 写代码也需要一点演技 – python2.6 的 class decorator -
blued:
没有报错,但排版效果一点都没有 咋回事。请指教
python排版工具 -
szxiaoli:
耍人呀,效果在哪儿呀
滑动效果 -
accaolei:
这个能监到控子目录吗?,我测试了一下,发现子目录里的文件监控不 ...
windows监控目录改动
3.
starfish(海星) ( ) 信誉:97 2001-10-28 22:53:55Z 得分:20
?
你的这个问题叫做量水问题,虽然宽度优先搜索可以做,但是那样做太蠢了:)复杂度太高。这个问题以前有人问过我,我把答案贴出来:)
[量水问题]:
有三个分别装有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;
2.
发信人: eigolomoh()
整理人: 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不是唯一的,
所以倒水的方式也不是唯一的。
1.
http://www.nocow.cn/index.php/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
问题描述:有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.
starfish(海星) ( ) 信誉:97 2001-10-28 22:53:55Z 得分:20
?
你的这个问题叫做量水问题,虽然宽度优先搜索可以做,但是那样做太蠢了:)复杂度太高。这个问题以前有人问过我,我把答案贴出来:)
[量水问题]:
有三个分别装有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;
2.
发信人: eigolomoh()
整理人: 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不是唯一的,
所以倒水的方式也不是唯一的。
1.
http://www.nocow.cn/index.php/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
问题描述:有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.
发表评论
-
Programming in Lua 读书摘抄
2008-10-16 01:25 3624据某某C++的叛徒说"感觉很多地方 lua 都是鄙 ... -
一个图像配准的小程序
2008-05-16 04:36 5035为伊人而coding. 源代码/程序见文末附件 分享一下, ... -
诡异的Windows编程
2008-05-10 10:44 1702在winx的example中添加了一个picture cont ... -
一道按单词逆转字符串的面试题
2008-05-03 15:42 2987/* python的string是不可变的,故无法进行in-p ... -
前100大的元素
2008-04-12 13:31 1707//清理硬盘,备份一下以前的程序 #include <c ... -
Boost 1.35发布
2008-03-30 12:22 2982添加了12个库,其中有ASIO网络库,啊啊啊啊啊啊啊啊啊啊啊啊 ... -
读 代码优化 的总结
2007-11-09 13:02 2060系列文章见 http://blog.c ... -
百度之星2007初赛第一条-水果开会时段
2007-05-26 23:22 3895百度之星2007年初赛第一条 时间好紧张,只完成了一题... ... -
2006百度之星程序设计大赛试题-变态比赛规则(解答)
2007-05-15 10:57 40682006百度之星程序设计大赛试题-变态比赛规则(解答) 题目 ... -
2006年百度之星程序设计大赛试题-百度语言翻译机(解答)
2007-05-13 21:26 6808题目+我的解答打包下 ... -
[翻译]Berkeley DB 文档 - C++入门篇 - 1.3节 - 访问方式(Access Methods)
2007-05-11 16:45 3824[翻译]Berkeley DB 文档 - C+ ... -
[意译]Berkeley DB 文档 - C++入门篇 - 1.2节 - Berkeley DB 概述
2007-05-10 10:45 4016[意译]Berkeley DB 文档 - C+ ... -
C++ std名字空间ostream_iterator与的诡异问题
2007-05-09 13:06 6012为了方便显示map而自定义的两个函数,出现了一个诡异的问题,感 ... -
[小技巧]集成Astyle到Microsoft Visual Studio
2007-04-08 18:15 5101Astyle是非常好用的开源的C++代码整理工具,能使你凌乱的 ... -
smartwin++之旅_1
2007-03-01 21:47 5251= 概览 = Smartwin++是一个体现了现代的C++设 ... -
我的文章整理
2005-11-15 19:21 2001我的文章整理(点击浏览/下载阅读) 《程序员,在路上……》 ... -
学习wxWidgets
2005-11-19 03:33 2383写作中.... 下面是链接,请点击浏览,希望大家多多指教和提意 ... -
学习ICE 3.0
2005-11-23 22:01 1944写作中.... 下面是链接,请点击浏览,希望大家多多指教和提意 ... -
怎么链接到动态链接库呢?
2005-11-28 22:36 3926先谢谢cppblog的各位指教. 链接到静态库(*.lib)很 ... -
Function object(函数对象)
2005-12-01 20:14 2426学习《C++ Primer》的笔记 函数指针的一种替代策略是F ...
相关推荐
CSDN 编程大赛 倒水问题,这道题不难,也正是这个原因,我这道题出了些问题,后面改进,可惜却没机会在测试它,因为这题下线了
NULL 博文链接:https://touch-2011.iteye.com/blog/1038893
初学IOS做的一个小玩意,8.5.3 三个水杯互相倒水,直至2个水杯都是4
java项目_五五开倒水 java项目_五五开倒水 java项目_五五开倒水
在网上看到这个用C#做的倒水解密游戏,感觉不错,分享一下了。
自己做的3D倒水是初学者的首选 和容易懂的
1、 编程解决如下数学问题:有12升水,怎样利用一个8升和一个5升的容器将水分为两个6升?要求以如下格式打印出分水步骤。(20分) a12 b8 c5 12 0 0 * * * ( “*”表示当前状态下每个容器的盛水量) ........
有两个水壶,一个盛满可以4公斤水,另一个3公斤水,水壶没有任何标记。怎样在能装4公斤的水壶里恰好只装2公斤水。使用状态空间法和盲目广度优先搜索算法解决这个问题。
这是Nils的一篇文章,基于LBM的自适应网格粗糙算法,来模拟往杯中倒水的情景。很有参考价值。
倒水解密游戏源码 游戏介绍: 《倒水解密》是一款很不错的益智类游戏 有N个容量不同的瓶子,指定「将a升水倒入容量为b的瓶子」。 游戏要求通过装水、倒水,达成给定的目标。 游戏操作方式如下: ?在瓶子上双击...
两个杯子倒水问题,两个版本解决方案,BFS遍历方式,csdn
用VC控制台实现的倒水程序 “倒水”算法代码实现
有3颗星强迫症的玩家兼程序员,写出这么个自动求解的小程序,以后这个问题再也不是问题了。 点击这里试试杯子倒水问题自动求解吧 算法基本逻辑: 每个杯子有倒满、倒空、倒入其它杯子的操作,所以总共是: 杯
野比的倒水解密游戏,纯GDI+,自己DIY游戏。
#资源达人分享计划#
倒水声.zip音效声音WAV格式或MP3格式素材下载倒水声.zip音效声音WAV格式或MP3格式素材下载 1.适合学生做毕业设计用 2.适合程序员开发项目用 3.适合小公司做项目使用
这是一份使用PowerPoint自带绘图工具绘制的一个,透明质感的玻璃瓶,玻璃瓶内的液体正在向外倾泻。 本PPT素材,适合用于在PPT中说明,某件事物包含哪些内容。或并列关系PPT内容表达。 关键词:瓶子、玻璃瓶...
主席台倒水礼仪-.docx
Jugs问题求解C++