大数，阶乘，小数位数

在codewar的一道题

Consider the following numbers (where n! is factorial(n)):

u1 = (1 / 1!) * (1!)
u2 = (1 / 2!) * (1! + 2!)
u3 = (1 / 3!) * (1! + 2! + 3!)
un = (1 / n!) * (1! + 2! + 3! + … + n!)
Which will win: 1 / n! or (1! + 2! + 3! + … + n!)?

Are these numbers going to 0 because of 1/n! or to infinity due to the sum of factorials or to another number?

Task

Calculate (1 / n!) * (1! + 2! + 3! + … + n!) for a given n, where n is an integer greater or equal to 1.

To avoid discussions about rounding, return the result truncated to 6 decimal places, for example:

1.0000989217538616 will be truncated to 1.000098
1.2125000000000001 will be truncated to 1.2125
Remark

Keep in mind that factorials grow rather rapidly, and you need to handle large inputs.

一开始提交，连简单的测试的都过不了，代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Suite
{
public:
  static double going(int n);
};
long long f(int n){
    if(n==1) return 1;
    else return (long long)(n*f(n-1));
}
long long fa(int n){
    if(n==1) return f(1);
    else return (long long)(f(n)+fa(n-1));
}

double Suite::going(int n){
   return result=((double)1.0)/f(n)*fa(n);
   }

给出这样的结果

Test Results:
going_Tests
Fixed__Tests
Expected: equal to 1.2125
Actual: 1.2125

原因是浮点数不能直接比较，因此做了如下改进：

1
2
3
4
5
6


double Suite::going(int n){
   double result = ((double)1.0)/f(n)*fa(n);
   long long re_l = (long long)(result*1000000);
   result = ((double)re_l)/1000000.0;
   return result;
   }

现在的测试结果

Test Results:
going_Tests
Fixed__Tests
Log
Correct. Testing; Expected is 1.275, and got 1.275
Correct. Testing; Expected is 1.2125, and got 1.2125
Correct. Testing; Expected is 1.173214, and got 1.173214
Correct. Testing; Expected is 1.146651, and got 1.146651
Correct. Testing; Expected is 1.052786, and got 1.052786
Testing; Expected should be 1.034525, but got 0.68527
Expected: false
Actual: 1
Random_tests
Log
****************** Random Tests **** going
Testing; Expected should be 1.032292, but got 1.166542
Expected: false
Actual: 1

很明显是阶乘结果太大，超出了long long的界限。

20190401更：
原本想着使用大数的处理方法，如https://blog.csdn.net/qq_39445165/article/details/88377252

但是发现即使使用了数组表示很大的数，后面的也不好处理。
现在把式子转化成1+1/n+1/n(n-1)+…+1/n(n-1)…2+1/n!，若分母很大比如大于10的8次方，那么这一项对于和没有意义，因为精度限制在六位小数，于是新的处理方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Suite
{
public:
  static double going(int n);
};

double Suite::going(int n){
   int i;
   long long re_l,temp = n;
   double result = 1.0;
   for(i=1;i<n;i++)
   {
       result += ((double)1.0)/temp;
       temp *= (n-i);
       if(temp>100000000) break;
   }
   re_l = (long long)(result*1000000);
   result = ((double)re_l)/1000000.0;
   return result;
   }

通过了测试

codewar 题1

Contents

大数，阶乘，小数位数