文档章节

大数阶乘求法

方绍伟
 方绍伟
发布于 2014/01/04 18:35
字数 1144
阅读 45
收藏 1
点赞 0
评论 0
一、递归方法
这个是最容易想的,如果是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;
    }
}

© 著作权归作者所有

共有 人打赏支持
方绍伟
粉丝 6
博文 60
码字总数 1947
作品 0
东城
javascript解决 - 求100!的结果的各位数之和为多少?

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

顽Shi ⋅ 2014/01/02 ⋅ 6

阶乘之计算从入门到精通-菜鸟篇

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

mj4738 ⋅ 2011/11/12 ⋅ 0

51Nod 1057 N的阶乘(基础题???数论???)

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

Akatsuki__Itachi ⋅ 2017/12/21 ⋅ 0

xynuoj 1816 大数阶乘

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

dear_jia ⋅ 05/02 ⋅ 0

BZOJ3028:食物(OGF)

传送门 题意: 给一堆东西和选的限制,求把背包装满的方案数。。 题解: 对于每种组合我们只关心每种食物的个数,故可以每一个组成对象构造一般性生成函数。 显然答案为所有食物的笛卡尔积,...

qq_35649707 ⋅ 2017/12/22 ⋅ 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

OJ水题----数的长度

描述: N!阶乘是一个非常大的数,大家都知道计算公式是N!=N(N-1)······21.现在你的任务是计算出N!的位数有多少(十进制)? 输入:首行输入n,表示有多少组测试数据(n<10) 随后n行每行...

一只小小小鸟 ⋅ 2015/05/18 ⋅ 0

C(题总结一下)

1.把2个大数存在字符串中进行处理,不能按照int, long , long long来处理 思路:把两个大数相同位数的数字全部加在一起,用个数组装起来,假如这个数字>9 ,前面的数字就+1(需要从后面开始判...

都英俊兮 ⋅ 2016/06/23 ⋅ 0

曾经做过的40道程序设计课后习题总结(三)

曾经做过的40道程序设计课后习题总结(三) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最大公约数与最小公倍数 8 完全平方数 9 统计字...

闵开慧 ⋅ 2015/08/11 ⋅ 0

n阶贝塞尔曲线绘制(C/C#)

贝塞尔是很经典的东西,轮子应该有很多的。求n阶贝塞尔曲线用到了 德卡斯特里奥算法(De Casteljau’s Algorithm) 需要拷贝代码请直接使用本文最后的例程,文章前面的大部分代码都不是最佳实...

Backspace110 ⋅ 2017/05/26 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

Spring JDBC使用方法

普通实现: 1、创建数据表customer。 可以使用任何数据库实现,在项目中要引入相应数据库驱动包并配置相应数据库连接。 2、创建Customer pojo。 Customer类的属性对应数据库的属性,除了为每...

霍淇滨 ⋅ 今天 ⋅ 0

Contos 7 安装Jenkins

Jenkins是一款能提高效率的软件,它能帮你把软件开发过程形成工作流,典型的工作流包括以下几个步骤 开发 提交 编译 测试 发布 有了Jenkins的帮助,在这5步中,除了第1步,后续的4步都是自动...

欧虞山 ⋅ 今天 ⋅ 0

revel

revel install go get github.com/revel/revelgo get github.com/revel/cmd create new app revel new git.oschina.net/zdglf/myapp run app revel run git.oschina.net/zdglf/myapp ot......

zdglf ⋅ 今天 ⋅ 0

49. Group Anagrams - LeetCode

Question 49. Group Anagrams Solution 思路:维护一个map,key是输入数组中的字符串(根据字符排好序) Java实现: public List<List<String>> groupAnagrams(String[] strs) { Map<Strin......

yysue ⋅ 今天 ⋅ 0

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 今天 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 今天 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部