问题描述
嗯，没错，我们都知道c,c++等机器执行效率很高，java在这方面没法比，但是我只喜欢java,最近在poj上做题，由于我是菜鸟，就挑简单点的做，这不，今天碰到的个非常水的题，如下：http://poj.org/problem?id=1953,这个题，想了会，找了会规律发现，根本不用去遍历，这个题就是个典型的数学题，小学生都会，如下：n=1answer=2n=2answer=3n=3answer=5n=4answer=8n=5answer=13呵呵，看到规律了吧，我还是不放心，我用遍历判断的方法又测试了几个大点数，没错，就是这个规律，说了这么多貌似跑题了，我的困惑在哪呢？我用publicstaticintgetRes(intn){inta=2;intb=3;intres=0;if(n==1){returna;}elseif(n==2){returnb;}for(inti=0;i<n-2;i++){res=a+b;a=b;b=res;}returnres;}
来实现求解，最后结果非常满意，172ms,嗯比其他大部分水友的效率都高，但是我发现有水友用java0s就可以实现的。我就在思考，怎么做到的，想了想估计是我的getRes方法还是消耗了很多时间，于是我在看到题目的n最多不大于45,所以我决定后台生成所有的结果，直接在程序中初始化一个数组，把上面的结果全部放入，然后输入n直接去数组取，这样的话应该不消耗时间了吧？哈哈，我暗自得意，以为问题就这么简单。我submit后不出所料AC了，但是，尼玛变219ms了。我就不明白了，为什么我直接从数组中取数，比用算法计算得出结果的时间还要长？？想了半天，无解，苦恼中，困惑中。。祈求大牛指点迷津！跪求！
解决方案
解决方案二：
尼玛，需要帮助的时候就没人来了，没事找着资料发发稿子谁都会，遇到问题就尼玛没人帮啊！
解决方案三：
publicstaticintgetRes(intn){inta=2;intb=3;if(n==1){returna;}elseif(n==2){returnb;}returngetRes2(n-1)+getRes2(n-2);}
要是我可能这么写，但是这个数据量多的时候也慢，不知道楼主那个时间怎么计算的，查询数据也是需要时间的
解决方案四：
publicstaticintgetRes(intn){inta=2;intb=3;if(n==1){returna;}elseif(n==2){returnb;}returngetRes(n-1)+getRes(n-2);}
上面贴错了，递归，数据量小比如n<10,这个方法应该比for循环快点
解决方案五：
publicstaticintgetRes(intn){return(int)((Math.pow((1+Math.sqrt(5))/2,n+2)-Math.pow((1-Math.sqrt(5))/2,n+2))/Math.sqrt(5));}
这个能通过么?
解决方案六：
试试直接用switch语句
解决方案七：
速度最快的肯定是直接用公式求解：http://baike.baidu.com/view/816.htm楼主给出来的是迭代算法，也就是老老实实慢慢加了。3楼给出来的是递归，比迭代算法更慢。楼主的疑问没啥好奇怪的吧，你所谓的后台算法，CPU时间都会被记录的，偷鸡是不行的。你如果真想试试能不能偷鸡，把45以内的值写死在程序代码所定义的数据里面，然后直接从数组里面获取结果吧。
解决方案八：
引用6楼ldh911的回复:
速度最快的肯定是直接用公式求解：http://baike.baidu.com/view/816.htm楼主给出来的是迭代算法，也就是老老实实慢慢加了。3楼给出来的是递归，比迭代算法更慢。楼主的疑问没啥好奇怪的吧，你所谓的后台算法，CPU时间都会被记录的，偷鸡是不行的。你如果真想试试能不能偷鸡，把45以内的值写死在程序代码所定义的数据里面，然后直接从数组里面获取结果吧。
递归那个，我测试n大概在小于10的时候，的确是比for循环快的，不过越往后，就不如for循环快了
解决方案九：
全部结果预先放入内存？查表法也有应用场景的，它有2个使用条件1.运算量大，也就是说计算非常消耗时间。2.有限空间，也就是说结果表空间不大。举个例子，如果题目是素数判断。20以内素数查表法时间复杂度是最差的，超过百万空间复杂度也很高。一万以内的素数判断，查表法的效率就很高了。
解决方案十：
引用4楼u012872817的回复:
publicstaticintgetRes(intn){return(int)((Math.pow((1+Math.sqrt(5))/2,n+2)-Math.pow((1-Math.sqrt(5))/2,n+2))/Math.sqrt(5));}这个能通过么?
这个可以通过，只是时间会很慢，应为pow是很多乘运算，很慢的，
解决方案十一：
引用7楼shixitong的回复:
Quote: 引用6楼ldh911的回复:
速度最快的肯定是直接用公式求解：http://baike.baidu.com/view/816.htm楼主给出来的是迭代算法，也就是老老实实慢慢加了。3楼给出来的是递归，比迭代算法更慢。楼主的疑问没啥好奇怪的吧，你所谓的后台算法，CPU时间都会被记录的，偷鸡是不行的。你如果真想试试能不能偷鸡，把45以内的值写死在程序代码所定义的数据里面，然后直接从数组里面获取结果吧。朋友你说直接用公式最快怎么得到的？？？为什么自己没有去做就乱说呢，直接用公式没有for循环快的，递归的话，数大直接回TLE的，哎
时间： 2024-12-05 23:59:37