我要招人

去企业版

首页 > 试题广场 >

兔子繁衍

[编程题]兔子繁衍

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

有一对兔子，从出生后的第五个月起每月生出一对小兔子（即满4月就开始生小兔），小兔子也会出生从第五个月起每月生一对小免子。假如兔子不会死，第n个月时，兔群有多少对兔子。

输入描述:

第n月（n为自然数，n<101）

输出描述:

第n个月时，兔子的对数（免群的兔子有多少对兔子）。

示例1

输入

输出

说明

第五个月时，有两对兔子

算法知识视频讲解

0xl1tmu2

#include<cstdio>

int main()
{
int n;
scanf("%d",&n);
long long c1 = 1,c2 = 0, c3 = 0, c4 = 0, c5 = 0;
//分年龄统计,c1到c4为不能繁殖的兔子（1-4月），c5表示当月可以繁殖的兔子
for(int i=1;i<n;i++)
{
c5 += c4;
c4 = c3;
c3 = c2;
c2 = c1;
c1 = c5;
}
printf("%ld",c1+c2+c3+c4+c5);
return 0;
}

发表于 2021-09-07 15:15:10 回复(0)

一大岐

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] dp = new long[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            if(i-4 < 0)
                dp[i] = dp[i-1];
            else
                dp[i] = dp[i-1]+dp[i-4];
        }
        System.out.println(dp[n-1]);
    }

}

发表于 2021-08-12 10:54:45 回复(0)

wallee59

JavaScript

let n = parseInt(readline());

if (n < 5) {
    print(1);
}
let arr = [1, 1, 1, 1];
for(let i = 4; i < n; i++){
    arr[i] = arr[i-4] + arr[i-1];
}
print(arr[n-1]);

发表于 2021-03-20 15:25:11 回复(2)

牛客483168324号

通过率100%。要把int改为long，否则会越界。

发表于 2021-03-20 14:35:41 回复(0)

张萝卜太可爱了

刚生下来的兔子就是1个月应该说一下吧....

发表于 2021-03-22 21:53:00 回复(0)

Python

牛客638919066号

看了评论才知道新兔子出生就算1月了

m = int(input())
r = [1, 0, 0, 0]  # [满1个月的兔子对数，满俩月的，满仨月的，满四月能生的]
for i in range(m-1):
    new = r[3]
    r[3] += r[2]
    r[2] = r[1]
    r[1] = r[0]
    r[0] = new
sum = 0
for i in r:
    sum += i
print(sum)

编辑于 2022-08-25 15:06:12 回复(0)

牛客718413958号

#include<stdio.h>

int main()
{
    double n[100]={1,1,1,1,2};
    int i,x;
scanf("%d",&x);
    for(i=5;i<=100;i++)
    {
        n[i]=n[i-4]+n[i-1];
    }
    printf("%.0f",n[x-1]);
    return 0;
}

发表于 2022-04-10 17:28:29 回复(0)

冰冰的心

import java.util.*;
public class Main {

    public static void main(String []args){
        long num=1l;

        Scanner in=new Scanner(System.in);
        int time=in.nextInt();
        long[] array=new long[time];
        if(time<=4){
            System.out.println(num);
            return;
        }
        for(int n=0;n<time&&time<100;n++){
            if(n<4){
                array[n]=1;
                continue;
            }
            num=num+array[n-4];
            array[n]=num;
        }
        System.out.println(num);
    return;
    }
}

为什么只有9例通过啊，求大神解答

发表于 2022-10-06 11:24:43 回复(0)

牛客668886414号

java思路：需要用到Bigdecimal，因为有测试案例涉及到很大的结果。用两个数组，一个维护兔子的数量，一个维护具有生育能力数组的数量。不要用递归，会超时。

import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(RabbitNum(n));
}
public static BigDecimal RabbitNum(int n){
if(n < 1){
throw new RuntimeException("wrong input");
}
BigDecimal[] nums = new BigDecimal[n+1];
BigDecimal[] adds = new BigDecimal[n+1];
for(int i = 1;i <= n;i++){
if(i <= 5){
adds[i] = new BigDecimal(i/5);
}else {
adds[i] = adds[i-1].add(adds[i-4]);
}
}
for (int i = 1;i <= n;i++){
if(i == 1){
nums[i] =new BigDecimal(1);
}else {
nums[i] = nums[i-1].add(adds[i]);
}
}
return nums[n];
}
}

发表于 2022-06-07 14:32:23 回复(0)

我想叫BruceWayne

我写的是c语言的，还是有点麻烦。主要是动态数组那里比较麻烦，后边就是分类。最坑的是数组越界的警告，后来将arr定义为n+1就好了，我忘了\0是最后一个。以及数组类型，换为longint就好

发表于 2021-03-29 18:52:15 回复(0)

C/C++

牛客231368726号

为什么的我C++代码过不去啊？输入87的时候，同样的思路java都可以

int n;
	cin >> n;   //87   596331286321
	long long flag[4]{0,0,0,0};	
	flag[0] = 1;
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		long t = flag[3];
		flag[3] = flag[2];
		flag[2] = flag[1];
		flag[1] = flag[0];
		
		if (i >= 5) {
			flag[1] = ans;
		}
		else {
			flag[0] = ans;
		}
		ans += t;
	}
	for (int i = 0; i < 4; i++) {
		ans += flag[i];
	}
	cout << ans << endl;

发表于 2021-03-23 21:07:43 回复(0)

国宾山城乐堡

动态规划

import java.util.*;
// 20
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if(n<4){
            System.out.print(1);
        }
        long[]dp=new long[n];
        dp[0]=1;
        dp[1]=1;
        dp[2]=1;
        dp[3]=1;
        for(int i=4;i<n;i++){
            dp[i]=dp[i-4]+dp[i-1];
        }
        System.out.print( dp[n-1]);
    }
}

发表于 2021-03-23 11:08:08 回复(0)

None201909231852369

我的思路是，创建4个笼子，用于存放未成熟的的兔子。每个笼子每隔四个月取出一次，加入到成熟的兔子群中进行繁殖。

#include<iostream>
using namespace std;
 
int main()
{
  long n,r=1,young[4]={0,0,0,0};
  cin>>n;//输入月份
  n=n-4;
  if(n<0){//月份少于5个月直接返回1
    cout<<r<<endl;
    return 0;
  }
   
  for(int i=0,count=0;i<n;i++)  //count为笼子编号
  {
    if(count>=4)count=0;//返回一号笼子
    if(young[count]!=0)  
    {
//取出已经成熟的兔子
        r=young[count]+r;
        young[count]=0;
    }
     
    young[count]=r;//把新繁殖出来的兔子放入笼子
    count++;
     
  }
  for(int i=0;i<4;i++)
  {
    r=r+young[i];
  }
   
  cout<<r<<endl;
 
return 0;
}

发表于 2021-03-22 19:10:10 回复(1)