N的阶乘 -- 牛客

佚名 5年前 (2019-08-19) 算法 2318人围观抢沙发百度已收录

题目描述

输入一个正整数N，输出N的阶乘。

输入描述:

正整数N(0<=N<=1000)

输出描述:

 输入可能包括多组数据，对于每一组输入数据，输出N的阶乘

示例1

输入

4
5
15

输出

24
120
1307674368000

解题思路

这并不是一道简单的求N阶乘的题目，一般来说求阶乘的方法有俩种：第一直接利用循环求解。第二是使用递归进行求解
但是在这里若是简单的使用以上的俩种方法将会导致内存不够。
所以，我们需要采用大数乘法的方式进行求解：
1、利用一个数组对结果按个位、十位、百位...进行存储。
2、对于阶乘，采用按位相乘的原则。首先建立i从1到 N 的循环，再从个位开始与i相乘，并且用一个进位位carry记录上一次相乘的进位。
3、记录下来当前乘法结果的位数，每一次内循环只需要依次计算当前结果的位数的长度。
4、以每4位为一个单位进行存储。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 using namespace std;
 5 #define max 10000
 6 int main()
 7 {
 8     int N;
 9     long res[max] = {0}; //利用长数组来存放结果
10     while(cin >> N)
11     {
12         int i,j,carry = 0,bit = 0; //分别记录进位位和当前结果的位数
13         res[0] = 1;
14         for(i=1;i<=N;i++,carry=0)
15         {
16             for(j = 0;j<=bit;j++)
17             {
18                 res[j] = res[j]*i + carry;
19                 carry = res[j]/10000;
20                 res[j] = res[j]%10000;
21             }
22             if(carry)
23                 res[++bit] = carry; //处理新的进位
24         }
25           for(printf("%ld",res[i=bit]);i;printf("%.4ld",res[--i])); //从高位开始输出
26               cout<<endl;
27 
28     }
29 }