首页 > 试题广场 >

牛妹的蛋糕

[编程题]牛妹的蛋糕
  • 热度指数：10610 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
众所周知，牛妹非常喜欢吃蛋糕。
第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？

有可能出现多解，返回任意一种可能的结果即可。
示例1

输入

2

输出

3
示例2

输入

4

输出

10

备注:
0
算法知识视频讲解
开通博客
头像 zhouleilei
发表于 2020-03-23 11:30:50
一、思路 用一个数组dp表示当前这天没吃蛋糕之前的蛋糕数目，那么dp的最后一个值，dp[n-1]一定是初始化为1，dp[i]由dp[i+1]推导而来： 因为:     dp[i+1] = dp[i] * (2/3)  - 1 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Miss.Zhou
发表于 2020-02-06 20:22:48
dp中最最基本的递推每一天由后一天的+1 的3/2倍得来 class Solution { public: /** * * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的． * @return long长整型 */ int 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 你永远得不到的祖奶奶
发表于 2020-06-25 11:29:21
众所周知，牛妹非常喜欢吃蛋糕。 第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向#下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时#候只剩下一个蛋糕。 牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？ class Soluti 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CroMarmot
发表于 2021-10-04 02:35:05
题意 一个值操作n次 每次对一个值减少它的三分之一向下取整再减1 问 最终剩余1，初始值是多少 题解 根据样例，最大只有10，所以我们不妨来直接正向模拟 10 10-3-1 = 6 6-2-1 = 3 3-1-1 = 1 把这个数据倒过来看 值 2 3=(1+1)⋅3//23 = (1+1 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Maokt
发表于 2021-07-31 13:42:51
算法思想一：迭代 解题思路： 由题可知，每天的蛋糕数量等于前一天蛋糕数量去除三分之一再加一个；反过来，每天的蛋糕数量等于后一天数量加1的 3/2 倍计算 因此可以采用迭代从n-1天到第一天的蛋糕数量 图解： 步骤 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-03 11:36:05
题目描述众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？这道题是典型的猴子吃桃问题 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛一霸
发表于 2021-07-29 22:45:54
题目：牛妹的蛋糕描述：众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？示例1：输入 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-29 23:19:17
思路： 题目的主要信息： 每天吃掉蛋糕总数的1/3，再额外吃1个 吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕 这是一个数学问题，可以用递归、动态规划、迭代处理。 方法一：递归具体做法：第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归： class Sol 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客534170409号
发表于 2021-08-04 17:21:20
题目描述 众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？主要信息：每天吃蛋糕总 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 StarsシHao
发表于 2020-08-10 17:48:12
1.特殊情况 n < 1时直接。2.设今天有蛋糕y个，前一天有x个。3.由题意得 y = x*2/3-1；也就是说x=3(y+1)/2。4.根据天数n迭代找到第0天有多少蛋糕 /** * * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的． * 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

基础数学
难度：
48条回答 5824浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛妹的蛋糕

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号