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

里克贝斯

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

6540

发布于 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++