经典倒水问题

2024-01-19 02:28| 来源: 网络整理| 查看: 265

倒水问题

　　有两个容器，容积分别为a升和b升，有无限多的水，现在需要c升水。问能否通过有限次的倒水操作，得到c升水？

解析

这类题有一个套路，小容量的杯子不断往大杯子里面倒水，大杯子满了之后就把大杯子全倒掉。先举个简单的例子，比如：3升和5升的杯子，得到4升水，下面步骤中的第一个数字表示3升杯子中的水量、第二个数字5升杯子中的水量，开始时都为0：

0，0

3，0

0，3

3，3

1，5

1，0

0，1

3，1

0，4

bingo，得到4升水了

到这你可能发现一些规律了：

小杯不断往大杯中倒水

大杯满了的时候，大杯全部倒掉

小杯继续往大杯倒水

重复上面的步骤，直到得到目标水量，或者实现不了目标而退出循环

这是不是很像数学中的某一种运算呢？对，就是“%”取余运算。就拿上面的案例来说：

3 % 5 = 3，第一杯倒完后大杯中有3升水

6 % 5 = 1，6表示当前倒的是第二小杯水，第二小杯水倒完的时候，大杯可以得到1升水

9 % 5 = 4，表示第三小杯水倒完后，我们就能得到4升水了。

用3的倍数不断地去对5取余，看结果是否满足

用数学的方法表达：求出a和b的最大公约数，如果c能被a和b的最大公约数整除，则可以倒出c升水

代码实现 int gcd(int a, int b) //递归求a和b的最大公约数 { return (b == 0) ? a : gcd(b, a % b); } int gcd1(int a, int b)//非递归求a和b的最大公约数 { if (a == 0) return b; if (b == 0) return a; while (a % b != 0)//b不断地去成为余数a % b，a去成为上一次的b { int yu = a % b; a = b; b = yu; } return b; } bool can(int a, int b, int c) { if (c % gcd1(a, b) == 0) return true; else return false; }

【本文地址】

公司简介

联系我们