首页 > 试题广场 >

养兔子

[编程题]养兔子

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

一只成熟的兔子每天能产下一胎兔子。每只小兔子的成熟期是一天。某人领养了一只小兔子，请问第N天以后，他将会得到多少只兔子。

输入描述:

测试数据包括多组，每组一行，为整数n(1≤n≤90)。

输出描述:

对应输出第n天有几只兔子(假设没有兔子死亡现象)。

示例1

输入

1<br/>2

输出

1<br/>2

算法知识视频讲解

Python

华科平凡

python solution:

while True:
    try:
        a, res = int(input()), [1, 2]
        while len(res) < a:
            res.append(res[-1] + res[-2])
        print(res[a - 1])
    except:
        break

发表于 2017-10-10 21:01:48 回复(0)

请别叫我河神

/*
对于这样的题目主要是抓住递推式的关系。
我对于F(n)=F(n-1)+1*F(n-2)的公式理解是这样的。F(n-1)代表昨天的兔子总量。
F(n-2)代表前天的兔子总量，刚好只有前天的兔子具有生产能力。
所以如果题目改成一只成熟的兔子能够生产2只，那么通项公式为F(n)=F(n-1)+2*F(n-2)
 
先预处理一个数组，这样对于多组测试数据就可以节约一点时间。
*/
#include<stdio.h>
int main()
{
	__int64 a[95]={1,2};
	int n,i;
	for(i=2;i<91;i++)
		a[i]=a[i-1]+a[i-2];
	while(scanf("%d",&n)!=EOF)
	{
		printf("%I64d\n",a[n-1]);
	}
	return 0;
}

发表于 2017-05-12 15:44:35 回复(0)

书生牛犊

#include <stdlib.h>
#include <stdio.h>
int main(){
int n;
long long a[91];
a[1]=1;
a[2]=2;
int min=2;
while((scanf("%d",&n))!=EOF){
		if(n>min){//动态扩展，根据输入数据的值动态扩展数据，没用到的大数据就不计算了，而每一次调用过后又将把数据保存下来，下次需要的数据就不必重新计算了。
			for(int i=min+1;i<=n;i++){
				a[i]=a[i-1]+a[i-2];
			}
                    min=n;
		}
		printf("%lld\n",a[n]);
	}







return 0;
}

编辑于 2017-12-28 20:04:39 回复(3)

C/C++

小周好饿

// write your code here cpp   斐波那契数列
#include<iostream>
using namespace std;
int main()
{
    int n=0;
    long arr[91]={1,1};
    for(int i=2;i<91;i++)
        arr[i]=arr[i-1]+arr[i-2];
    while(cin>>n){
        cout<<arr[n]<<endl;
    }
    return 0;
}

发表于 2020-03-07 17:09:22 回复(0)

我不是董皓宇。

斐波那契数列

奇安信笔试题扩展：假设兔子在第五天开始每天生两个小兔子

哪位哥哥姐姐解答一下~📌

int main()
{
    vector<long> v(91, 1);
    v[1] = 1;
    for(int i = 2; i < v.size(); i++)
        v[i] = v[i-1] + v[i-2];
    int n;
    while(cin>>n)
        cout<<v[n]<<endl;
    return 0;
}

编辑于 2020-03-06 14:55:38 回复(2)

JIEs201803180115154

a=1
b=1

for i in range(90):
print (b)
a,b=b,a+b

编辑于 2019-03-21 00:54:54 回复(0)

kestars

import java.math.BigInteger;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            BigInteger oldRabbit=new BigInteger("1");
            BigInteger newRabbit=new BigInteger("0");
            for(int i=0;i<n-1;i++){
                BigInteger temp=newRabbit;
                newRabbit=oldRabbit;
                oldRabbit=oldRabbit.add(temp);
            }
            System.out.println(oldRabbit.add(newRabbit));
        }
    }
}

发表于 2018-09-29 18:16:40 回复(0)

Java

Mr.Husky

//就是斐波那契数列
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            
            long[] arr = new long[91];
            arr[1] = 1;
            arr[2] = 2;
            for(int i = 3;i < arr.length;i++){
                arr[i] = arr[i-1] + arr[i-2]; 
            }
            System.out.println(arr[n]);
        }
    }
}

发表于 2017-10-05 22:08:21 回复(1)

Java

牛客8596300号

兔子是哺乳动物，领一只兔子，生个毛线啊

发表于 2018-01-25 16:31:21 回复(4)

C/C++

WZ_Dale

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

发表于 2020-08-21 09:55:20 回复(0)

未见花闻

// write your code here

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            long f0 = 1;
            long f1 = 1;
            //斐波拉契数列 f[i]=f[i-1]+f[i-2]
            long f = 1;
            while (n - 1 > 0) {
                f = f0 + f1;
                f0 = f1;
                f1 = f;
                n--;
            }
            System.out.println(f);
        }
    }
}

发表于 2022-10-01 15:22:40 回复(0)

爱干饭的猿

想问一下，为什么每次用动态规划（类似的题也是） new long[n + 1]都会越界，而大家也都直接new long[91]，

所有我new long[n + 2]；

import java.util.Scanner;

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

发表于 2022-06-02 18:02:20 回复(1)

Java

来学习的小张

import java.util.*;
public class Main{
    public static long[] arr = new long[91];
    
    public static void fun(){
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 0;
        for(int i = 2;i < arr.length;i++){
            arr[i] = arr[i - 1] +arr[ i - 2];
        }
    }
   // public static void main(String[] args){
   //     Scanner sc = new Scanner(System.in);
   //     while(sc.hasNext()){
   //         int n = sc.nextInt();
    //        fun();
    //        System.out.println(arr[n]);
   //     }
  //  }
    
    
    
    //方法二：
    
     public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            long f0 = 1;
            long f1 = 1;
            long f2 = 1;
            for(int i = 2;i <= n;i++){
                f2 = f1 +f0;
                f0 = f1;
                f1 = f2;
            }
            System.out.println(f2);
        }
    }
}

编辑于 2022-05-18 16:02:58 回复(0)

txy_钟琛

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner =  new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            long ans = Fibnaqi(n);
            System.out.println(ans);
        }
    }
    public static long Fibnaqi(int n){
        if(n == 1 || n == 2){
            return n;
        }
        long ans = 0;
        long a = 1;
        long b = 2;
        while(n > 2){
            ans = a + b;
            a = b;
            b = ans;
            n--;
        }
        return ans;
    }
}

发表于 2022-03-31 22:43:11 回复(0)

C/C++

AlbatrossLy

// 本质：斐波那契数列的考察
// 注意数据类型long long

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

int main()
{
    int n;
    while(cin >> n)
    {
        vector<long long> v(91, 0);
        v[1] = 1;
        v[2] = 2;
        for(int i = 3; i < 92; i++)
            v[i] = v[i - 2] + v[i - 1];
        cout << v[n] << endl;
    }
    
    return 0;
}

编辑于 2021-11-17 22:43:51 回复(0)

C/C++

DuXinyu

就是一个斐波那契数列的第n项的数字的问题，不过这里考的就是数据类型的大小的知识点

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

int main()
{
    vector<long> v{ 1,1,2 };
    for (int i = 3; i <= 90; i++)
        v.push_back(v[i - 1] + v[i - 2]);

    int n = 0;
    while (cin >> n)
        cout << v[n] << endl;

    return 0;
}

发表于 2020-07-24 15:40:48 回复(0)

什么都easy

刚开始递推公式不是很好想，就把前几天兔子的个数列出来，分为成熟兔子+刚生兔子，第i+1天的成熟兔子等于第i天的所有兔子，i+1天的刚生兔子等于第i天的成熟兔子即第i-1天的所有兔子，即可得出递推式。除此之外用递归会超时，用一维数组存且好

#include <iostream>
////1  1+0
////2  1+1
////3  2+1
////4  3+2
////5  5+3 
using namespace std;
int main(){
	int n;
	long long a[100];
	a[1]=1;
	a[2]=2;
	while(cin>>n){
		for(int i=3;i<=n;i++){
			a[i]=a[i-1]+a[i-2];
		}
		cout<<a[n]<<endl;
	}
}

发表于 2020-03-29 15:47:38 回复(0)

C/C++

赫菲斯托斯

//斐波那契数列

// write your code here cpp
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    vector<long> arr{1,2};
    while(cin>>n)
    {
        if(n>arr.size())
            for(int i=arr.size();i<=n;++i)
                arr.push_back(arr[arr.size()-1]+arr[arr.size()-2]);
        cout<<arr[n-1]<<endl;
    }
    return 0;
}

编辑于 2020-03-06 20:44:25 回复(0)

C/C++

不偷不抢安度因_

//Fibonacci数列
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    long long int fib[90] = {1, 2};
    while(~scanf("%d", &n))
    {
        if(fib[n-1] == 0)
        {
            for(int i = 2; i < n; i++)
            {
                fib[i] = fib[i-1] + fib[i-2];
            }
        }
        printf("%ld\n", fib[n-1]);
    }
}

一开始我直接用递归结果超时，然后就取消使用递归栈，直接用size为90的数组，每输入一个n就补充一下fib数组，然后就可以了

编辑于 2020-03-02 15:35:24 回复(0)

hestyle

时间	成熟（可繁殖）	幼年（出生）	总数
第1天	1	0	1
第2天	1	1	2
第3天	2	1	3
第4天	3	2	5
第5天	5	3	8
第6天	8	5	13

不难看出，由于兔子成熟期为1天，因此第 i - 1天的所有兔子到第 i 天全部成熟，构成第i天的成熟兔f(i-1)，现在我们来计算第i天有多少只兔子出生。

并不是第i-1天的兔子都能进行繁殖，只有第i - 1成熟的兔子才能繁殖，根据递推关系，第i - 1天的成熟兔子 == 第 i - 2天的兔子总数，因此第i天新出生的兔子数为f(i - 2).

最终得到递推关系 f(i) = f(i - 1) + f(i - 2).

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int number = 0;
    //scanf返回值为正确输出数据的变量个数，当一个变量都没有
    //获取到数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        if (number < 4) {
            //计算可知第一天1只，第2天2只，第3天3只
            printf("%d\n", number);
        } else {
            //递推第i(i ≥ 4)天的兔子f(i) = f(i - 1) + f(i - 2)
            long long before = 2, now = 3, next = 0;
            for (int i = 4; i <= number; ++i) {
                //f(i) = f(i - 1) + f(i - 2)
                next = before + now;
                //更新f(i - 2) = f(i - 1), f(i - 1) = f(i)
                before = now;
                now = next;
            }
            printf("%lld\n", now);
        }
    }
    return 0;
}

发表于 2020-03-02 09:30:46 回复(0)