文档章节

大数阶乘求法

方绍伟
 方绍伟
发布于 2014/01/04 18:35
字数 1144
阅读 48
收藏 1
一、递归方法
这个是最容易想的,如果是1的阶乘,则返回1,其他的都返回n-1的阶乘与n的积,循环调用即可。不过问题是即使用double来存放该值,由于double本身的精度、能存的数字大小所限,算不了太大的数的阶乘。
二、数组方法
思路:用data数组来存放阶乘的每一位数字,首先令第一位的数值为1,位数为1,然后将每次相乘的乘积存回数组,并循环处理每个数组中超过10的数,若数值超过10,则需要进位,将位数加1,原来的数除以10,商数加前一位数的数值后存回前一位数的数组中,再将余数存回原来位数的数组中。
例如求5!的值
步骤一:
1!=1
位数1
数组内容0      0      0      1
步骤二:
2!=2*1!=2
位数1
数组内容0      0      0      2
步骤三:
3!=3*2!=3*2=6
位数1
数组内容0      0      0      6
步骤四:
4!=4*3!=4*4=24
位数1
数组内容0      0      0      24
因为24大于10,需要进位
data[1]=data[1]+data[0]/10=0+2=2
data[0]=data[0]%10=4
所以数组内容为0      0      2      4
位数2
步骤五:
5!=5*4!=5*24=120
位数2
数组内容为0      0      2*5      4*5
即0      0      10      20
因为data[0]大于10,需要进位
data[1]=data[1]+data[0]/10=10+2=12
data[0]=data[1]%10=0
此时数组内容为0      0      12      0
data[2]=data[2]+data[1]/10=0+1=1
data[1]=data[1]%10=2
位数加1
数组内容为0      1      2      0
一次类推,可以计算大数的阶乘,代码如下:
#include <stdio.h>

int main(void)
{
       int Data[10001];
       int digit;
       int i,j,r,k;
       int N;
    
       for(i=1;i<10000+1;i++)
          Data[i]=0;
       Data[0]=1;
       Data[1]=1;
       digit=1;
    
       printf("Enter a number what you want to calculus:");
       scanf("%d",&N);
    
       for(i=1;i<N+1;i++)
       {
           for(j=1;j<digit+1;j++)
               Data[j]*=i;
           for(j=1;j<digit+1;j++)
           {
               if(Data[j]>10)
               {
                   for(r=1;r<digit+1;r++)
                   {
                       if(Data[digit]>9)
                           digit++;
                       Data[r+1]+=Data[r]/10;
                       Data[r]=Data[r]%10;
                   }
               }
           }
       }
       printf("%d!=",N);
       for(k=digit;k>0;k--)
           printf("%d",Data[k]);
       return 0;
}

具体算法中有最朴实的乘法运算思想,请各位细细体味。
#include 
int main()
{

int n;                                             //阶乘大小
printf("请输入n的大小:");
scanf("%d",&n);                                    //从键盘接收阶乘大小
int a[200];                                        //确保保存最终运算结果的数组足够大
int carry;                                         //进位
int digit = 1;                                     //位数
a[0] = 1;                                          //将结果先初始化为1
int temp;                                          //阶乘的任一元素与临时结果的某位的乘

积结果
         
for(int i = 2; i <= n; ++i)                        //开始阶乘,阶乘元素从2开始依次“登场


{
          //按最基本的乘法运算思想来考虑,将临时结果的每位与阶乘元素相乘 
   for(int j = 1, carry = 0; j <= digit; ++j)    
   {
    temp = a[j-1] * i + carry;                 //相应阶乘中的一项与当前所得临时结果的某

位相乘(加上进位)
         a[j-1] = temp % 10;                        //更新临时结果的位上信息
    carry = temp / 10;                         //看是否有进位
   }
   while(carry)                                   //如果有进位
   {
    a[++digit-1] = carry % 10;                 //新加一位,添加信息。位数增1
    carry /= 10;                               //看还能不能进位
   }
}

printf("结果是:\n%d ! = ",n);                      //显示结果
for(int i = digit; i >=1; --i)
{
   printf("%d",a[i-1]);
}
return 0;
}

#include<stdio.h>
#include<stdlib.h> // for malloc()
#include<string.h> // for memset()
#define QUOTIETY 4 // 内存分配系数,计算10000以内阶乘设置为4就足够,如果需要
                     // 计算更大的数的阶乘,则将该系数适当增大

void process(const int index, int *result);
int cnt = 1;

int main(void)
{
    int index = 0;
    int input = 0;
    int *result = NULL;

    // 获得输入数据
    printf("请输入你要计算的阶乘数,内存有限,请不要超过10000:\n");
    scanf("%d", &input);
    while (input <= 0 || input > 10000)
    {
        printf("请输入合理的数据,谢谢:\n");
        scanf("%d", &input);
    }
    
    // 申请空间储存计算结果
    result = (int *)malloc(sizeof(int) * input * QUOTIETY);
    if (result == NULL)
    {
        printf("内存申请失败!\n");
        exit(-1);
    }
    memset(result, 0, sizeof(int) * input * QUOTIETY); // 初始化存储空间
    result[0] = 1;

    // 进行阶乘计算
    for ( index = 1; index <= input; ++index)
    {
        process(index, result);
    }

    // 打印结果
    for (index = cnt - 1; index >= 0L; --index)
    {
        printf("%d", result[index]);
    }
    putchar('\n');
    printf("结果一共有%d位数!\n", cnt);

    free(result);
    return 0;
}

/*
* 计算阶乘核心代码
*/
void process(const int index, int *result)
{
    int product = 0; // 乘积
    int carry = 0;    // 进位
    int remainder = 0; // 余数
    int i = 0;

    for (i = 0; i < cnt; ++i)
    {
        product = result[i] * index + carry;
        carry = product / 10;
        remainder = product % 10;
        result[i] = remainder;
    }

    if (carry != 0)
    {
        while (carry / 10 != 0)
        {
            result[cnt] = carry % 10;
            carry /= 10;
            ++cnt;
        }
        result[cnt++] = carry;
    }
}

本文转载自:http://blog.163.com/mq_wei/blog/static/14089115920101014105531274/

共有 人打赏支持
方绍伟
粉丝 6
博文 60
码字总数 1947
作品 0
东城
私信 提问
阶乘之计算从入门到精通-菜鸟篇

摘要:本文给出一些最简单的计算阶乘的程序,这也是许多C语方言初学者写出的算阶乘的程序。它虽然不能正确地计算出大数阶乘,但它依然有许多正确的思想。让我们从错误中开始,开始一个漫长的...

mj4738
2011/11/12
0
0
javascript解决 - 求100!的结果的各位数之和为多少?

今天无意中看到一篇博客http://www.oschina.net/code/snippet25390027679,作者在里面提到一个问题是通过java处理100!的结果的各位数之和为多少? 因为Java有着严格的数据类型机制,数据会越界...

顽Shi
2014/01/02
0
6
51Nod 1057 N的阶乘(基础题???数论???)

输入N求N的阶乘的准确值。 Input 输入N(1 <= N <= 10000) Output 输出N的阶乘 Input示例 5 Output示例 120 把这种题放在基础题。。。也太打击人的自信了吧。。。 基础题都刷不了。。。 本来套...

Akatsuki__Itachi
2017/12/21
0
0
xynuoj 1816 大数阶乘

1816: 大数阶乘时间限制: 3 Sec 内存限制: 64 MB [提交][状态][讨论版] 题目描述 我们都知道如何计算一个数的阶乘,可是,如果这个数很大呢,我们该如何去计算它并输出它? 输入 输入一个整数...

dear_jia
05/02
0
0
Bryce1010 Acm模板

目录 STL标准模板库 STL简介 STL pair STL set STL vector STL string STL stack STL queue STL map upperbound和lowerbound STL bitset STL iterator简介 STL algorithm greater< int>()和l......

Fire_to_cheat_
2017/09/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用form表单同时实现上传文件和提交文本数据

使用form表单同时实现上传文件和提交文本数据,此示例中在后台将文件上传到阿里的oss存储服务器中 申请oss相关账号: endpoint = "http://oss-cn-qingdao.aliyuncs.com"; accessKeyId = "key"...

貔貅叔
13分钟前
1
0
结合实际场景谈一谈微服务配置

作为 Nacos 5W1H 的系列文章,本文将围绕“Where”,讲述 Nacos 配置管理的三个典型的应用场景: 数据库连接信息 限流阈值和降级开关 流量的动态调度 上一篇:Nacos帮我解决了什么问题? 数据...

阿里云云栖社区
15分钟前
1
0
在Windows安装运行Kafka

https://www.cnblogs.com/flower1990/p/7466882.html 一、安装JAVA JDK 1、下载安装包 http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 注意:根据3......

洛水
16分钟前
1
0
插件

sftp Bracket Pair Colorizer Guides Auto Rename Tag Chinese (Simplified) Language Pack for Visual Studio Code...

dragon_tech
17分钟前
1
0
Missing Number(leetcode268)

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. Example 1: Input: [3,0,1]Output: 2 Example 2: Input: [9,6......

woshixin
22分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部