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

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

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

1. 问题分析

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

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

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

main( )
{int i,n,j,sign=1;
float s,t=1;
input(n);
s=1；
for(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）。