算法题——立方体的体对角线穿过多少个正方体?

简介: 这道题是笔者当年参加竞赛的题目,多年来一直未得其解,久久不能释怀。近日,重新拿起该题细细研究,终于将其解出,著文以记之。   问题描述: 长方体长X,宽Y,高Z。X、Y、Z都是正整数。长方体由长1、宽1、高1的正方体堆积而成。

这道题是笔者当年参加竞赛的题目,多年来一直未得其解,久久不能释怀。近日,重新拿起该题细细研究,终于将其解出,著文以记之。

 

问题描述:

长方体长X,宽Y,高Z。X、Y、Z都是正整数。长方体由长1、宽1、高1的正方体堆积而成。那么长方体的体对角线穿过多少个正方体?

 

这个题考量三维空间的想象。近日研究的时候,尝试先考量二维的情况,在求解出二维的情况下,在推广到三维里。下面是二维情况下的问题描述

 

长方形长X,宽Y。X、Y都是正整数。长方形由长1、宽1的正方形组成。那么长方形的对角线穿过多少个正方形?

 

 

以实例说明。长方形长6,宽4。长方形由长1、宽1的正方形组成。那么长方形的对角线穿过多少个正方形?

这个还是比较简单的,直接用图表示即可,如下图所示:

 

1

 

如上图所示,对角线一共穿过8个正方形(灰色部分)。但是,我们不可能每个问题都画图表示,比如长777,宽581的长方形的解就很难画图表示(数字太大,不容易精确表示)。

仔细看看,这8个正方形实际上把对角线分成了8段。线段的端点是对角线和水平线(或竖直线)的交点。

于是,问题似乎可以转化成

要求穿过多少个正方形,实际上相当于求有多少个线段

要求有多少个线段,实际上相当于求对角线和水平线和垂直线的交点的个数

 

把上图放在平面直角坐标系中,左下角坐标为(0,0),右上角坐标为(6,4)

则对角线的直线方程为

 

clip_image002

 

和我们一般想象中的直线方程不太一样。没关系,首先这个是正确的直线方程,其次是为了和后面的三维中的直线方程的表现形式统一。

我们把对角线和水平线(或竖直线)的交点在图上标示出来(为了后文的描述方便,我用不同颜色标示点)

 

2

左下角的起点用灰色标示,红色的点标示对角线和竖直线的交点(交点的横坐标是整数),绿色的点标示对角线和水平线的交点(交点的纵坐标是整数)

起点不算,则穿过的方块数和线段数和点的个数一致(都是8个)。

 

红色点的坐标(横坐标是整数)分别是:

clip_image002[4]

个数和长方形的长的数值是一致的(是6)

 

绿色点的坐标(纵坐标是整数)分别是:

clip_image002[6]

个数和长方形的宽的数值是一致的(是4)

 

可以看出,红色点和绿色点有2个点是重合的(图上用半红半绿的点标示),因此这些点合在一起就是如下(按照和起点的远近来进行排序)

clip_image002[8]

 

于是该问题的求解过程可以如下表示:

1、求出横坐标是整数的点的个数,就是长方形长的数值。本题是6

2、求出纵坐标是整数的点的个数,就是长方体宽的数值。本题是4

3、求出步骤1和步骤2中重合的点的个数,也就是横纵坐标都是整数的点的个数。本题是2

4、问题的答案:步骤1的答案+步骤2的答案-步骤3的答案。本题是6+4-2=8

 

步骤1、2、3、4中,关键是步骤3,如何求出步骤1和步骤2中重合的点的个数,也就是横纵坐标都是整数的点的个数。

 

最大公约数:正整数a和b,若a能被b整除,则a是b的倍数,b是a的约数。正整数a和b中约数最大的那个称为a和b的最大公约数,记作gcd(a,b)

 

本题中,(4,6)=2,正好是步骤3的答数,是巧合么?不是,接下来我们来证明。

 

证明:长X、宽Y的长方形,对角线经过双整数点(横纵坐标都是整数)的个数为gcd(X,Y)(注:不算起点)

证:令x1=X/gcd(X,Y),y1=Y/gcd(X,Y)。则x1和y1都是整数,且x1和y1互质(除1以外,没有公约数)。

对角线所在的直线方程为

clip_image002

当x取整数时(1≤x≤X)时,要使y也是整数,则x必须取x1的倍数(这样才能把分母完全约掉)

而在1到X之间,x1的倍数一共有gcd(X,Y)个

证明完毕

 

综上所述:长方形长X,宽Y。X、Y都是正整数。长方形由长1、宽1的正方形组成。那么长方形的对角线穿过多少个正方形?

其解为:Ans=X+Y-gcd(X,Y),可以用下图表示

3

 

例如:

长6,宽4的长方形的对角线穿过6+4-gcd(6,4)=6+4-2=8个正方形

长5,宽3的长方形的对角线穿过5+3-gcd(5,3)=5+3-1=7个正方形

长12,宽8的长方形的对角线穿过12+8-gcd(12,8)=12+8-4=16个正方形

 

扩展到三维。长方体长X,宽Y,高Z。X、Y、Z都是正整数。长方体由长1、宽1、高1的正方体堆积而成。那么长方体的体对角线穿过多少个正方体?

长X、宽Y、高Z的立方体的体对角线的直线方程是

clip_image002[5]

这个方程虽然有点怪,但是学过空间解析几何的都明白这个方程的正确性

 

求解的过程和二维的类似,也是找寻坐标是整数的点。可以用下图表示:

4

 

 

其解为:Ans=X+Y+Z-gcd(X,Y)-gcd(X,Z)-gcd(Y,Z)+gcd(X,Y,Z)

例如:

长5,宽3,高4的长方体的体对角线穿过5+3+4-gcd(5,3)-gcd(5,4)-gcd(3,4)+gcd(5,3,4)=5+3+4-1-1-1+1=10个正方体

长8,宽6,高3的长方体的体对角线穿过8+6+3-gcd(8,6)-gcd(8,3)-gcd(6,3)+gcd(8,6,3)=8+6+3-2-1-3+1=12个正方体

长12,宽8,高6的长方体的体对角线穿过12+8+6-gcd(12,8)-gcd(12,6)-gcd(8,6)+gcd(12,8,6)=12+8+6-4-6-2+2=16个正方体

 

 

下图是长5,宽3,高4的长方体的体对角线穿过正方体的示意图,一共10个正方体,你看清了么?

3-4-5

 

 

 

这个题历时若干年,总是百思不得其解。也是今朝灵光一闪,终于把该题解决了。也总算是一块石头落了地

相关文章
|
4月前
|
人工智能 弹性计算 自然语言处理
阿里云产品与AI产品优惠信息参考:Token Plan、万小智AI建站、AI组合购等优惠信息汇总
阿里云最新云产品与AI产品优惠信息:覆盖基础云服务器、AI大模型、编程智能体、视频生成等全链路产品。核心优惠包括:百炼全模型通用Token Plan包季低至4.5折,覆盖150+款大模型;轻量应用服务器2核2G新人专享68元/年起,e实例99元/年续费同价;Qoder CN编程智能体59元/月起,秒悟Pro版限量9.9元/月,HappyHorse视频生成限时8折,万小智AI建站赠域名与灵感值。同时搭配最高100万元OPC创新助力Token补贴,全方位降低AI落地与上云综合成本。
|
10月前
|
缓存 JSON 监控
采购与招标 item_search - 关键词搜索接口对接全攻略:从入门到精通
采购与招标item_search接口(cgzb.item_search)提供多维度招标项目检索,支持关键词、地区、预算、发布时间等精准筛选,分页返回结构化数据,联动item_get获取详情,适用于商机监控、投标决策等场景。HTTPS+API Key/Secret认证,JSON/XML双格式响应,合规性强、筛选精准、权限分明。本攻略覆盖权限申请、签名认证、Python对接、调试排错及生产优化,助力全链路高效集成。(239字)
|
11月前
|
存储 人工智能 编译器
智驾大模型的「隐形战场」:当GPU堆不动了,行业拼什么?
与参会嘉宾一起探讨了如何通过技术协作加速智能驾驶的进步,分享了各自在自动驾驶技术栈中的前沿实践与生态思考。
|
12月前
|
Linux Python
Anaconda和Miniconda在Linux系统下迁移虚拟环境
将A服务器的Miniconda虚拟环境loonflow3通过`conda list --explicit`导出配置,并打包env目录为tar.gz文件,使用scp传输至B服务器后解压至对应路径,再激活环境即可完成迁移。
832 5
|
11月前
|
监控 前端开发 安全
区块链DApp开发和上线
DApp开发步入高性能与合规并重新阶段,涵盖智能合约、前端交互及中间件三层架构。北京木奇移动专注软件外包,提供专业开发服务,欢迎合作。商务联系:muqi2026。#区块链开发 #DAPP开发
|
10月前
|
移动开发 前端开发 C++
HTML的标签
HTML标签需先掌握核心规则:成对出现或自闭合,属性加引号,推荐小写。按功能分类学习更高效——结构标签构建骨架,文本标签排版内容,媒体标签插入资源,列表与表格展示数据,表单实现交互,语义化标签提升可读性。建议新手从高频标签入手,边写边练,结合MDN查阅,注重语义理解而非死记硬背,规范书写避免常见错误。(239字)
2697 0
|
机器人 数据中心
Dataphin功能Tips系列(79)精准获知标准更新动态,协同治理更高效
Dataphin支持数据标准变更订阅,可实时通过站内信、邮箱或钉群机器人通知相关人员,确保业务及时响应。用户可通过标准列表、个人中心等入口批量订阅,变更消息包含状态、版本及跳转链接,便于快速查看与处理。
424 8
|
运维 监控 安全
数据安全:网络时间同步构建信息化堡垒
NTP网络授时服务器构建统一时间坐标系,支持北斗/GPS高精度授时,具备高稳守时、高并发处理与安全认证能力,广泛应用于金融、电力、交通、政务及工业互联网,保障系统时序一致与数据安全。
怎么找到安装软件的存放目录?安装软件所在目录查找教程
怎么找到安装软件的存放目录?安装软件所在目录查找教程
2146 4