欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求1/1!-1/3!+1/5!-1/7!+…+(-1)n+1/(2n-1)!(-1的n+1次方)

程序员文章站 2022-05-08 22:19:45
...

求1/1!-1/3!+1/5!-1/7!+…+(-1)n+1/(2n-1)!(-1的n+1次方)

一、普通的思路——循环的嵌套

1. 问题分析

此问题中既有累加又有累乘,准确的说累加的对象是累乘的结果。

2. 所要构造的数学模型:

求1/1!-1/3!+1/5!-1/7!+…+(-1)n+1/(2n-1)!(-1的n+1次方)

3. 算法的设计:(伪代码描述)

main( )
{int i,n,j,sign=1;
float s,t=1;
input(n);
s=1for(i=2;i<=n;i=i+1)
  {t=1;          /*求阶乘*/
   for(j=1;j<=2*i-1;j=j+1)
         t=t*j;
   sign =1; /*求(-1)n+1*/
   for(j=1;j<=i+1;j=j+1)
       sign = sign *(-1);
   s=s+ sign/t;
   }
 print(“Sum=,s);
}
            

4. 算法分析:

以上算法是二重循环来完成 ,但算法的效率却太低是O(n2)。
其原因是,当前一次循环已求出7!,当这次要想求9!时,没必要再从1去累乘到9,只需要充分利用前一次的结果,用7!89即可得到9!,模型为An=An-11/((2n-2)(2n-1)。另外运算sign= sign (-1);总共也要进行n(n-1)/2次乘法,这也是没有必要的。下面我们就进行改进。

二、递归的思路

1.所要构造的数学模型

Sn=Sn-1+(-1)n+1An;
An=An-1 1/((2n-2)(2n-1))
//先不考虑正负号,1/7!=(1/5!)(1/6)(1/7)

2.算法的设计(伪代码描述)

main( )
{int i,n, sign;
 float s,t=1;
 input(n);
s=1;
sign=1; 
 for(i=2;i<=n;i=i+1)for(i=1;i<=n-1;i=i+1)
  {sign=-sign;                       { sign=-sign;
   t= t*(2*i-2)*(2*i-1)}             t= t*2*i*(2*i+1)};
   s=s+sign/t; }                      s=s+ sign/t; }
  print(“Sum=,s);
}

3.算法说明

构造循环不变式时,一定要注意循环变量的意义,如当i不是项式序号的时候,(右边的循环中)有关t的累乘式与i是项式序号时就不能相同。

4.算法分析

按照数学模型2,只需一重循环就能解决问题。算法的时间复杂性为O(n)。

相关标签: 递归法