首页 > 试题广场 >

牛妹的蛋糕

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

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

输入

2

输出

3
示例2

输入

4

输出

10

备注:
0
算法知识视频讲解
添加回答
C/C++
卷积神经网络哦头像 卷积神经网络哦 
int cakeNumber(int n) {
        int res = 1;
        while(--n) res = 3 * (res + 1) / 2;
        return res;
    }
这道题不太严谨，理论上是有多组解的，比如n=2是蛋糕总数既可以是3也可以是4。如果我们无视这个不严谨的地方，无脑做还是可以做出来的。。
实际上就是一个正推一个反推，假设前一天为x, 第二题为y，则y = 2x / 3 - 1 ,也即x = 3(y+1) / 2; 重复这个公式n-1次即可。
另外：前面有用递归和开新数组动态规划的答案，都浪费了时间复杂度或者空间复杂度。
发表于 2020-05-04 12:14:05 回复(6)
更多回答
Python
Tappiness头像 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)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    /**
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    int cakeNumber(int n) {
        if(n==0)
            return 0;
        int x = 1;
        for(int i=1;i<n;i++)
            x = 3*(x+1)/2;
        return x;
    }
};

发表于 2020-07-07 20:28:18 回复(0)
ooobsidian头像 ooobsidian 
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    def cakeNumber(self , n ):
        dp=[0 for _ in range(n)]
        if(n<1):
            return 0
        else:
            dp[n-1]=1
            for i in range(n-2,-1,-1):
                dp[i]=3*(dp[i+1]+1)//2
        return dp[0]

发表于 2020-06-14 00:04:00 回复(0)
辣子鸡丁真好吃头像 辣子鸡丁真好吃 
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    public int cakeNumber (int n) {
        // write code here
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 3;
        }else{
            return  3*(cakeNumber(n-1)+1)/2;
        }
    }
}

发表于 2020-06-08 19:12:00 回复(0)
牛客860698372号头像 牛客860698372号 
import math 
class Solution:
    def cakeNumber(self , n ):
        # write code here
         result =1 
         for i in range(n-1):
                result = math.floor((result+1)*3/2)
               
         return result

我的思路如下，首先最后一次的剩余的蛋糕数为1.
假设上一次为X个，吃掉了CEIL(X/3) +1 ,剩下的为2/3 X -1 个

于是2/3*X-1 =1 
可推算出X = (1+1)*3/2
发表于 2020-05-27 16:55:03 回复(0)
lllx123头像 lllx123 
动态规划
class Solution {
private:
	vector<int> dp;
public:
	int cakeNumber(int n) {
		dp.resize(n);
		dp[n - 1] = 1;
		for (int i = n - 2; i >= 0; i--)
			dp[i] = (dp[i + 1] + 1) * 1.5;
		return dp[0];
	}
};

发表于 2020-04-18 20:28:07 回复(0)
阿尔辛多头像 阿尔辛多
这个绝对有问题，我开始设置输出为double死活都不能通过，说是一个测试是输入5得16。
我们反着看，16个蛋糕第一天就他妈除不尽啊，怎么三分之一？这个测试用例都有问题，这个题目是也有问题的我认为
要么你把用例都换成可行的整数，要么就接受double的输出
发表于 2020-03-29 04:46:01 回复(3)
卖报人头像 卖报人 
/*
从第n天开始回推，d(n-1) = (d(n)+1)*3/2
特别注意，要先乘3再除2，则符合整形取余后的结果
*/

class Solution {
public:
    /**
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    int cakeNumber(int n) {
        // write code here
        if(n == 1) {
            return 1;
        }
        int i;
        int tmp = 1;
        for(i = 2; i <= n; i++) {
            tmp = (tmp + 1)*3/2;
        }
        return tmp;
    }
};

编辑于 2020-03-16 14:30:23 回复(0)
Java
世界杯2009头像 世界杯2009 
public int cakeNumber(int n) {
    // write code here
    int start = 1;
    for (int i = n - 1; i > 0; i--) {
        // x - (n/3+1) = y
        // x - x/3 - 1 = y
        // 2/3x = y + 1
        // x = (y + 1) * 3 / 2
        start = (start + 1) * 3 / 2;
    }
    return start;
}

发表于 2021-10-16 18:30:18 回复(0)
Python 3
ZhongHaoWang头像 ZhongHaoWang 
class Solution:
    def cakeNumber(self , n ):
        # write code here
        # 每次加1为当前的2/3
        cur = 1
        
        while n - 1:
            cur += 1
            if not cur & 1:
                cur = cur // 2 * 3
            else:
                cur = (cur - 1) // 2 * 3 + 1
            n -= 1
        return cur

发表于 2021-08-28 12:18:40 回复(0)
Python
牛客717689322号头像 牛客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)
牛客351868423号头像 牛客351868423号
确实是有多组解，思路如下：
假设第n天有X(n)=3i+j个蛋糕（j=0,1,2）
那么第n+1天就只剩下X(n+1)=2i+j-1个蛋糕
假设j=1时：
X(n+1)=2i，为偶数，所以可以推出当某一天剩下的蛋糕为偶数，则前一天的j必定为1，所以前一天的蛋糕数是固定的,X(n)=X(n+1)/2*3.
假设j=0时：
X(n+1)=2i-1,可以推出前一天的蛋糕数为X(n)=( X(n+1)+1 )/2*3 + 0;
假设j=2时：
X(n+1)=2i+1,可以推出前一天的蛋糕数为X(n)=( X(n+1)-1 )/2*3 + 2;
综合假设j=0和j=2的情况：可以发现当某一天蛋糕为奇数时：我们只能推断出，可能的两种情况，并不能确定前一天到底有多少蛋糕。

发表于 2021-03-21 16:43:08 回复(0)
灰头小聪头像 灰头小聪
#include <stdio.h>

int main()
{ void cakeNumber(int n);
    int n;
     scanf("%d",&n);
     cakeNumber(n);}
     void cakeNumber(int n) {
        int i,sum;
        sum=1,i=1;
        while(i<n){
            sum=(int)3*(sum+1)/2;
            i++;}
        printf("%d",sum);
     }

发表于 2021-01-01 21:27:46 回复(0)
Python
角三落头像 角三落
cake[0] = 1
cake[i] - cake[i]//3 -1 = cake[i-1]

发表于 2020-11-10 15:50:01 回复(0)
Aliceye头像 Aliceye 
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    def cakeNumber(self , n ):
        # f(x)=f(x-1)+1/3*f(x-1)-1=2/3*f(x-1)-1
        # f(1) = 1
        # f(2) = 3
        # f(n) = (f(n-1)+1)*3/2
        f=[0 for i in range(n+1)]
        f[0] = 0
        f[1] = 1
        for i in range(2,n+1):
            f[i] = int(f[i-1]+1)*3/2
        return f[n]

发表于 2020-10-21 10:37:08 回复(0)
RyuAsuka头像 RyuAsuka 
    int cakeNumber(int n) {
        if (n == 1)
            return 1;
        return (int)ceil(3*(cakeNumber(n - 1) + 1) / 2);
    }
本质上是 
编辑于 2020-09-20 20:26:15 回复(0)
高级CV开发工程师头像 高级CV开发工程师
这道题怎么感觉有问题？答案不唯一？第二天蛋糕为3的话，第三天蛋糕数可以为5也可以为6吧？5 - 5/3 - 1 也等于3吧
发表于 2020-09-10 15:46:46 回复(0)
张无衣头像 张无衣
这么喜欢吃蛋糕，不如叫猪妹好了
发表于 2020-09-03 14:33:13 回复(0)
mawy610头像 mawy610
这道题本质上是一道高中数学的数列题，递推公式是a[i+1] = (2a[i] - 3) / 3，已知a[n] = 1，求a[1]
反过来，则是已知a[1] = 1, a[i+1] = (3a[i] + 3) / 2，求a[n]，由于是计算机（终于不用苦逼地求通项公式了），可以直接无脑循环
当然，也可以直接用换元法求出通项公式：a[i] = (3/2)^i - 3
发表于 2020-08-22 07:44:10 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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