首页 > 试题广场 > 统计每个月兔子的总数
[编程题]统计每个月兔子的总数
  • 热度指数:54384 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少?

 

    /**
     * 统计出兔子总数。
     * 
     * @param monthCount 第几个月
     * @return 兔子总数
     */
    public static int getTotalCount(int monthCount)
    {
        return 0;
    }

 

 


输入描述:

输入int型表示month



输出描述:

输出兔子总数int型

示例1

输入

9

输出

34
#include <iostream>
using namespace std;

int main(){
    int m;
    while(cin>>m){
        int a=1,b=0,c=0;//a:一个月兔子数,b:两个月兔子数,c:三个月兔子个数
        while(--m){//每过一个月兔子数变化
            c+=b;
            b=a;
            a=c;
        }
        cout<<a+b+c<<endl;
    }
}

发表于 2016-09-07 16:16:20 回复(29)
#include <stdio.h>

int main()
{
    ///关键是找到递推式 f(n)=f(n-1)+f(n-2) (n>=4)
    ///递推式的解释:对于第n个月的兔子数量:有两部分组成,
    ///一部分是上个月的兔子f(n-1),另一部是满足3个月大的兔子
    ///会生一只兔子f(n-2)
    int arr[100];
    int i,N;
    arr[1]=arr[2]=1;
    arr[3]=2;
    for(i=4;i<100;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    while((scanf("%d",&N))!=EOF){
        printf("%d\n",arr[N]);
    }
    return 0;
}



编辑于 2016-01-28 21:32:39 回复(16)
23ms 277k
import java.util.Scanner;
public class Main{
	
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        	int input = sc.nextInt();
        	System.out.println(Main.getNumber(input));
        	        	
        }
    }
    //通过列举出每月的有生育能力兔子的数目,没有生能力的兔子的说目,一月大的兔子的数目和二月大的兔子的数目可知
    //
    public static int getNumber(int mounth){
    	if(mounth == 1 || mounth == 2){
    		return 1;
    	}
    	int tempold = 1;
    	int tempyoung = 1;
    	int mounth1 = 1;
    	int mounth2 = 0;
    	for(int j = 4; j <= mounth; j++){
    		//第一步,第二个月的变成了有生育能力的兔子
    		tempold += mounth2;
    		//第二步,一个月大的兔子变成了两个月大的兔子
    		mounth2 = mounth1;
    		//第三步,有生育能力的兔子生出了一个月大的小兔子
    		mounth1 = tempold;
    		//当月小兔子的个数
    		tempyoung = mounth1 + mounth2;  		
    		
    	}
    	return tempold + tempyoung;
    }
}

发表于 2016-05-26 11:24:08 回复(5)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int monthCount = in.nextInt();
            System.out.println(getTotalCount(monthCount));
        }
        in.close();
    }
    
    public static int getTotalCount(int monthCount){
        if(monthCount==1 || monthCount==2){
            return 1;
        }
        
        return getTotalCount(monthCount-1)+getTotalCount(monthCount-2);
    }
}

发表于 2016-04-04 10:24:25 回复(2)
根据高赞答案添加了详细注释,包看包懂。就是可能有点啰嗦……
#include <iostream>
using namespace std;
int main()
{
    int month;
    while(cin >> month)
    {
        int shu3 = 0;//成熟了的可以生兔子的兔子数量,即成熟度是3及以上的
        int shu1 = 1;//新生的成熟度为1的兔子数量
        int shu2 = 0;//差一个月就成熟的成熟度为2的兔子数量
        
        //这里一定是--month
        //因为初始三个值已经是第一个月的数了,所以循环少一个月
        while(--month)
        {
            shu3 += shu2;//之前熟了的兔子加上两个月熟的兔子就是所有熟兔子
            shu2 = shu1;//两个月的成熟度的兔子都是新生兔子变的
            shu1 = shu3;//新生兔子都是成熟了的兔子生的
        }
        cout << shu1 + shu2 + shu3 << endl;
    }
    return 0;
}

发表于 2020-02-02 15:12:59 回复(1)

python解法如下

while True:
    try:
        a=int(input())-1
        arr=[1,2]
        while len(arr)<a:
            arr.append(arr[-1]+arr[-2])
        print(arr[-1])
    except:
        break
编辑于 2017-09-18 10:45:43 回复(2)
本质上是斐波那契数列,没什么好讲的,就是用递归来算
#include<bits/stdc++.h>
using namespace std;
int num_rabit(int month){
    int res;
    if(month==1 || month==2 )
            res=1;
    else
        res=num_rabit(month-1)+num_rabit(month-2);
    return res;
}
int main(){
    int month;
    while(cin>>month){
        
       int res=num_rabit(month);
        cout<<res<<endl;
    }
    return 0;
}

发表于 2017-12-10 22:03:11 回复(2)
#include<iostream>
using namespace std;
int getTotalCount(int month)
{
	int count;
	if (month < 3)
		count = 1;
	else
		count = getTotalCount(month - 1) + getTotalCount(month - 2);
	return count;
}
int main()
{
	int month;
	while (cin >> month)
	{
		cout << getTotalCount(month)<<endl;
	}
	return 0;
}


发表于 2017-06-17 15:45:59 回复(1)
while True:
    try:
        m = int(input())
        t1,t2 = 1,1
        for i in range(m):
            if i < 2:#前2个月都是1只兔
                res = 1
            else:#从第三个月开始,当月兔子的数量是前两个月的加和
                res = t1 + t2
                t1 = t2
                t2 = res
        print(res)
    except:
        break

发表于 2020-01-23 20:12:12 回复(0)
/*注意:题目意思是兔子第三个月就可以生小兔子,也就是经过两个月之后*/
#include<iostream>
using namespace std;
int countRabbit(int n)
{
    if(n==1 || n==2)
        return 1;
    return countRabbit(n-1)+countRabbit(n-2);
}
int main()
{
    int n;
    while(cin>>n)
    {
        int num=countRabbit(n);
        cout<<num<<endl;
 }
    return 0;
}

发表于 2016-12-18 19:33:38 回复(0)
第n个月的兔子数量由两部分组成,一部分是上个月的兔子f(n-1),另一部是满足3个月大的兔子,会生一只兔子f(n-2)。所以第n个月兔子总数: f(n) = f(n - 1) + f(n - 2)。本题是在变相考察斐波那契数列。
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int month;
    while(cin >> month){
        int a = 1;
        int b = 1;
        int count = 0;
        for(int i = 2; i < month; ++i){
            count = a + b;
            a = b;
            b = count;
        }
        cout << count << endl;
    }
    return 0;
}

发表于 2020-06-13 09:44:34 回复(0)
#    新生度1 新生度2 熟兔
#      1      0     0
#      0      1     0
#      1      0     1
#      1      1     1
#      2      1     2

def getTotalCount(n):
    new1 =1
    new2 =0
    adult=0
    for i in range(1,n):
        adult+=new2
        new2=new1
        new1=adult
    return new1+new2+adult
 
while True:
    try:
        num=int(input())
        print(getTotalCount(num))
    except:
        break
假设有三种兔子,一种是新生度为1的兔子,也就是刚活第一个月的兔子;一种是新生度为2的兔子,也就是活到第二个月的兔子;熟兔就是第三个月及以后的兔子。其中新生度为1和新生度为2没有繁育能力。每次更新,先将原来新生度为2的兔子加到熟兔里面,熟兔数量更新;再把新生度为2的兔子更新(替换)为原来新生度为1的兔子。因为熟兔可以生一个新兔子,所以用熟兔的数量更新(替换)新生度为1的兔子。往复循环,可以得到第n个月兔子的总数,就是将上述三种兔子加一起。
编辑于 2020-02-16 15:12:41 回复(2)
/**
 * 对题目的分析:
 *    每个月的兔子都分为两类:1.上个月继承下来的兔子 2.这个月有生育能力生下来的兔子(每个兔子生一个)
 *      有生育能力的兔子==两个月前的兔子数量
 *      因此假设第n个月,则第n个月的兔子数量为 f(n) = f(n-1) + f(n-2)
 *      分析完毕发现这道题是斐波那契数列的变形
 */
import java.util.Scanner;
public class Main2 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int monthCount=sc.nextInt();
            System.out.println(getTotalCount1(monthCount));
            //System.out.println(getTotalCount2(monthCount));
        }
    }
    //迭代版本
    private static int getTotalCount1(int monthCount) {
        if(monthCount==1||monthCount==2){
            return 1;
        }
        int first=1;
        int second=1;
        int sum=0;
        //从第三个月开始算起
        for(int i=2;i<monthCount;i++){
            sum=second+first;
            first=second;
            second=sum;
        }
        return sum;
    }
    //递归版本
    private static int getTotalCount2(int monthCount) {
        if(monthCount==1||monthCount==2){
            return 1;
        }
        //这里是倒着算的,不影响结果,因为算的次数是相同的
        return getTotalCount2(monthCount-1)+getTotalCount2(monthCount-2);
    }
}

编辑于 2019-12-02 17:47:27 回复(0)
import java.util.*;

public class Main {
	
	public static int get(int month){
		if(month <= 0)
			return 0;
		if(month == 1 || month == 2)
			return 1;
		else
			return get(month - 1) + get(month - 2);
	}
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	while(sc.hasNext()){
    		int month = sc.nextInt();
    		System.out.println(get(month));    		
    	}
    	sc.close();
    }     
}

发表于 2016-08-10 18:54:07 回复(0)
非递归算法,思路逻辑超级简单,如此短的代码,大家能体会有多简单了吧
import sys
for s in sys.stdin:
    m = int(s)
    k3 = 0
    k2 = 0
    k1 = 0
    for i in range(m):
        k3 = k3 + k2
        k2 = k1
        if k3==0 and k2 == 0:
            k1 = 1
        elif k3==0 and k2 == 1:
            k1 = 0
        else:
            k1 = k3
    
    print(k1+k2+k3)


发表于 2020-06-08 13:25:32 回复(1)
#include<iostream>
using namespace std;
int num(int month)
{
    
    if(month==1||month==2)
        return 1;
    else
        return num(month-1)+num(month-2);
}
int main()
{
    int month;
    while(cin>>month)
    {
        int n=num(month);
        cout<<n<<endl;
    }
    return 0;
}
发表于 2020-05-27 21:04:09 回复(0)
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();
            int[] a = new int[n];
            a[0] = 1; a[1] = 1;
      //当前月兔子的数量是前两月份兔子数量的2倍(到下下个月即当前月都会繁殖)+前一月份新增的兔子数量(这个月份兔子到下个月即当前月不会繁殖)       
            for(int i = 2; i < n; i++){
                a[i] = 2 * a[i-2] + (a[i-1] - a[i - 2]);
            }
            System.out.println(a[n-1]);
        }
    }
}

发表于 2020-04-14 11:20:25 回复(0)
#include <iostream>

using namespace std;

/*
    0	all	1	2	3
    1	1	1	0	0
    2	1	0	1	0
    3	2	1	0	1
    4	3	1	1	1
    5	5	2	1	2
    6	8	3	2	3
    7	13	5	3	5
    8	21	8	5	8
    由以上数据可以发现一个规律,3月份的 = 3月份的 + 2月份的;
    2月份的 = 1月份的; 1月份的 = 3月份的
    由此可以写出代码
*/

int main() {
    int num;
    while ( cin >> num ) {
        int sum = 0, three = 0, two = 0, one = 1;
        if ( num <= 0 ) {
            cout << ( num == 0 ? 1 : 0 ) << endl;
            continue;
        }
        while ( -- num ) {
            three += two;
            two = one;
            one = three;
        }
        cout << one + two + three << endl;
    }
    return 0;
}

发表于 2020-04-07 23:18:32 回复(0)
while True:
    try:
        a = int(input())
        f = [0 for i in range(a)]
        f[0],f[1],f[2] = 1,1,2
        for i in range(2,a):
            f[i] = f[i-1]+f[i-2]
        print(f[-1])
    except:
        break


编辑于 2020-03-05 10:59:25 回复(0)
//在纸上写一下情况,比较容易做出来
#include<iostream>
using namespace std;
int getTotalCount(int month){
    switch(month){
        case 1: return 1;
        case 2: return 1;
        case 3: return 2;
    }
    int l=1,m=0,s=1;
    for(int i=4;i<=month;i++){
        l=l+m;
        m=s;
        s=l;
    }
    return l+m+s;
}
int main(){
    int month;
    while(cin>>month){
        cout<<getTotalCount(month)<<endl;
    }
}

发表于 2020-01-06 22:20:23 回复(0)