算法笔试模拟题精解之“叠叠高”
算法笔试模拟题精解之“叠叠高”
贡献者 | 黄信旭
简介：题目中问的是可以组成多少种不同高度的塔。首先计算每种高度的塔至少
需要多少张卡片，然后判断多出来的卡片数与至少需要的卡片数之间的关系。
题目描述
等级：容易
知识点：数论
查看题目：叠叠高
A 同学买了 n 张卡片，他想用卡片来叠成一个塔，每层塔由数量不同的房间组
成，且高层的房间数量必须少于低层的房间数量，房间可看做两张倾斜的卡片组成，
两张卡片上面头部相接触。特殊的，每层的所有房间必须相邻，且高层的房间需要建
在天花板上。
当 n=13 的时候只有以上两种方法去叠，但只能叠高度为 2 的塔。
相邻两个房间之间用一张卡片作为天花板相连。现在他想知道 n 张卡片全部使用
的情况下他一共可以叠成多少种不同高度的塔。
输入一个整数 n(1 <= n <= 10^9)，表示卡片数量；
输出一个数字，可以叠成的高度的种类数。
示例 1
输入：
13
输出：
1
解题思路：数学题
题目中问的是可以组成多少种不同高度的塔。
首先计算每种高度的塔至少需要多少张卡片，然后判断多出来的卡片数与至少需
要的卡片数之间的关系。
观察下图三层的塔。从上向下。
第一层一个房间，第二层两个房间，……，第 i 层 i 个房间。
一个房间需要 2 张卡片，两个房间需要 5 张卡牌（每个房间 2 张 + 天花板 1
张），……，i 个房间需要 2i+i-1 = 3i-1 张。
这样每一层的卡片数都可以计算出来了，前 k 层的卡片数求和即可。记前 k 层最
少需要 f(k) 张卡片
接下来观察多余卡片与房间的关系。下图中圈出来的房间位置从 1 层放到了 2
层。因此，对于多出来的卡片，我们可以都放到第一层处理（因为题目只问有多少种
不同高度，而不是多少种不同的搭建方法）。
每多出来一间房，需要 3 张卡片（包括天花板）。所以多余的卡片为 3 的倍数，
则这个高度的塔可以搭建。
计算过程
- 从第一层开始，计算 f(i)，直到 f(i) 大于 K。
- 判断每个 f(i) 与 k 的差值是否为 3 的倍数，是，则总数加 1。
时间空间复杂度都很小。f(i) 不需要一个数组来保存，只需要算出当前层的直接
判断是否为 3 的倍数即可。
看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”