manthanein 发表于 2022-12-4 01:45:12

倒水问题的一般解答

本帖最后由 manthanein 于 2022-12-4 01:49 编辑

倒水问题大概可以分成限制总用水量的倒水问题和不限总用水量的倒水问题。
如果不限用水量，那么对于两个杯子的情况就是简单的不定方程。
如果限制用水量，假设有ABC三个杯子，容量从大到小，A杯容量为总用水量，可以这么倒：
（1）A杯倒满C杯。
（2）C杯的水倒入B杯：如果不能倒满B杯则全部倒入，如果能倒满，先把B杯倒满，再把装满的B杯倒入A杯，然后把C杯剩下来的水倒入空下来的B杯。
（3）重复以上步骤。

用excel，假设第一行为三杯容量，第二行为A杯容量、0、0，那么后面单元格的公式可以写成：

A3 =IF(MOD(ROW(),2)=1,A2-$C$1,IF(B2+C2<$B$1,A2,A2+$B$1))
B3 =IF(MOD(ROW(),2)=1,IF(C2=0,B2,C2),IF(B2+C2<$B$1,B2+C2,0))
C3 =IF(MOD(ROW(),2)=1,$C$1,IF(B2+C2<$B$1,0,B2+C2-$B$1))
下拉后就能得到一个倒水方案给出很多种情形的解，如三杯分别为29、18、13：

29        0        0
16        0        13
16        13        0
3        13        13
21        0        8
8        8        13
26        0        3
13        3        13
13        16        0
0        16        13
18        0        11
5        11        13
23        0        6
10        6        13
28        0        1
15        1        13
15        14        0
2        14        13
20        0        9
7        9        13
25        0        4
12        4        13
12        17        0
-1        17        13
17        0        12
4        12        13
22        0        7
9        7        13
27        0        2
14        2        13
14        15        0
1        15        13
19        0        10
6        10        13
24        0        5
11        5        13

问：这种做法什么时候适用？如果不适用的情形怎么办？两个水杯限制总量可能倒出给定容量吗？

aimisiyou 发表于 2022-12-6 11:00:21

不能出现负数吧

northwolves 发表于 2022-12-6 17:39:01

递归吧，类似汉诺塔

aimisiyou 发表于 2022-12-8 15:14:19

northwolves 发表于 2022-12-6 17:39
递归吧，类似汉诺塔

有些区别，没有限定是哪一个瓶子，且移动规则也有些区别。
页: [1]
查看完整版本: 倒水问题的一般解答