时间戳

首页 > 解决方案 > FooLand 城市的奶牛

java - FooLand 城市的奶牛

问题描述

我正在经历这个问题-

FooLand 城市的奶牛是有趣的动物。他们的专长之一与生产后代有关。FooLand 的一头母牛在两岁时生产第一头小牛（雌性小牛），然后继续生产其他小牛（一年一头雌性小牛）。

现在农民 Harold 想知道在 N 年结束时他会拥有多少只动物，如果我们假设没有一只小牛死亡，因为最初他只有一只雌性小牛？

输入：

第一行包含一个整数 T，表示测试用例的数量。测试用例的每一行都包含一个整数 N，如问题中所述。

输出：

对于每个测试用例，在新行中打印 N 年末预期的动物数量

我通过以下代码解决了这个问题-

public static void main (String[] args)
{
    Scanner ab=new Scanner(System.in);
    int t=ab.nextInt();  //number of test cases

    for (int i=0;i<t;i++)
    {
        int n=ab.nextInt(); //years
        int arr[]=new int[n];
        arr[0]=1;
        arr[1]=2;
        if(n>2)
        {
            for(i=2;i<n;i++)
            {
                arr[i]=arr[i-1]+arr[i-2];
            }
        }
        System.out.println(arr[arr.length-1]);


     }
}

但是当我在网上搜索时，他们在网上给出了一个非常复杂的解决方案-

https://hackerranksolutionc.blogspot.in/2017/10/cows-of-fooland.html

我尝试匹配输出，发现结果对于小数字是相同的，但对于非常大的数字是不同的。

我想知道我的解决方案有什么问题吗？

标签： javafibonacci

解决方案

如果预期的时间复杂度是，您的解决方案将不起作用O(log N). 您可以将递归方程转换为矩阵形式并使用矩阵求幂求解。

对于更通用的版本解决这个问题https://www.spoj.com/problems/SEQ/

推荐阅读