龚秋志


私信TA

用户名:uq_48078956563

访问量:15907

签 名:

又回来看了一眼

等  级
排  名 41
经  验 10280
参赛次数 29
文章发表 62
年  龄 19
在职情况 学生
学  校 湖北生物科技职业学院
专  业 计算机应用

  自我简介:

解题思路:

        第n年的母牛的来源分别来自于前一年剩下的和往前推3年的母牛(能生的母牛,最早的也算在里面)

       

第一年
第二年
第三年
第四年
第五年
第六年
1
2
3
4

4(第四年)+2(第二年)=6

f(5-1) + f(5-3) = 6

f(4) + f(2) = 6

6(第五年)+3(第三年)=9

f(6-1) + f(6-3) = 9

f(5) + f(3) = 9

    

        6 = 前一年剩下的4头牛+(第2年新产的母牛刚具有生育能力生下的1头+最早的母牛1头)

        解题公式:f(n) = f(n-1) + f(n-3)

注意事项:


解法1 递归

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
        
    }
    
    public static int f(int n){
        //前四天没有母牛出生
        if(n<=4){
            return n;
        }
        //上一天出生数加前三天的出生数
        return f(n-1)+f(n-3);
    }
    
}

解法2 记忆型递归+剪枝  避免计算重复子问题

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
        
    }
    
    public static Integer[] arr = new Integer[999];
    
    public static int f(int n){ 
        //前四天没有母牛出生       
        if(n<=4){
            arr[n]=n;
            return n;
        }
        //剪枝避免计算重复子问题
        if(arr[n]!=null){
            return arr[n];
        }
        //记住存储结果 以便复用
        arr[n]=f(n-1)+f(n-3);        
        return arr[n];
    }
}

解法3 动态规划

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int [] arr = new int[999];
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            for(int i = 1;i <= n;i++ ){
                //前四天没有母牛出生    
                if(i<=4){
                    arr[i]=i;
                }else{
                    arr[i]=arr[i-1]+arr[i-3];
                }
            }
            System.out.println(arr[n]);
        }
        
    }
    
}


 

0.0分

6 人评分

  评论区

#include<stdio.h>
int main()
{
    int i,n[60],m,a;
    for(i=0;i<60;i++)
    {
    scanf("%d",&n[i]);
    if(n[i]==0)break;
    }
    for(i=0;n[i]!=0;i++)
    {if(n[i]<=4)
    printf("%d\n",n[i]);
    else
    {a=n[i]-4;
    for(m=0;a>0;a--)
    m=m+n[i]+a;
    printf("%d\n",m);
    }}
    return 0;
}
为什么提交后显示错误啊!
2022-01-15 13:38:54 | |
  • «
  • 1
  • »