求n!的位数以及求n!具体的值（C or C++）

里克贝斯

发布于 2021-05-21 17:11:14

6510

发布于 2021-05-21 17:11:14

首先我们先求n!位数可以将n!表示成10的次幂,即n!=10^M(10的M次方)则不小于M的最小整数就是 n!的位数，对该式两边取对数，有 M =log10^n! 即： M = log10^1+log10^2+log10^3…+log10^n 循环求和,就能算得M值，该M是n!的精确位数。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    int i;
    double d;
    while (cin>>n)
    {
        d=0;
        for (i=1;i<=n;i++)
        {
            d+=(double)log10(i);
        }
        cout<<(int)d+1<<endl;
 }
 return 0;
}

接下来，求n!的具体值具体题目原型来自HDOJ ：http://acm.hdu.edu.cn/showproblem.php?pid=1042

C++ Version:

#include <iostream>
#include <cstring>
/* 一个数组元素表示 4 个十进制位，即数组是万进制的 */
#define BIG_RADIX 10000
#define RADIX_LEN 4
/* 10000! 有 35660 位 */
#define MAX_LEN (35660/RADIX_LEN + 1)
using namespace std;
int x[MAX_LEN + 1];
void Big_Print()
{
    int start_output = 0;//用于跳过多余的0
    for (int i=MAX_LEN;i>= 0;--i)
    {
        if (start_output == 1){//如果多余的0已经跳过，则输出
            cout<<x[i];
        }
        else if (x[i] > 0){//表示多余的0已经跳过
            cout<<x[i];
            start_output = 1;
        }
    }
    if (start_output == 0)//如果全为0
        cout<<"0";
}
void Big_Multiple(int y)
{
    int carry = 0;//保存进位
    int tmp;
    for (int i=0;i<MAX_LEN;++i)
    {
        tmp = x[i] * y + carry;
        x[i] = tmp % BIG_RADIX;
        carry = tmp / BIG_RADIX;
    }
}
void Big_Factorial(int N)
{
    memset(x, 0, sizeof(x));
    x[0] = 1;
    for (int i=2; i<=N;++i){
        Big_Multiple(i);
    }
}
 
int main(void)
{
    int N;
    while (cin>>N)
    {
        Big_Factorial(N);
        Big_Print();
        cout<<endl;
    }
    return 0;
}

C Version:

#include <stdio.h>  
#include <string.h>  
 
/* 一个数组元素表示 4 个十进制位，即数组是万进制的 */  
#define BIG_RADIX 10000  
#define RADIX_LEN 4  
/* 10000! 有 35660 位 */  
#define MAX_LEN (35660/RADIX_LEN + 1)  
 
int x[MAX_LEN + 1];  
 
void Big_Print(){  
    int i;  
    int start_output = 0;//用于跳过多余的0  
 
    for (i = MAX_LEN; i >= 0; --i){  
        if (start_output == 1){//如果多余的0已经跳过，则输出  
            printf("%04d", x[i]);  
        }  
        else if (x[i] > 0){//表示多余的0已经跳过  
            printf("%d", x[i]);  
            start_output = 1;  
        }  
    }  
    if (start_output == 0)//如果全为0  
        printf("0");  
}  
 
void Big_Multiple(int y){  
    int i;  
    int carry = 0;//保存进位  
    int tmp;  
 
    for (i = 0; i < MAX_LEN; ++i){  
        tmp = x[i] * y + carry;  
        x[i] = tmp % BIG_RADIX;  
        carry = tmp / BIG_RADIX;  
    }  
}  
 
void Big_Factorial(int N){  
    int i;  
 
    memset(x, 0, sizeof(x));  
    x[0] = 1;  
    for (i = 2; i <= N; ++i){  
        Big_Multiple(i);  
    }  
}  
 
int main(void){  
    int N;  
 
    while (scanf("%d", &N) != EOF){  
        Big_Factorial(N);  
        Big_Print();  
        printf("\n");  
    }  
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除

c++