VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 1313|回复: 3

[讨论] 如何解决阶乘运算中大数溢出的问题?求助!!!!!!!!!!!

[复制链接]
16_avatar_middle
在线会员 发表于 2016-2-21 18:52:18 | 显示全部楼层 |阅读模式
本帖最后由 小迪 于 2016-2-21 18:53 编辑

//  阶乘

#include <stdio.h>
main()
{
        //代码开始
        long long int num=1,n=0,i=1;//分别定义num[自己乘以i的数,即部分阶乘]、n[被阶乘的数字]、i[自加1的数]
        while(1)
        {
start:
                num=1;
                n=0;
                i=1;
                scanf("%d",&n);
                getchar();
                if(n<=0)
                {
                        printf("您输入的数字不合法!请重新输入!\n");
                        goto start;
                }
                printf("%d的阶乘计算公式及结果如下所示:\n",n);
                printf("1");
                do
                {
                        num=num*i;
                        if(i>1)
                        {
                                printf("×%d",i);
                        }       
                        i=i+1;
                } while (i<=n);
                printf("=%d\n",num);
        }


        getchar();
        return 0;
}


如题所示,当进行大一点的数字时就会溢出,算出来的数不正确,该怎样解决?





上一篇:C语言的指针、数据、结构体关系总结
下一篇:一个C/C++书籍的网盘
81_avatar_middle
online_moderator 发表于 2016-2-22 08:54:50 | 显示全部楼层
更大一些的数的话,恐怕 int 就不够用了,这时候可以考虑用更大的类型,比如:long long
53_avatar_middle
在线会员 发表于 2016-3-4 10:07:23 | 显示全部楼层
在 Intel 32位芯片 + Microsoft WIN32 系统中,数的存储极限
有符号整形 long                         = power(2,31) - 1 = 2147483647        (4 bytes 存储 10位精度的十进制数)
无符号整形 unsgined long = power(2,32) - 1 = 4294967295 (4 bytes 存储 10位精度的十进制数)
双精度浮点 double                 = power(10,308)                                (8 bytes 存储 14位精度的十进制数)(14位以后的精度被忽略)

由上可知,要存储一个大整数或一个高精度的浮点数需要用数组
即把一个数表示为: F(X) = F0(X) + F1(X) + F2(X) + ... + Fn(X)

那么用什么类型的数组比较合适呢?
先考察一下 14 位精度的 double 类型:
当做乘法运算如: A = B * C , 其中 A,B,C 皆为 double 类型,
A 的最大值应该为 99999999999999 (14位)
则 B 或 C 的最大值为 power(A,0.5) = 9999999
得出的结论是 8 bytes 存储一个 7 位的十进制数,固然浪费了存储空间,
而且运算中要进行浮点运算,降低运算效率,所以采用 double 是不合理的

long 与 unsigned long 的存储位数相同,所以性能也是一样的
在讨论它们之前,先了解一小 Intel 32位心片的乘除计算
EDX:EAX = long * long
DX:AX = short * short
AX = byte * byte

EDX:EAX / long => EAX = 商 ; EDX = 余数
DX:AX / short => AX = 商 ; DX = 余数
AX / byte => AL = 商 ; AH = 余数

由上可知,当做乘法运算 A = B * C 时,
A 的最大值应该为 A = power(2,64) - 1 (20位十进制数)
B 或 C 的最大值为  power(A,0.5) = 4294967295 (10位的十进制数)
因为 4294967295 < 9999999999 ,所以只能用 9 位 = 999999999
得出结论是 4 bytes 存储 9 位十进制数,不用浮点运算,效率最佳

A = B * C 得出 A 的最大值 power(999999999,2)
A = B + C + 1 得出 A 的最大值 = 1999999999
53_avatar_middle
在线会员 发表于 2016-3-4 10:41:46 | 显示全部楼层
本帖最后由 xieglt 于 2016-3-4 10:58 编辑

这是很久很久以前写的一个大整数的类。
希望能对你有所帮助。

使用方法
1、计算阶乘30000! 结果输出在 CString strResult 里
        CFloatNumeric a;
        a.InitNumeric(30000,1);
        a.SetInteger(1);
        for(int i = 1 ; i<=30000 ; i ++)
        {
                a.Mul(i);
        }
        CString strResult;
        a.NumericToString(strResult);

2、计算pi小数点后9000位
        CFloatNumeric fnPI;
        CFloatNumeric fnTag;
        CFloatNumeric fnPower;
        CFloatNumeric fnIncrease;
        clock_t endclock, startclock;

        const long dA[] = {12,8,5};
        const long dB[] = {324,3249,57121};
        const long dC[] = {18,57,239};

        fnPI.InitNumeric(1,1000);
        fnTag.InitNumeric(1,1000);
        fnPower.InitNumeric(1,1000);
        fnIncrease.InitNumeric(1,1000);

        fnPI.SetInteger(0);
       
        startclock = clock();

        for(int nLoop = 0; nLoop < 3 ; nLoop ++){
                BOOL blnSign = FALSE;

                fnTag.ZeroNumeric();
                fnTag.SetInteger(0);

                fnPower.ZeroNumeric();
                fnPower.SetInteger(1);

                fnIncrease.ZeroNumeric();

                fnPower.Div(dC[nLoop]);
                fnTag.Add(&fnPower);

                int nInside = 3;
               
                do{
                        fnPower.Div(dB[nLoop]);

                        fnIncrease = fnPower;
                        fnIncrease.Div(nInside);
                       
                        if(blnSign)
                                fnTag.Add(&fnIncrease);
                        else
                                fnTag.Sub(&fnIncrease);

                        nInside += 2;
                        blnSign = !blnSign;

                        if(fnPower.IsZero())
                                break;
                }while(TRUE);
               
                fnTag.Mul(dA[nLoop]);
                if(nLoop != 2)
                        fnPI.Add(&fnTag);
                else
                        fnPI.Sub(&fnTag);
        }
       
        fnPI.Mul(4);

        CString strResult
        fnPI.NumericToString(strResult);

        endclock = clock ();
        TRACE1("Computation time is : %9.2f seconds\n",(float)(endclock-startclock)/(float)CLOCKS_PER_SEC);

HugeInteger.rar

4.69 KB, 下载次数: 1, 下载积分: 驿站币 -1

您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-4-20 21:20

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表