首页 > 试题广场 >

吃糖果

[编程题]吃糖果

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

名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。现在给定N，请你写程序求出名名吃巧克力的方案数目。

输入描述:

输入只有1行，即整数N。

输出描述:

可能有多组测试数据，对于每组数据，
输出只有1行，即名名吃巧克力的方案数。

示例1

输入

输出

算法知识视频讲解

C/C++

咖喱的cuy

直接暴力dfs穷举

using namespace std;

int N, solution;

void dfs(int rem, int eat){
    if(rem < eat){
        return;
    }
    if(rem == eat){
        solution++;
        return;
    }
    dfs(rem - eat, 1);
    dfs(rem - eat, 2);
}

int main(){
    while(cin >> N){
        solution = 0;
        dfs(N, 0);
        cout << solution << endl;
    }
    return 0;
}

发表于 2019-03-13 16:14:47 回复(2)

Python

TimeMac

递归法

def findPlan(num):
    if num <= 3:
        return num
    return findPlan(num-1) + findPlan(num-2)
try:
    while True:
        num = int(input())
        print(findPlan(num))
except Exception:
    pass

编辑于 2018-10-04 11:45:39 回复(0)

viod

//分析可知规律等同于斐波那契数列

#include<stdio.h>
int main(){
    int i = 0,n,f1=1,f2=2,fabri;
    while(~scanf("%d",&n)){
        if(n==1){
            printf("1\n");
            break;
        }
         if(n==2){
            printf("2\n");
            break;
        }
        else 
        {
           for(i=n;i>2;i--){
               fabri=f1+f2;
               f1=f2;
               f2=fabri;
           }
            printf("%d\n",fabri);
        }
    }
}

发表于 2021-12-26 22:22:48 回复(0)

梦回与君同

#include <iostream>
using namespace std;
int main(){
    int fab[20] = {1,1},n;
    for(n = 2;n<20;++n)
        fab[n] = fab[n-1]+fab[n-2];
    while(cin >> n)
        cout << fab[n] << endl;
    return 0;
}

编辑于 2021-01-26 19:56:05 回复(0)

漫漫云天自翱翔

入门DP

#include<iostream>
(720)#include<cstring>
#include<algorithm>
(831)#include<cstdio>
using namespace std;
int main()
{
    int n;
    int dp[25];
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<25;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    while(cin>>n){
        cout<<dp[n]<<endl;

    }
    return 0;
 }

发表于 2020-04-13 09:47:30 回复(0)

C/C++

YhX.

//N=1 1种  N=2  2种   N=3  3种  N=4  5种 a[N]=a[N-1]+a[N-2]
#include<stdio.h>//找规律问题
int main()
{
    int n,a[20],i;
    a[1]=1;a[2]=2;
    scanf("%d",&n);
    for(i=3;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    printf("%d\n",a[n]);
}

发表于 2020-04-01 21:01:49 回复(0)

Java

LHC0512

Java解法，动态规划

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] record =new int[21];
        record[1]=1;
        record[2]=2;
        for (int i = 3; i <= n; i++) {
            record[i]=record[i-1]+record[i-2];
        }
        System.out.println(record[n]);
    }
}

发表于 2020-03-06 10:22:29 回复(0)

Java

JXhacker

递归方法，三行代码

private static int eatChocolate(int N) {
        if (N == 1) return 1;
        if (N == 2) return 2;
        return eatChocolate(N - 1) + eatChocolate(N - 2);
    }

编辑于 2019-04-20 10:50:04 回复(0)

度小满首席推荐官

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int manage(int k){
    if(k == 1)
        return 1;
    else if(k == 2)
        return 2;
    return manage(k-1)+manage(k-2);
}
int main(){
    int k;
    cin>>k;
    int sum;
    sum = manage(k);
    cout<<sum;
    return 0;
}

发表于 2019-03-01 15:05:40 回复(1)

小陈也只是想要一个实习罢了

感觉就是斐波那契的变型啊hhh，看出递归规律就很好做了

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int* candy=new int[n+1];
    candy[1]=1;
    candy[2]=2;
    for(int i=3;i<=n;i++)
        candy[i]=candy[i-1]+candy[i-2];
    cout<<candy[n]<<endl;
}

发表于 2019-02-07 16:31:28 回复(1)

hestyle

#include<iostream>
using namespace std;
int function(int n)
{
    if(n == 0)//终止条件一
        return 1;
    else if(n < 0)//终止条件二
        return 0;
    else
        return function(n - 2) + function(n - 1);//每天只有吃一块或者两块这两种方法
        
}
int main()
{
    int n;
    int cnt;
    cin >> n;
    cnt = function(n);
    cout << cnt << endl;
    return 0;
}

递归法

每天只有吃一块或者两块这两种方法，所以function（n）= function（n - 1） + function（n - 2）

递归的终止条件是形参n <= 0, n == 0则这种方法合理，return 1； n < 0 则这种方法不合理 return 0

发表于 2018-09-22 21:05:59 回复(0)

一个小太阳

#include <iostream>  
using namespace std;  
int digui(int n);
int main(int argc, const char * argv[])  
{
	int N;
	while(cin>>N)
	{
		cout<<digui(N)<<endl;
	}
}
int digui(int n)
{
	if(n==1) return 1;
	if(n==2) return 2;
	else return digui(n-1)+digui(n-2);
}

发表于 2017-05-16 23:04:49 回复(0)

kestars

#include<stdio.h>


int getCount(int n){
    if(n==1)
        return 1;
    if(n==2)
        return 2;
    return getCount(n-1)+getCount(n-2);
}

int main(){
    int N;
    while(scanf("%d",&N)!=EOF){
		printf("%d\n",getCount(N));	        
    }
    return 0;
}

发表于 2016-10-25 23:10:32 回复(0)

263保洁小妹

动态规划问题。最后一天可以吃两块，也可以吃一块。所以dp(n)=dp(n-1)+dp(n-2)

#include <stdio.h>

int dp(int n)
{
    if(n==1) return 1;
    else if(n==2) return 2;
    else return dp(n-2)+dp(n-1);
}

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        printf("%d\n", dp(n));
    }
    return 0;
}

发表于 2018-02-22 10:47:24 回复(11)

C/C++

_stormpang

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 21;

int num[maxn];

int main()
{
    num[1] = 1;
    num[2] = 2;
    for(int i = 3; i < maxn; ++i)
    {
        num[i] = num[i-1]+num[i-2];
    }

    int n;
    while(cin >> n)
    {
        cout << num[n] << endl;
    }
    return 0;
}

发表于 2016-08-09 17:36:47 回复(1)

灰的咩

大家用动态规划比较多，我一开始也打算用，但是在分析动态规划的过程中发现了规律，觉得可以直接算某一行，不需要用动态规划。主要的思路就是和高中学的排列组合一样，应为至少每天吃一块，所以就在总天数里选出吃两块的组合数就可以了。例如4块巧克力，[2,4]天吃完，两天的话就是c(2,2),三天是c(3,1),四天是 c(4,0)，加起来就是总共的方案数5。select函数就是实现了一下组合数的计算。代码如下：

#include<stdio.h>
int select(int a,int b){
    if(b==0){
        return 1;
    }
    int result,temp1=1,temp2=1;
    int i;
    for(i = a; i > a-b; i--){
        temp1 *= i;
    }
    for(i = b; i>0; i--){
        temp2 *= i;
    }
    result = temp1/temp2;
    return result;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int b[20] = {0};
        if(n%2==0){
            for(int i = n/2; i <= n; i++){
                b[i] = select(i, n-i);
            }
        }else{
            for(int i = n/2+1; i<=n; i++){
                b[i] = select(i, n-i);
            }
        }
        int sum = 0;
        for(int i = 0; i <= n; i++){
            sum += b[i];
        }
        printf("%d\n", sum);
    }
    return 0;
}

发表于 2019-08-16 20:33:24 回复(1)

C/C++

算法小屁孩

#include<bits/stdc++.h>
int num(int n){ 
    if(n<=1)
        return 1;
    else
        return num(n-1)+num(n-2);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF)
        printf("%d",num(n));
    return 0;
}

编辑于 2019-03-02 11:29:21 回复(0)

Python

华科平凡

跳台阶问题变种。

days, res = int(input()), [1, 2]
for i in range(days):
    res.append(res[-1] + res[-2])
print(res[days - 1])

编辑于 2018-04-01 09:23:43 回复(0)

Python

红尘梦断都城

#数列是：1,2,3,5,8,13
#发现后一个数是前两项之和，递归
def f(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return f(n-1)+f(n-2)
while 1:
    try:
        n=int(input())
        print(f(n))
    except:
        break

发表于 2017-09-04 20:55:21 回复(0)

C++

别样的人儿

#include <iostream>
using namespace std;

// 动态规划吃糖果
int dp(int n) { // 返回吃巧克力的方案数目
    if (n == 1) // 只有一块巧克力的情况
        return 1;
    if (n == 2) // 只有两块巧克力的情况
        return 2;
    /*
    吃n块巧克力的方案数=最后一次是吃一块巧克力的方案数+最后一次是吃两块巧克力的方案数
                      =吃n-1块巧克力的方案数+吃n-2块巧克力的方案数
    */
    return dp(n - 1) + dp(n - 2);
}

int main() {
    int n;
    while (cin >> n) {
        cout << dp(n);
    }
}

发表于 2023-03-22 20:33:40 回复(0)