none
求100阶乘,考虑溢出哦~

    问题

  • 如题,大数果断会溢出啊,该怎么实现?有没有不使用递归的方法?

    理论上说,只要for循环即可,但是当结果超出了int,long,double的可表示的长度时,应怎么处理得到预期的结果呢?

    2016年5月31日 9:13

答案

  • Hi,

    你可以试试这个数组阶乘算法:

     public static uint[] CalculateLargeNumber(int n)
            {
                if (n < 0) { throw new ArgumentOutOfRangeException("n必须为非负数。"); }
    
                if (n == 0 || n == 1) { return new uint[] { 1 }; }
                // 数组的最大长度
                const int MaxLength = 100000;
                uint[] array = new uint[MaxLength];
                // 1! = 1
                array[0] = 1;
                int i = 0;
                int j = 0;
                // valid为当前阶乘值的位数(如5! = 120,此时valid = 3)
                int valid = 1;
    
                for (i = 2; i <= n; i++)
                {
                    long carry = 0;
                    for (j = 0; j < valid; j++)
                    {
                        long multipleResult = array[j] * i + carry;
                        // 计算当前位的数值
                        array[j] = (uint)(multipleResult % 10);
                        // 计算进到高位的数值
                        carry = multipleResult / 10;
                    }
                    // 为更高位赋值
                    while (carry != 0)
                    {
                        array[valid++] = (uint)(carry % 10);
                        carry /= 10;
                    }
                }
                // 截取有效元素
                uint[] result = new uint[valid];
                Array.Copy(array, result, valid);
                return result;
            }

    使用方法(算法得出的值是高位存在后边):

                uint[] u = CalculateLargeNumber(100);
                string temp = "";
                foreach (var v in u)
                {
                    temp = temp.Insert(0, v.ToString());
                }
                richTextBox1.Text = temp;

    结果:

    93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

    参考链接:

    http://bbs.csdn.net/topics/230022919

    Regards,

    moonlight


    We are trying to better understand customer views on social support experience, so your participation in this interview project would be greatly appreciated if you have time. Thanks for helping make community forums a great place.
    Click HERE to participate the survey.






    2016年6月1日 6:54

全部回复

  • 你试一试就知道了,不要猜测~
    2016年6月1日 6:03
  • Hi,

    你可以试试这个数组阶乘算法:

     public static uint[] CalculateLargeNumber(int n)
            {
                if (n < 0) { throw new ArgumentOutOfRangeException("n必须为非负数。"); }
    
                if (n == 0 || n == 1) { return new uint[] { 1 }; }
                // 数组的最大长度
                const int MaxLength = 100000;
                uint[] array = new uint[MaxLength];
                // 1! = 1
                array[0] = 1;
                int i = 0;
                int j = 0;
                // valid为当前阶乘值的位数(如5! = 120,此时valid = 3)
                int valid = 1;
    
                for (i = 2; i <= n; i++)
                {
                    long carry = 0;
                    for (j = 0; j < valid; j++)
                    {
                        long multipleResult = array[j] * i + carry;
                        // 计算当前位的数值
                        array[j] = (uint)(multipleResult % 10);
                        // 计算进到高位的数值
                        carry = multipleResult / 10;
                    }
                    // 为更高位赋值
                    while (carry != 0)
                    {
                        array[valid++] = (uint)(carry % 10);
                        carry /= 10;
                    }
                }
                // 截取有效元素
                uint[] result = new uint[valid];
                Array.Copy(array, result, valid);
                return result;
            }

    使用方法(算法得出的值是高位存在后边):

                uint[] u = CalculateLargeNumber(100);
                string temp = "";
                foreach (var v in u)
                {
                    temp = temp.Insert(0, v.ToString());
                }
                richTextBox1.Text = temp;

    结果:

    93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

    参考链接:

    http://bbs.csdn.net/topics/230022919

    Regards,

    moonlight


    We are trying to better understand customer views on social support experience, so your participation in this interview project would be greatly appreciated if you have time. Thanks for helping make community forums a great place.
    Click HERE to participate the survey.






    2016年6月1日 6:54
  • 非常感谢您的回答。在网上搜了好久,但是答案都是不太满意:因为几乎都没有考虑溢出,要么就是程序运行有问题。

    大概知道大数溢出的解决方案是使用数组来解决,但是一直没找到答案,谢谢~

    2016年6月1日 14:07
  • 1.我是试过了之后才回复的您,但是从结果来看,您的回复是靠设想和猜测。因为decimal最多能处理到28的阶乘。

    2.我不是说让您帮我去试一试,只是感觉您实际去运行的话会加深对decimal长度的理解和对100阶乘长度的概念的理解。

    3.在问msdn之前,我确实已经在网上搜了好久,但是答案机会都不太满意。要么没考虑溢出,要么程序没法运行,只是知道了大概思路是靠数组解决。所以希望,要么在msdn上有大神回复,以更清晰思路从而实现,要么有大神直接贡献令人惊喜的源码。

    4.我从不认为别人有义务帮我。

    5.可能我的第一个回复言辞欠妥,希望您见谅

    2016年6月1日 14:18