首页 > 试题广场 >

统计每个月兔子的总数

[编程题]统计每个月兔子的总数

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

有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。

例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。

一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？

数据范围：输入满足 $1 \le n \le 31 \$

输入描述:

输入一个int型整数表示第n个月

输出描述:

输出对应的兔子总数

示例1

输入

输出

算法知识视频讲解

Java

黄磊_HL

思想：生的不是兔子而是生兔子的工厂，递归调用生兔子工厂

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int month = in.nextInt();
        int rbbits = 1;

        System.out.println(birth(rbbits,month));
    }

    public static int birth(int rabbits,int month){
        for(int i = 0; i <= month ;i++){
            if(i>2){
                rabbits += birth(1,month-i+1);
            }
        }
        return rabbits;
    }
}

发表于今天 00:11:02 回复(0)

Java

无梦0

晋升一下，最大的为3：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int len = in.nextInt();
        Map<Integer, Integer> map = new HashMap();
        map.put(1, 1);
        map.put(2, 0);
        map.put(3, 0);
        for (int i = 1 ; i < len; i++) {
            int old2 = map.get(2);
            map.put(2, map.get(1));
            map.put(1, map.get(3) + old2);
            map.put(3, map.get(3) + old2);
        }
        int re = 0;
        for (int key : map.keySet()) {
            re += map.get(key);
        }
        System.out.print(re);

    }
}

编辑于 2024-04-07 18:36:14 回复(0)

Java

_撅腚的鸭子_

import java.util.Scanner;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));        
        int n = Integer.parseInt(reader.readLine());
        int smallrabbit = 1;
        int middlerabbit = 0;
        int bigrabbit = 0;
        for(int i = 1;i < n;i++){
            bigrabbit += middlerabbit;
            middlerabbit = smallrabbit;
            smallrabbit = bigrabbit;
        }
        System.out.print(smallrabbit + middlerabbit + bigrabbit);        
    }
}

编辑于 2024-03-20 17:08:01 回复(0)

Java

山里灵活的狗123

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // Attention difference between hasNext and hasNextLine
        //一看就知道是 斐波那契数列
        // 1 2 3 4 5 6 月份
        // 1 1 2 3 5 8 数量
        // A(n)=A(n-1) + A (n-2)
        //矩阵表达 ；
        // |A(n)   |   == | 1  1 |  ** | A(n-1) | ==| 1 1| ^^ (n-1) ** | A(1) = 1|
        // |A(n-1) |   == | 1  0 |  ** | A(n-2) | ==| 1 0|          ** | A(0) = 0|
        int[][] M = {{1, 1}, {1, 0}};

        int[][] res = {{1, 0}, {0, 1}};
        int t = n - 1;
        while (t > 0) {
            if ((t & 1) == 1) {
                res = matrixMul(res, M);
            }
            M = matrixMul(M, M);
            t >>>= 1;
        }
        System.out.println(res[0][0]);


    }

    private static int[][] matrixMul(int[][] m1, int[][] m2) {
        int[][] res = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = m1[i][0] * m2[0][j] + m1[i][1] * m2[1][j];
            }
        }
        return res;
    }
}

发表于 2024-03-20 07:26:16 回复(0)

Java

老师我太想进步溜

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();
            System.out.println(dp(n));
        }
    }
    public static int dp(int n) {
        int num[] = new int[n];
        num[0] = 1;
        num[1] = 1;
        for (int i = 2; i < n; i++) {
            num[i] = num[i - 1] + num[i - 2];
        }
        return  num[n-1];
    }
}

发表于 2024-03-09 19:47:31 回复(0)

Java

今生能进大厂吗

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();//5
            //1  2  3   4   5   6
            //1  1  2   3   5   8
            int res = 1;
            List<Integer> arr= new ArrayList();//记录每个月的兔子数
            arr.add(1);//第一天
            if (num > 2) {
                for (int i = 1; i < num - 1; i++) {
                    arr.add(res);
                    res = arr.get(i-1) + res;
                   
                }
            } else {
                System.out.println(1);
            }
            System.out.println(res);
        }
    }
}

发表于 2024-01-04 18:14:50 回复(0)

Java

看我头像帅不帅

月份： 1 2 3 4 5 6 ... n

该月总兔数：1 1 2 3 5 7 ... f(n)

记第n月该月总兔数为f(n)

以第6月为例，4月份的兔子就可以下崽（题意可知），所以所有4月份的兔子就会变成double，而5月份的兔子减去4月份的兔子就是不能下崽的兔子总数：

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

=f(4)+f(5)

同理可知：

f(n)=f(n-2)+f(n-1)

由f(n)的推到公式可知：f(n)为n前两个数的f()相加可得，可简化为斐波那契数列求f(n)的值（动态规划入门题）

1.初始化数组a[0]=a[1]=1;

2.递推公式：a[i] = a[i - 1] + a[i - 2];

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[] a = new int[n];

a[0] = a[1] = 1;

for (int i = 2; i < n; i++) {

a[i] = a[i - 1] + a[i - 2];

}

System.out.println(a[n - 1]);

}

发表于 2023-10-21 17:58:25 回复(1)

Java

风的糖果

当k=3时候：k3=2, 以后的每个月都满足公式 k3=k3+k2(更新后的k2)

k2=0, => k2=k1

k1=1 k1=k3

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

if(a <=2){

System.out.print(1);

break;

}

int result=1;

int k1=0;

int k2=0;

int k3=0;

for(int i=3;i<=a;i++){

if(i==3){

k1=1;

k2=0;

k3=2;

}else{

int k33 = k3;

k2=k1;

k1=k33;

k3=k3+k2;

}

System.out.print(k3);

}

发表于 2023-09-20 17:10:42 回复(0)

Java

墨未浓

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int months = in.nextInt();
//定义一个容器，记录1,2和 3月以上的兔子数量
int[] r = new int[3];
//初始时候只有一只一月的兔子
r[0]=1;

        while(months>0){
            int orgOne = r[0];
            int orgTwo = r[1];
            int orgThr = r[2];

            if(orgOne>0){
                //如果有一月份的数据 ，全量递增到二月份
                r[0]-=orgOne;
                r[1]+=orgOne;
            }

            //如果二月份之前有数据 ，全量递增到三月份
            if(orgTwo>0){
                r[1]-=orgTwo;
                r[2]+=orgTwo;
            }

            //如果三月份有数据，全量新增到一月
            if(orgThr>0){
                r[0]+=r[2];
            }
            months--;
        }

        System.out.println(r[0]+r[1]+r[2]);
    }
}

}

发表于 2023-08-16 09:38:36 回复(0)

Java

牛客106397800号

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = Integer.parseInt(line);

        /**
         * 1 2 3 4 5 6 7
         * 1 1 2 3 5
         */
        System.out.println(rabbit(n));

    }

    /**
     * 斐波那契数列，递归思想
     *
     * @param n
     * @return
     */
    private static int rabbit(int n) {
        if (n <= 2) {
            return 1;
        } else {
            return rabbit(n - 1) + rabbit(n - 2);
        }
    }
}

发表于 2023-08-09 10:16:35 回复(0)

Java

浓眉大眼11

找规律，一二月都是只有一只，从第三个月开始，数量等于前两个月的数量相加

发表于 2023-06-08 16:10:11 回复(0)

Java

梁山教父

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int month=in.nextInt();
        int arr[]=new int[]{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269};
        System.out.print(arr[month-1]);
    }
}

发表于 2023-05-28 10:52:00 回复(1)

Java

我姓郭我信过

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

System.out.println(f(a));

}

public static int f(int n){

int source = 0;

if(n < 2) {

source = n;

}else{

source = f(n-1) + f(n-2);

}

return source;

}

发表于 2023-05-06 10:20:08 回复(0)

Java

牛客604637229号

public static int dp(int n){

if(n<3){

n=1;

}

if(n==3){

return 2;

}

if(n==4){

return 3;

}

return dp(n-2)+dp(n-1);

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

System.out.println(dp(a));

}

发表于 2023-04-21 00:34:37 回复(0)

Java

牛客875622066号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int month = in.nextInt();

int num[] = new int[month];

if(month == 1) {

System.out.print(1);

}else if(month == 2) {

System.out.print(1);

}else {

num[0] = 1;

num[1] = 1;

for (int i = 2; i < month; i++) {

num[i] = num[i-1] + num[i-2];

}

System.out.print(num[month-1]);

}

发表于 2023-03-29 16:50:26 回复(0)

Java

周中梁

//模拟解法 
   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        //将兔子分为三类，出生第一个月为baby、第二个月为teen、第三个月adult
        int baby = 1;
        int teen = 0;
        int adult = 0;

        for(int i = 2; i <= n; i++){
            //来到第i个月，给兔子们加一岁（月岁）,重新计算每个阶段的兔子数
            adult = adult + teen;//teen成年
            teen = baby;//baby成为新的teen
            baby = adult;//每只成年兔子生一直baby
        }

       System.out.println(adult + teen + baby);
    }

发表于 2023-03-17 16:45:11 回复(1)

Java

无敌壮壮

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(s.readLine()),a=0,sum=1,i=0;
        for(int j=0;j<n-1;j++){
            a=i;
            i=sum;
            sum=sum+a;
        }
        System.out.println(sum);
    }
}

发表于 2023-01-20 23:52:46 回复(1)

Java

胆小的话题终结者开挂了

``` java

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextInt()) {

int a = in.nextInt();

// 我们发现计算当月兔子数量只需要用到上个月和上上个月的数据，所以只请求3个int长度的数组即可

int[] ans = new int[]{1,1,2};

for (int i = 3; i < a; i++) {

ans[i % 3] = ans[(i - 2) % 3] + ans[(i - 1) % 3];

}

System.out.println(ans[(a - 1) % 3]);

}

```

发表于 2022-12-28 00:21:43 回复(0)

Java

RunnIng51

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int month = sc.nextInt();
        if (month == 1 || month == 2) {
            System.out.println(1);
        }
        int count = 0;
        int i=1,j=0,k=0,l,m,n;
        while (month > 2) {
            l = i+j;
            m = k;
            n = i+j;
            count = l + m +n;
            i = l;
            j = m;
            k = n;
            month--;
        }
        System.out.println(count);
    }
}

发表于 2022-11-04 21:00:38 回复(0)