经典倒水问题 | 您所在的位置:网站首页 › 三个容器倒水问题数学 › 经典倒水问题 |
倒水问题
有两个容器,容积分别为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; }
|
CopyRight 2018-2019 实验室设备网 版权所有 |