c++之阶乘之和

。。。

问题:用高精度计算出S = 1! + 2! + 3! + ``` + n! (n <= 50)。其中 “!” 表示阶乘,例如:5! = 5 * 4 * 3 * 2 * 1。

先偷个懒用python试试答案:

1
2
3
4
5
6
7
8
9
10
#算出n=50的阶乘之和
sum = 0
for i in range(1,51):
b = 1
for j in range(1, i+1):
b *= j
sum += b
print(sum)

print(len(str(sum)))

输出:

31035053229546199656252032972759319953190362094566672920420940313
65

最大只有65位,所以说数组最大开到65就行。。

再用Java偷个懒。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.IOException;
import java.math.BigInteger;
import java.util.Scanner;

public class Main{
public static void main(String[] args) throws IOException {
Scanner sn = new Scanner(System.in);
int n = sn.nextInt();
sn.close();

BigInteger ans = new BigInteger("0");
for (int i=1; i <= n; ++i) {
BigInteger temp = new BigInteger("1");
for (int j=2; j<=i; ++j) {
temp = temp.multiply(new BigInteger(Integer.toString(j)));
}
ans = ans.add(temp);
}
System.out.println(ans.toString());
}
}

这代码没优化,不过运行没问题(尴尬…)

输入50,输出:31035053229546199656252032972759319953190362094566672920420940313

一样,最后用c++

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

#define MAXN 65
int a[MAXN], b[MAXN];

int main() {

int n;
cin >> n;

for (int i = 1; i <= n; ++i) {

memset(b, 0, sizeof(b));
b[0] = 1;

for (int j = 1; j <= i; ++j) {
for (int k = 0; k < MAXN; ++k)
b[k] *= j;
for (int j = 1; j < MAXN; ++j) {
b[j] += b[j - 1] / 10;
b[j - 1] %= 10;
}
}

for (int j = 0; j < MAXN; ++j)
a[j] += b[j];
}

for (int i = 1; i < MAXN; ++i) {
a[i] += a[i - 1] / 10;
a[i - 1] %= 10;
}

int pos = MAXN - 1;
while (!a[pos]) {
--pos;
}

for (int i = pos; i >= 0; --i) {
cout << a[i];
}

return 0;
}

50
31035053229546199656252032972759319953190362094566672920420940313

上面python已经知道65是最长的答案了,所以MAXN = 65没问题,然后一堆for解决….

改进了一下,不用每次都清空b了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

#define MAXN 65
int a[MAXN], b[MAXN];

int main() {

int n;
cin >> n;

b[0] = 1;

for (int i = 1; i <= n; ++i) {

for (int k = 0; k < MAXN; ++k)
b[k] *= i;

for (int j = 1; j < MAXN; ++j) {
b[j] += b[j - 1] / 10;
b[j - 1] %= 10;
}

for (int j = 0; j < MAXN; ++j)
a[j] += b[j];
}

for (int i = 1; i < MAXN; ++i) {
a[i] += a[i - 1] / 10;
a[i - 1] %= 10;
}

int pos = MAXN - 1;
while (!a[pos])
--pos;

for (int i = pos; i >= 0; --i)
cout << a[i];

return 0;
}
评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...