黑马程序员技术交流社区

标题: 解惑:求 2/1+3/2+5/3+8/5+13/8…..前20项之和的算法 [打印本页]
作者: 小丑的媳妇2    时间: 2013-3-6 23:49
标题: 解惑:求 2/1+3/2+5/3+8/5+13/8…..前20项之和的算法
本帖最后由 朱荣宁. 于 2013-3-6 23:50 编辑

对于这道题目 2/1+3/2+5/3+8/5+13/8…..前20项之和我相信很多人都见过,其实这道题的算法思想并不是很难,比如如下代码就可以实现:
class Sum
{
public static void main(Sting[] args)
{
double sum=0;
double fenZi=2.0, fenMu=1.0;    //初始的分子 (fenZi)＝2，分母(fenMu)＝1
for(int i=1; i<=20; i++){
sum += fenZi / fenMu ;
fenMu = fenZi;           //下一项的分母 ＝ 上一项的分子
fenZi += fenMu;         //下一项的分子 ＝ 上一项的分子加分母
}
System.out.println(“sum= “sum);
}
}
这是一种最容易想到的方法,可是这种方法的空间复杂度和时间复杂度都是不理想的,我本人是初学者,想请教高手,可不可以用递归来实现算法,如果可以,请高手给出可以运行的代码,小女子感激不尽!



作者: 陈圳    时间: 2013-3-7 08:56
        public static double method_2(int n,double z,double m)//n为运行次数,z分母,m分子.
        {
               
                if(n==1)
                        return z/m;
                else
                {
                        m=z;//m=2;
                        z=m+z;//z=3
                        return method_2(n-1,z,m)+z/m;//
                }
        }
我感觉结果不正确,也不想验证了.但是与你上面结果一样的.你可以参考下
作者: BitmapFactory    时间: 2013-3-7 09:06


这个应该是最优的了
空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间

而你这个求和的就相当于一个链表,必须知道前面的是什么,才能知道自己是什么
如果用递归的话,要知道前面的是什么才能用,还是得从头找起,反正都是得从头找起,为啥不直接从头找起呢
而且递归占用的空间会很多,递归一次就会创建一个堆栈空间
个人感觉你这个代码 不管从时间复杂度,还是空间复杂度,都是最优的了

作者: 邹学良    时间: 2013-3-7 10:03
本帖最后由 邹学良 于 2013-3-7 10:07 编辑
  1. public static void main(String args[])
  2.         {
  3.         
  4.         int i=1;
  5.         double y=0;
  6.         double sum=0;
  7. //因为分母从2开始，所以共22项
  8.         for(i=1;i<=22;i++) {
  9.                 if(i>2){
  10.                    y=f(i)/f(i-1);
  11.            sum+=y;
  12.                 }
  13.         }
  14.         System.out.print(sum+" ");
  15.         
  16.         }
  17.     public static double f(double x)
  18.         {

  20.         if(x==1||x==2){
  21.         return 1;
  22.         }else{
  23.         return f(x-1)+f(x-2);
  24.         }
  25.         }
  26. }
复制代码
通过斐波那契数列进行递归
作者: BitmapFactory    时间: 2013-3-8 14:07
看晕了,很多东西都忘记了
斐波那契数列看着不太好懂



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2