两个桶兑出特定容积的水
面试的时候,可能会经常碰到这样一个问题:嘉定区有两个桶,一个容量为 3 升,一个容量为 5 升,我们怎么能够不通过其他度量工具的帮助兑出 1 升的水来。假定水是无限的。
!! 此处限制条件:会给定先倒入哪个桶,并且在倒的过程中,不能出现如下情况:给定先倒的桶空了,而另一个桶是满的。
例如题:https://exercism.io/my/solutions/3b849bba3ee840ccac12eb7ca734ba8e
问题分析
如果单纯针对这个问题来看,相信我们还是可以很容易的得到一个推导过程。既然我们有两个桶,一个是 3 升,一个是 5 升,那么我们可能需要将一个桶装满水,然后倒到另外一个桶里,通过将一个桶倒满而另外一个桶可能还有盈余来达到最终兑换出期望容量的水的目的。按照这个思路,我们可以开始第一步分析。
初步分析
上个例子问题中,我们整个兑水的过程可以描述如下(假设先倒入 3 升的桶):
(3, 0)
将 a 桶倒满;(0, 3)
将 a 桶倒入 b 桶;此情况可以出现,因为虽然 a 桶满了,但是 b 桶未满(3, 3)
将 a 桶倒满;(1, 5)
将 a 桶倒入 b 桶 2 升,b 桶仅剩下 2 升的容积。此时 a 桶剩下 1 升,即为所求。
从这个特定的问题本身,似乎没什么特殊的,我们就这么来回的倒腾似乎有点靠运气。
可是,如果我们再深层次的去想想。
- 是不是任意容积的水都可以通过指定容量的两个桶给兑换出来呢?
- 如果可以兑换的话,它们之间有没有什么规律?
- 如果不行的话,问题的根源又是在哪里呢?
进一步分析
假定我们定义这两个桶分别为 a 升, b 升。那么它们这两个桶里水的容积可以表示为(a, b)
这样一个数对,它们满足什么条件才能兑换出 n
升的水?
试想, n 升的水肯定是这两个桶兑换过程中的容积差 的积累,即 a*x - b*y = n
(如果从 a 倒满开始)。
即 感觉 n 必须是 a 和 b 的线性组合才能兑换出来。( 🙋♀️ 下面我们会通过非常严格的证明证明这点)
可以使用 💡** 数学归纳法证明**:假设有两个桶,容量分别为 a 和 b。那么按照前面兑水的要求,最后桶里的水量 n 总是 a 和 b 构成的一个线性组合。
高中毕业 🎓 这么些年,是不是早就还给数学老师了? 👀
假设 P(m) 表示经过 m 步兑水后的结果,那么需要证明:
- 初始条件P(0)是 a 和 b 线性组合:P(0)表示空桶状态, P(1) 表示先往要求的桶中倒满水,那么 0 升(
P(0)= a*
0 + b*0
)和 a 升(P(1) = a*1+b*0
) 或者 b 升(P(1) = a*0+b*1
) 都是 a 和 b 线性组合 - 如果 P(m) 是 a 和 b 的线性组合, 那么 P(m+1) 也是 a 和 b 的线性组合:如果 P(m) 是 a 和 b 的线性组合,即假设两个桶分别是
P(m_a) = a * sa + b*ta
,P(m_b) = a * sb+ b*tb
那么 P(m+1)是什么情况:- 一个桶空了,另一个桶为
P(m_a) + P(m_b)
:明显,这种情况下,P(m+1)
仍是 a 和 b 线性组合(P(m_a)
和P(m_b)
分别是 a 和 b 线性组合, 那么P(m_a) + P(m_b)
肯定也是 a 和 b 线性组合)。 - 一个桶满了(可能是 a 或者 b),另一个桶则为
P(m_a) + P(m_b) - a
或者P(m_a) + P(m_b) - b
,因为容积总量不变:P(m_a)
和P(m_b)
分别是 a 和 b 线性组合,那么P(m_a) + P(m_b)
肯定也是 a 和 b 线性组合,那么P(m_a) + P(m_b)-a
或者P(m_a) + P(m_b) - b
肯定也是 a 和 b 线性组合。
- 一个桶空了,另一个桶为
所以在兑换过程中,每个桶的水容量均为桶容量的线性组合!(目标容量肯定是兑换过程中,某个桶的容量)
解决问题
我们证明了桶容量和目标容量的关系,但是在实际求解的时候,使用a*x - b*y = n
这样,一个个 x 和 y 的数对去尝试吗? 这肯定是比较笨的方法 👎
这个时候,我们似乎陷入了一个困境,看似没有什么有效的办法能够一步就判断出来某个给定的容积是否可行。
我们再来看这个线性组合的表示方式a*x - b*y
。我们要判定一个数字是否可以表示为a*x - b*y
的时候会比较困难。如果我们来看看 a, b 之间有没有什么共同的关系呢?
这一步会比较困难,不过如果我们想到最大公约数的话,这个问题就有了一个新的思路。我们知道,对于两个整数来说,它们的最大公约数gcd(a, b)
同时整除这两个数字。那么对于数字 a 和 b 来说,他们可以分别表示为a = s * gcd(a, b)
, b = t * gcd(a, b)
。那么对于 a 和 b 的线性组合a*x - b*y
来说呢?很显然,它们也必然能够被gcd(a, b)
整除。
这个时候,我们就发现了一个非常重要的结论: 对于 a, b 的线性组合**a*x - b*y**
,它们能够被**gcd(a, b)**
整除。
由于 目标容量 n 升水是 a, b 的线性组合, 那么 n 也能过被**gcd(a, b)**
整除。
那么 n 能被 gcd(a, b)
整除, n 是 a, b 的线性组合吗?
欧几里德扩展定理:如果 a 和 b 是不都为 0 的任意整数,则 gcd(a,b)是 a 和 b 的线性组合集合 { ax + by | x , y 为整数 } 中的最小正元素。
由于目标 n 能被 gcd(a, b)
整除, 且gcd(a, b)是
a 和 b 的线性组合集合的最小元素, 那么 n 肯定是 a 和 b 的线性组合,与我们之前分析的直觉一直。
所以 ** n 能被 **gcd(a, b)**
整除 <===> n 是 a 和 b 的线性组合**。
解
判断是否可以兑换出目标 n 升水(RUST 代码):
pub fn reachable(a: u8, b: u8, goal: u8) -> bool { let gcd = gcd(a, b); return goal % gcd == 0; } pub fn gcd(a: u8, b: u8) -> u8 { if b == 0 { return a; } return gcd(b, a % b); }
兑换过程,核心:
//判断有解吗?a作为开始桶 if reachable(a, b, goal) { let mut a1 = 0, b1 = 0; // 可能有特殊情况:b桶就是目标goal ,那么只需要装装样子把a装满,再直接装b即可 if b == goal { a1 = a; b1 = b; //返回 } while b1 != goal && a1 != goal { if a1 == 0 {// a 桶空 a1 = a; }else if b1 == b || a1+b1 ==b {//b 桶满 或者 剩余的水恰好只能装满b(满桶顺序不能调换) b = 0; }else if b1 + a1 < b {// a b 两桶剩余容量 不够装满b桶 b1 += a1; a1 = 0; } else { // ab 两桶剩余水量 大于b桶容量 let c = a1 + b1; a1 = c - b; b1 = b; } } }
题目的兑换过程:
#[derive(PartialEq, Eq, Debug)] pub enum Bucket { One, Two, } /// A struct to hold your results in. #[derive(PartialEq, Eq, Debug)] pub struct BucketStats { /// The total number of "moves" it should take to reach the desired number of liters, including /// the first fill. pub moves: u8, /// Which bucket should end up with the desired number of liters? (Either "one" or "two") pub goal_bucket: Bucket, /// How many liters are left in the other bucket? pub other_bucket: u8, } /// Solve the bucket problem pub fn solve(capacity_1: u8, capacity_2: u8, goal: u8, start_bucket: &Bucket) -> Option<BucketStats> { if reachable(capacity_2, capacity_1, goal) { let buckets: [u8; 2] = [capacity_1, capacity_2]; //开始倒水的桶index let mut start_index: usize = 0; match start_bucket { Bucket::Two => start_index = 1, _ => start_index = 0, } let other_index = (start_index + 1) %2; //中间状态 let mut state: [u8; 2] = [0, 0]; let mut counter: u8 = 0; //特殊情况, other桶就是goal,那么只需要两步就可以,第一步将Bucket::One 装满, 第二步将Bucket::Two装满 if buckets[other_index] == goal { state[start_index] = buckets[start_index]; state[other_index] = buckets[other_index]; counter +=2; }else { //不是goal的状态,则循环处理 while state[other_index]!= goal && state[start_index]!=goal { //开始桶没水了,倒满 if state[start_index] == 0 { state[start_index] = buckets[start_index]; counter +=1; println!("({}, {})\t {} full",state[0], state[1], start_index ); }else if state[start_index] + state[other_index] < buckets[other_index] { //两个桶剩余量小于 other 桶的量,则全部倒入other桶的量 state[other_index] = state[start_index] + state[other_index]; state[start_index] = 0; counter +=1; println!("({}, {})\tpour {} into {}",state[0], state[1], start_index, other_index ); }else if state[other_index] == buckets[other_index] || // n * buckets[start_index] = buckets[other_index]时,可能出现如下情况 state[start_index] + state[other_index] == buckets[other_index] { // other 桶满了,则需要倒掉 state[other_index] = 0; counter +=1; println!("({}, {})\tempty {}",state[0], state[1], other_index ); }else{ //other 桶未满,且start 桶有水,则直接倒倒other桶。 let total_tmp = state[start_index] + state[other_index]; state[other_index] = buckets[other_index]; state[start_index] = total_tmp - buckets[other_index]; println!("({}, {})\tpour {} into {}",state[0], state[1], start_index, other_index ); counter +=1; } println!("({}, {})\n\n", state[0], state[1]); } } if state[start_index] == goal { match start_index { 0 => return Some(BucketStats{moves: counter, goal_bucket: Bucket::One, other_bucket:state[other_index]}), _ =>return Some(BucketStats{moves: counter, goal_bucket: Bucket::Two, other_bucket:state[other_index]}), } }else if state[other_index] == goal { match other_index { 0 => return Some(BucketStats{moves: counter, goal_bucket: Bucket::One, other_bucket:state[start_index]}), _ =>return Some(BucketStats{moves: counter, goal_bucket: Bucket::Two, other_bucket:state[start_index]}), } } } None }
上述代码中由于要处理给定两个桶中任意个为初始装满水的情况,比较冗余。
附
如果 a 和 b 是不都为 0 的任意整数,则 gcd(a,b)是 a 和 b 的线性组合集合 { ax + by | x , y 为整数 } 中的最小正元素
证明如下:s 是 a 与 b 的线性组合集中的最小正元素,并且存在 x,y,使得 s = ax + by
成立。
设q=⌊a/s⌋
,
则有 a mod s=a−qs = a−q(ax+by) = a(1−qx)+b(−qy)
因此,a mod s 也是 a 与 b 的一种线性组合。但由于 a mod s 取值范围 [ 0 ,s )
,所以 a mod s=0
(因为 s 是满足这样线性组合的最小正整数,a mod s 是 a,b 的线性组合, 故 a mod s < s
不能取正数只能取 0.)。
a mod s = 0
,那么 a 能被 s 整除, 同理也可得出 b 能被 s 整除,因此 s 是 a 与 b 的公约数,所以 gcd(a, b) >= s
。
又因为 a 与 b 能被 gcd(a, b)
整除,并且 s = ax + by
.
所以 s 能被gcd(a, b)
整除 , s >0 ,可知 gcd(a, b) <= s
。 故 gcd(a, b) = s
,证毕。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Serverless + Egg.js 后台管理系统实战
作为一名前端开发者,在选择 Nodejs 后端服务框架时,第一时间会想到 Egg.js,不得不说 Egg.js 是一个非常优秀的企业级框架,它的高扩展性和丰富的插件,极大的提高了开发效率。开发者只需要关注业务就好,比如要使用 redis,引入 egg-redis 插件,然后简单配置就可以了。正因为如此,第一次接触它,我便喜欢上了它,之后也用它开发过不少应用。 有了如此优秀的框架,那么如何将一个 Egg.js 的服务迁移到 Serverless 架构上呢? 背景 我在文章 基于 Serverless Component 的全栈解决方案 中讲述了,如何将一个基于 Vue.js 的前端应用和基于 Express 的后端服务,快速部署到腾讯云上。虽然受到不少开发者的喜爱,但是很多开发者私信问我,这还是一个 Demo 性质的项目而已,有没有更加实用性的解决方案。而且他们实际开发中,很多使用的正是 Egg.js 框架,能不能提供一个 Egg.js 的解决方案? 本文将手把手教你结合 Egg.js 和 Serverless 实现一个后台管理系统。 读完此文你将学到: Egg.js 基本使用 如何使用...
- 下一篇
探究 Go 语言 defer 语句的三种机制
Golang 的 1.13 版本 与 1.14 版本对 defer 进行了两次优化,使得 defer 的性能开销在大部分场景下都得到大幅降低,其中到底经历了什么原理? 这是因为这两个版本对 defer 各加入了一项新的机制,使得 defer 语句在编译时,编译器会根据不同版本与情况,对每个 defer 选择不同的机制,以更轻量的方式运行调用。 堆上分配 在 Golang 1.13 之前的版本中,所有 defer 都是在堆上分配,该机制在编译时会进行两个步骤: 在 defer 语句的位置插入 runtime.deferproc,当被执行时,延迟调用会被保存为一个 _defer 记录,并将被延迟调用的入口地址及其参数复制保存,存入 Goroutine 的调用链表中。 在函数返回之前的位置插入 runtime.deferreturn,当被执行时,会将延迟调用从 Goroutine 链表中取出并执行,多个延迟调用则以 jmpdefer 尾递归调用方式连续执行。 这种机制的主要性能问题存在于每个 defer 语句产生记录时的内存分配,以及记录参数和完成调用时参数移动的系统调用开销。 栈上分配 G...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果