年轻母牛的故事

布满荆棘的人生 2023-02-23 10:55 18阅读 0赞

#### 题目是这样的： ####

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

##### 输入 #####

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。  
n=0表示输入数据的结束，不做处理。

##### 输出 #####

对于每个测试实例，输出在第n年的时候母牛的数量。  
每个输出占一行。

--------------------

题目非常简洁，不知道是不是歪果仁想的题，我猜它的英文版是这样的：

There is a cow, which gives birth to a heifer at the beginning of each year. Each heifer starts from the fourth year, and a heifer is also born at the beginning of each year. Please program how many cows are there in the nth year?

母牛特别能生，4年就发育成熟，就能生！问第几年有多少头母牛？哎呀，对于一个刚入门的新手来说，要想解决这个题，确实很费劲了(很烧脑)！只能感叹：这公牛的后宫不久就壮大了！牛批！而老手一眼看穿规律，就有了思路。那么老手是怎么看穿的呢？

从数学角度看，这个母牛数目增长还是有一定的规律的，所以我们需要把每一年的母牛的数目清点一下，这个时候，数学基础就暴露出来了，第几年多少头牛都点不清，这还是小学问题，就是个点数题！注意题目描述！

> 第一年：1头
> 
> 第二年：2头
> 
> 第三年：3头
> 
> 第四年：4头
> 
> 第五年：6头
> 
> 第六年：9头

OK，我相信你数学非常好，很快就能发现规律。归结为一个数学题：设第n年的母牛头数为a\[n\]，则可以得出一个·递推公式：

> a\[n\] = a\[n-1\] + a\[n-3\]；

可以验证一波，没问题了就可以撸代码了，这里提供了java和c++版的代码题解，如果测试出现翻车概不负责！请注意！

Java版(我写的)：

import java.util.Scanner;
    
    public class Main{
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int[] a = new int[60];
            a[0] = 0;
            a[1] = 1;
            a[2] = 2;
            a[3] = 3;
            a[4] = 4;
            for(int i=5;i<=55;i++){
                a[i] = a[i-3] + a[i-1]; //递推填充数组
            }
            while (scanner.hasNextInt()) {      //等待输入
                int num = scanner.nextInt();
                if(num==0){             //判断是否为0
                    break;
                }
                System.out.println(a[num]);
            }
        }
    }

c++版：

#include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
        int t , a[60];
        a[1] = 1 ;
        a[2] = 2;
        a[3] = 3;
        a[4] = 4;
        for(int i = 5 ; i < 60 ; i ++)
        {
            a[i] = a[i-1] + a[i-3];
        }
        while(~scanf("%d",&t) && t)
        cout<<a[t]<<endl;
        return 0 ;
    }

hh,如果真有问题公众号交流，加群也行！以学习为首要！

--------------------

#### 总结： ####

对比两个代码版本，其实也没差多少，核心代码几乎相同，在算法上完全是一模一样！所以说算法在任何情况下都是通用的，每一种算法都可以解答一种题目，很有逻辑性。另外还涉及到数学的思想，有些特别简单，比如这个数学递推公式，这就结合数学来解算法题了！遇到这样的题目算是很有趣了，一般都有规律可循，只不过需要花点时间。OK，我是小码，一个会发光的准程序员！下期再见！