文档章节

大数阶乘求法

方绍伟
 方绍伟
发布于 2014/01/04 18:35
字数 1144
阅读 45
收藏 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
BZOJ3028:食物(OGF)

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

qq_35649707
2017/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring详解

Spring详解(一)------概述 目录 1、什么是 Spring ? 2、Spring 起源 3、Spring 特点 4、Spring 框架结构 5、Spring 框架特征 6、Spring 优点   本系列教程我们将对 Spring 进行详解的介绍...

DemonsI
25分钟前
0
0
CentOS7系统Nginx安装

1、下载nginx,官方网站https://nginx.org wget https://nginx.org/download/nginx-1.14.0.tar.gz 2、下载Nginx Sticky Module,官方网站https://bitbucket.org/nginx-goodies/nginx-sticky-......

m_lm
28分钟前
0
0
使用zTree树控件(二)

1:treeNode.checked用于判断是勾选还是取消勾选。(treeNode指的是节点) 2:treeObj.transformToArray(nodes)用于查询nodes节点下的所有子节点,json格式。(treeObj为数的id)...

uug
28分钟前
0
0
export, import 和 export default的区别

ES6的两个功能: export 和 import export 对外输出模块 import 引入(加载)进来一个模块 一、export => import 单个变量 export var name = "lishi" 在其他文件里引用 import {name} f...

Js_Mei
33分钟前
1
0
打造RecyclerView的n级列表

先上效果图: 1.该多级列表的优势: 支持无限级列表展开 基于一个recyclerView实现 可以自定义每一级item的样式,定制化更强 2.设计的思路 数据结构List<ItemBean>,ItemBean类中有变量List<...

WelliJohn
42分钟前
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部