6-10 阶乘计算升级版

发表于 分类于 ， ， ， 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟
简介：PTA - 基础编程题目集 - 函数题 - 6-10阶乘计算升级版

题目

https://pintia.cn/problem-sets/14/problems/742

本题要求实现一个打印非负整数阶乘的函数

程序样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

void Print_Factorial ( const int N );

int main()
{
    int N;

    scanf("%d", &N);
    Print_Factorial(N);
    return 0;
}

/* 你的代码将被嵌在这里 */

方法一

关键代码

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
void Print_Factorial ( const int N ){
	if(N<0){
		printf("Invalid input");
	}else{
		int M = N;
		
		int res[3000];
		res[0] = 1;
		int len = 1;//记录长度 
		
		for(int i=1;i<=N; i++){
			for(int j=0;j<len;j++){
				res[j] *= i;
			}
			
			int k;
			for(int j=0;j<len;j++){
			 	k = j;
				int temp = res[j];
				
				while(temp>0){
					if(j==k){
						res[k] = temp%10;
					}else{
						res[k] += temp%10;
					}
					k++;
					temp /= 10;
				}
			}
			len = k;
		}
		
		for(int i=len-1;i>=0;i--){
			printf("%d ",res[i]);
		}
	}
}

遇到的坑：虽然把数拆成了数组，但是由于计算量过大，单个数组元素还是超出了int范围

结果：N为1000时结果出错。（400时就已经开始出错了）

方法二

关键代码

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
void Print_Factorial ( const int N ){
	if(N<0){
		printf("Invalid input");
	}else{
		int M = N;
		
		int res[3000];
	
		res[0] = 1;
		int len = 1;//记录长度 
		
		for(int i=1;i<=N; i++){
			int w = 0;//w记录进位 
			for(int j=0;j<len;j++){
				res[j] = res[j]*i+w;
				w = res[j]/10;
				res[j] = res[j]%10;
			}
			while(w>0){
				res[len++] = w%10;
				w = w/10;
			}
		}
		
		for(int i=len-1;i>=0;i--){
			printf("%d",res[i]);
		}
	}
}

思路：数组元素依次对1到N相乘，每乘一次，处理一下进位。

结果：OK