我要招人

去企业版

首页 > 试题广场 >

牛妹的蛋糕

[编程题]牛妹的蛋糕

热度指数：10568 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众所周知，牛妹非常喜欢吃蛋糕。

第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。

牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？

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

示例1

输入

输出

示例2

输入

输出

备注:

算法知识视频讲解

Python

牛客717689322号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
def cake(res,n):
for i in range(n-1):
res = int((res+1)*1.5)
return res

class Solution:
def cakeNumber(self , n ):
# write code here
return cake(1, n)

发表于 2021-03-26 00:56:23 回复(0)

Python

角三落

cake[0] = 1

cake[i] - cake[i]//3 -1 = cake[i-1]

发表于 2020-11-10 15:50:01 回复(0)

Python

2020offers冲鸭冲

class Solution:
    def cakeNumber(self , n ):
        # write code here
        if not n:
            return 0
        x=1
        for i in range(n-1):
            x=int((x+1)*3/2)
        return x

迭代法

发表于 2020-08-21 14:56:21 回复(0)

Python

白色纯度

python的两种高效方法：看你喜欢哪一个了

第一种：动态规划

class Solution:
    def cakeNumber(self , n ):
        dp = [0 for _ in range(n)]
        dp[-1] = 1
        for i in range(n-2,-1,-1):
            dp[i] = int((dp[i+1]+1)*3/2)
        return dp[0]

第二种方法，数学倒推解法：

class Solution:
    def cakeNumber(self , n ):
        res = 1
        for _ in range(n-1):
            res +=  1
            res *= 3
            res //= 2
        return res

运行效率都差不多，就这样吧。

发表于 2020-07-29 23:15:02 回复(0)

Python

清风思月

def cakeNumber(self , n ):
        # write code here
        if n == 1:
            return 1
        return (self.cakeNumber(n-1)+1)*3//2

动态规划思想

当n=1，说明只有一天且只吃一个蛋糕；

当n=2，开始计算：sum = 第二天吃的一个蛋糕 + 第一天吃的1/3*sum + 1

求解方程：sum = （第一天吃的 +1）* 3 // 2

同理：当n>1，sum = （前一天吃的总数 +1）* 3 // 2

发表于 2020-07-17 11:50:32 回复(0)

Python

Tappiness

这个题的难点和易错点在于吃掉蛋糕总数三分之一（向下取整）多一个。

首先推导公式:

将y = [x] 记为向下取整函数，则x <= x < x +1

F(1) - [F(1) / 3] = F(2) + 1

F(2) - [F(2) / 3] = F(3) + 1

....

F(n-1) - [F(n-1) / 3] = F(n) + 1

所以

F(n-1) - F(n-1) / 3 - 1 < F(n-1) - [F(n-1) / 3] <= F(n-1) - F(n-1) / 3

所以能够求得前一天蛋糕数量的取值范围

1.5 * (F(n) + 1) <= F(n-1) < 1.5*(n + 2)

最后在取值范围内遍历一下就能找到正确的蛋糕数量了

class Solution:
    def cakeNumber(self , n ):
        # n =0 时直接返回
        if n == 0:
            return None
        dp = [0] * n
        dp[0] = 1
        for i in range(1,len(dp)):
            #获取前一天蛋糕数量的取值范围
            max = int(1.5*(dp[i-1] + 2))
            min = int(1.5*(dp[i-1] + 1))
            #遍历范围，然后找出正确的数量
            for j in range(min,max):
                if j - j // 3 - 1 == dp[i-1]:
                    dp[i] = j
        return dp[n-1]

编辑于 2020-07-10 22:18:02 回复(2)

Python

Richard_Zhouu

def cakenumber(n): 
    if n == 1: 
        return 1  
    res = (cakenumber(n - 1) + 1) * 3 // 2  
    return res

python支持这种形式的递归吗？我在pycharm跑没问题，牛客这里提交不了。

发表于 2020-06-10 12:16:48 回复(0)

Python

微笑先生

我们倒退一下思路，比如第一天的数字为1，他就是一个简单的一元一次方程。x2 = ((x1+1)*3)/2),这个样子，但是我们的结果必须是整数，因为蛋糕无法分割，那么问一下上面这个式子哪里有问题？就在那个÷2，因为在第4天时，这个左边的结果为21，直接除2是不可以的，得不到整数，我们只需要将那个÷变成地板÷就可以了或者说向下取整即可。我用的是python所以双划线//即可。

发表于 2020-05-17 06:21:53 回复(0)

Python

牛客580063049号

就是一个倒推的过程, 我们从第n天一直往第1天退, 设蛋糕数为m 第二天的蛋糕数为m(2/3) - 1

因此, 前一天的蛋糕数就是(m+1)3/2

第n天蛋糕数

n 1

n-1 (1+1)3/2=6

n-2 (6+1)3/2=11.5

因此, 我们只需要定义一个临时变量=1, 然后进行(n-1)次的循环赋值即可

我们可以循环n-1次

这里我第一次想到的是递归, 因为想装一逼, 但是搞了好久才写出来, 尴尬哈

class Solution:
    m = 1
    def cakeNumber(self , n):
        n -= 1
        self.m = int(3*(self.m+1)/2)
        if n == 1:
            return int(self.m)
        return self.cakeNumber(n)

编辑于 2020-03-25 21:35:06 回复(2)