求一个C#阶乘的算法(能算100以上的),用字符串来保存结果。

求一个C#阶乘的算法(能算100以上的),用字符串来保存结果。在线等待。谢谢答复。

144 个解决方案

#1

是个问题，等待高手

#2

参考：
http://topic.csdn.net/u/20080520/16/c6968aa3-be5f-4592-85bc-b8739d698530.html
用数组存储

#3

100！=9332621544394415268169923885626670049071596826438162146
8592963895217599993229915608941463976156518286253697920827223
758251185210916864000000000000000000000000

#4

就一个递归思想

#5

楼上的，不仅仅是递归，还有溢出

#6

引用 4 楼 zwcscq 的回复:

就一个递归思想

现在世界上有计算机能用递归算出100! ?

#7

不是要结果哈,要代码...
我以前算过10000的阶乘的.就是用字符串保存结果这个算法算的,用了7秒多...

#8

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;
        } 
static void Main(string[] args)
        {
            uint[] arr = CalculateLargeNumber(100);
            string str = "";
            for (int i = arr.Length-1; i >=0 ; i--)
            {
                str += arr[i].ToString();
            }
            Console.WriteLine(str);
            Console.ReadKey();
        }

给你链接，不好好看

#9

可以考虑用大整数：BigInteger

#10

引用 9 楼 *8808 的回复:

可以考虑用大整数：BigInteger

顶

#11

using System;
using System.Text;
using System.Collections.Generic;

namespace Skyiv
{
  class Factorial
  {
    const int n = 100;
    
    static void Main()
    {
      BigInteger f = 1;
      for (int i = 2; i <= n; i++)
      {
        f *= i;
      }
      Console.WriteLine("{0}! = {1}", n, f);
    }
  }
  
  static class Utility
  {
    public static void Swap<T>(ref T x, ref T y)
    {
      T z = x;
      x = y;
      y = z;
    }
  }

  sealed class BigInteger : IEquatable<BigInteger>, IComparable<BigInteger>
  {
    static readonly int Len = 9; // int.MaxValue = 2,147,483,647
    static readonly int Base = (int)Math.Pow(10, Len);

    int sign;
    List<int> data;

    BigInteger(long x)
    {
      sign = (x == 0) ? 0 : ((x > 0) ? 1 : -1);
      data = new List<int>();
      for (ulong z = (x < 0) ? (ulong)-x : (ulong)x; z != 0; z /= (ulong)Base) data.Add((int)(z % (ulong)Base));
    }

    BigInteger(BigInteger x)
    {
      sign = x.sign;  // x != null
      data = new List<int>(x.data);
    }

    public static implicit operator BigInteger(long x)
    {
      return new BigInteger(x);
    }

    public static BigInteger Parse(string s)
    {
      if (s == null) return null;
      s = s.Trim().Replace(",", null);
      if (s.Length == 0) return 0;
      BigInteger z = 0;
      z.sign = (s[0] == '-') ? -1 : 1;
      if (s[0] == '-' || s[0] == '+') s = s.Substring(1);
      int r = s.Length % Len;
      z.data = new List<int>(new int[s.Length / Len + ((r != 0) ? 1 : 0)]);
      int i = z.data.Count - 1;
      if (r != 0) z.data[i--] = int.Parse(s.Substring(0, r));
      for (; i >= 0; i--, r += Len) z.data[i] = int.Parse(s.Substring(r, Len));
      z.Shrink();
      return z;
    }

    public static BigInteger Abs(BigInteger x)
    {
      if (x == null) return null;
      BigInteger z = new BigInteger(x);
      z.sign = Math.Abs(x.sign);
      return z;
    }

    public static BigInteger Pow(BigInteger x, long y)
    {
      if (x == null) return null;
      BigInteger z = 1, n = x;
      for (; y > 0; y >>= 1, n *= n) if ((y & 1) != 0) z *= n;
      return z;
    }

    public static BigInteger operator +(BigInteger x)
    {
      if (x == null) return null;
      return new BigInteger(x);
    }

    public static BigInteger operator -(BigInteger x)
    {
      if (x == null) return null;
      BigInteger z = new BigInteger(x);
      z.sign = -x.sign;
      return z;
    }

    public static BigInteger operator ++(BigInteger x)
    {
      return x + 1;
    }

    public static BigInteger operator --(BigInteger x)
    {
      return x - 1;
    }

    public static BigInteger operator +(BigInteger x, BigInteger y)
    {
      if (x == null || y == null) return null;
      if (x.AbsCompareTo(y) < 0) Utility.Swap(ref x, ref y);
      BigInteger z = new BigInteger(x);
      if (x.sign * y.sign == -1) z.AbsSubtract(y);
      else z.AbsAdd(y);
      return z;
    }

    public static BigInteger operator -(BigInteger x, BigInteger y)
    {
      if (x == null || y == null) return null;
      return x + (-y);
    }

    public static BigInteger operator *(BigInteger x, BigInteger y)
    {
      if (x == null || y == null) return null;
      BigInteger z = 0;
      z.sign = x.sign * y.sign;
      z.data = new List<int>(new int[x.data.Count + y.data.Count]);
      for (int i = x.data.Count - 1; i >= 0; i--)
        for (int j = y.data.Count - 1; j >= 0; j--)
        {
          long n = Math.BigMul(x.data[i], y.data[j]);
          z.data[i + j] += (int)(n % Base);
          z.CarryUp(i + j);
          z.data[i + j + 1] += (int)(n / Base);
          z.CarryUp(i + j + 1);
        }
      z.Shrink();
      return z;
    }

    public static BigInteger operator /(BigInteger dividend, BigInteger divisor)
    {
      BigInteger remainder;
      return DivRem(dividend, divisor, out remainder);
    }

    public static BigInteger operator %(BigInteger dividend, BigInteger divisor)
    {
      BigInteger remainder;
      DivRem(dividend, divisor, out remainder);
      return remainder;
    }

    public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
    {
      remainder = null;
      if (dividend == null || divisor == null) return null;
      if (divisor.sign == 0) throw new DivideByZeroException();
      if (dividend.AbsCompareTo(divisor) < 0)
      {
        remainder = new BigInteger(dividend);
        return 0;
      }
      remainder = 0;
      BigInteger quotient = 0;
      quotient.sign = dividend.sign * divisor.sign;
      quotient.data = new List<int>(new int[dividend.data.Count]);
      divisor = Abs(divisor); // NOT: divisor.sign = Math.Abs(divisor.sign);
      for (int i = dividend.data.Count - 1; i >= 0; i--)
      {
        remainder = remainder * Base + dividend.data[i];
        int iQuotient = remainder.BinarySearch(divisor, -1);
        quotient.data[i] = iQuotient;
        remainder -= divisor * iQuotient;
      }
      quotient.Shrink();
      if (remainder.sign != 0) remainder.sign = dividend.sign;
      return quotient;
    }

    public static BigInteger Sqrt(BigInteger x)
    {
      if (x == null || x.sign < 0) return null;
      BigInteger root = 0;
      root.sign = 1;
      root.data = new List<int>(new int[x.data.Count / 2 + 1]);
      for (int i = root.data.Count - 1; i >= 0; i--) root.data[i] = x.BinarySearch(root, i);
      root.Shrink();
      return root;
    }

    int BinarySearch(BigInteger divisor, int i)
    {
      int low = 0, high = Base - 1, mid = 0, cmp = 0;
      while (low <= high)
      {
        mid = (low + high) / 2;
        cmp = CompareTo(divisor, mid, i);
        if (cmp > 0) low = mid + 1;
        else if (cmp < 0) high = mid - 1;
        else return mid;
      }
      return (cmp < 0) ? (mid - 1) : mid;
    }

    int CompareTo(BigInteger divisor, int mid, int i)
    {
      if (i >= 0) divisor.data[i] = mid;
      return AbsCompareTo(divisor * ((i >= 0) ? divisor : mid));
    }

    void AbsAdd(BigInteger x)
    {
      for (int i = 0; i < x.data.Count; i++)
      {
        data[i] += x.data[i];
        CarryUp(i);
      }
    }

    void AbsSubtract(BigInteger x)
    {
      for (int i = 0; i < x.data.Count; i++)
      {
        data[i] -= x.data[i];
        CarryDown(i);
      }
      Shrink();
    }

    void CarryUp(int n)
    {
      for (; data[n] >= Base; n++)
      {
        if (n == data.Count - 1) data.Add(data[n] / Base);
        else data[n + 1] += data[n] / Base;
        data[n] %= Base;
      }
    }

    void CarryDown(int n)
    {
      for (; data[n] < 0; n++)
      {
        data[n + 1]--;
        data[n] += Base;
      }
      Shrink();
    }

    void Shrink()
    {
      for (int i = data.Count - 1; i >= 0 && data[i] == 0; i--) data.RemoveAt(i);
      if (data.Count == 0) sign = 0;
    }

    public static bool operator ==(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return object.ReferenceEquals(y, null);
      return x.Equals(y);
    }

    public static bool operator !=(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return !object.ReferenceEquals(y, null);
      return !x.Equals(y);
    }

    public static bool operator <(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return !object.ReferenceEquals(y, null);
      return x.CompareTo(y) < 0;
    }

    public static bool operator >(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return false;
      return x.CompareTo(y) > 0;
    }

    public static bool operator <=(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return true;
      return x.CompareTo(y) <= 0;
    }

    public static bool operator >=(BigInteger x, BigInteger y)
    {
      if (object.ReferenceEquals(x, null)) return object.ReferenceEquals(y, null);
      return x.CompareTo(y) >= 0;
    }

    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      if (sign < 0) sb.Append('-');
      sb.Append((data.Count == 0) ? 0 : data[data.Count - 1]);
      for (int i = data.Count - 2; i >= 0; i--) sb.Append(data[i].ToString("D" + Len));
      return sb.ToString();
    }

    public override int GetHashCode()
    {
      int hash = sign;
      foreach (int n in data) hash ^= n;
      return hash;
    }

    public override bool Equals(object other)
    {
      if (other == null || GetType() != other.GetType()) return false;
      return Equals(other as BigInteger);
    }

    public bool Equals(BigInteger other)
    {
      return CompareTo(other) == 0;
    }

    public int CompareTo(BigInteger other)
    {
      if (object.ReferenceEquals(other, null)) return 1;
      if (sign < other.sign) return -1;
      if (sign > other.sign) return 1;
      if (sign == 0) return 0;
      return sign * AbsCompareTo(other);
    }

    int AbsCompareTo(BigInteger other)
    {
      if (data.Count < other.data.Count) return -1;
      if (data.Count > other.data.Count) return 1;
      for (int i = data.Count - 1; i >= 0; i--)
        if (data[i] != other.data[i])
          return (data[i] < other.data[i]) ? -1 : 1;
      return 0;
    }
  }
}

#12

这个是简化版，程序更短，其中的 BigInteger 类只实现了必要的方法：

using System;
using System.Text;
using System.Collections.Generic;

namespace Skyiv
{
  class Factorial
  {
    const int n = 100;
    
    static void Main()
    {
      BigInteger f = 1;
      for (int i = 2; i <= n; i++)
      {
        f *= i;
      }
      Console.WriteLine("{0}! = {1}", n, f);
    }
  }

  sealed class BigInteger
  {
    static readonly int Len = 9; // int.MaxValue = 2,147,483,647
    static readonly int Base = (int)Math.Pow(10, Len);

    int sign;
    List<int> data;

    BigInteger(long x)
    {
      sign = (x == 0) ? 0 : ((x > 0) ? 1 : -1);
      data = new List<int>();
      for (ulong z = (x < 0) ? (ulong)-x : (ulong)x; z != 0; z /= (ulong)Base) data.Add((int)(z % (ulong)Base));
    }

    BigInteger(BigInteger x)
    {
      sign = x.sign;  // x != null
      data = new List<int>(x.data);
    }

    public static implicit operator BigInteger(long x)
    {
      return new BigInteger(x);
    }

    public static BigInteger operator +(BigInteger x, BigInteger y)
    {
      if (x == null || y == null) return null;
      if (x.AbsCompareTo(y) < 0) Swap(ref x, ref y);
      BigInteger z = new BigInteger(x);
      if (x.sign * y.sign == -1) z.AbsSubtract(y);
      else z.AbsAdd(y);
      return z;
    }

    public static BigInteger operator *(BigInteger x, BigInteger y)
    {
      if (x == null || y == null) return null;
      BigInteger z = 0;
      z.sign = x.sign * y.sign;
      z.data = new List<int>(new int[x.data.Count + y.data.Count]);
      for (int i = x.data.Count - 1; i >= 0; i--)
        for (int j = y.data.Count - 1; j >= 0; j--)
        {
          long n = Math.BigMul(x.data[i], y.data[j]);
          z.data[i + j] += (int)(n % Base);
          z.CarryUp(i + j);
          z.data[i + j + 1] += (int)(n / Base);
          z.CarryUp(i + j + 1);
        }
      z.Shrink();
      return z;
    }

    void AbsAdd(BigInteger x)
    {
      for (int i = 0; i < x.data.Count; i++)
      {
        data[i] += x.data[i];
        CarryUp(i);
      }
    }

    void AbsSubtract(BigInteger x)
    {
      for (int i = 0; i < x.data.Count; i++)
      {
        data[i] -= x.data[i];
        CarryDown(i);
      }
      Shrink();
    }

    void CarryUp(int n)
    {
      for (; data[n] >= Base; n++)
      {
        if (n == data.Count - 1) data.Add(data[n] / Base);
        else data[n + 1] += data[n] / Base;
        data[n] %= Base;
      }
    }

    void CarryDown(int n)
    {
      for (; data[n] < 0; n++)
      {
        data[n + 1]--;
        data[n] += Base;
      }
      Shrink();
    }

    void Shrink()
    {
      for (int i = data.Count - 1; i >= 0 && data[i] == 0; i--) data.RemoveAt(i);
      if (data.Count == 0) sign = 0;
    }

    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      if (sign < 0) sb.Append('-');
      sb.Append((data.Count == 0) ? 0 : data[data.Count - 1]);
      for (int i = data.Count - 2; i >= 0; i--) sb.Append(data[i].ToString("D" + Len));
      return sb.ToString();
    }

    int AbsCompareTo(BigInteger other)
    {
      if (data.Count < other.data.Count) return -1;
      if (data.Count > other.data.Count) return 1;
      for (int i = data.Count - 1; i >= 0; i--)
        if (data[i] != other.data[i])
          return (data[i] < other.data[i]) ? -1 : 1;
      return 0;
    }

    public static void Swap<T>(ref T x, ref T y)
    {
      T z = x;
      x = y;
      y = z;
    }
  }
}

#13

关于 BigInteger 的更多讨论，请参见以下文章：

浅谈 BigInteger 
http://www.cnblogs.com/skyivben/archive/2008/07/13/1241681.html

#14

硬调3.5框架中的biginteger

Type t = Type.GetType("System.Numeric.BigInteger, System.Core, Version=3.5.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089");
DynamicMethod dm = new DynamicMethod(string.Empty, typeof(string), new Type[] { typeof(int) }, true);
var il = dm.GetILGenerator();
var current = il.DeclareLocal(t);
var factor = il.DeclareLocal(typeof(int));
var exit = il.DefineLabel();
var condition = il.DefineLabel();
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Stloc_S, factor);
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Newobj, t.GetConstructor(new Type[] { typeof(int) }));
il.Emit(OpCodes.Stloc_S, current);
il.Emit(OpCodes.Br_S, condition);
il.MarkLabel(condition);
il.Emit(OpCodes.Ldloc_S, factor);
il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Bgt_S, exit);
il.Emit(OpCodes.Ldloc_S, factor);
il.Emit(OpCodes.Newobj, t.GetConstructor(new Type[] { typeof(int) }));
il.Emit(OpCodes.Ldloc_S, current);
il.Emit(OpCodes.Call, t.GetMethod("Multiply"));
il.Emit(OpCodes.Stloc_S, current);
il.Emit(OpCodes.Ldloc_S, factor);
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Add);
il.Emit(OpCodes.Stloc_S, factor);
il.Emit(OpCodes.Br_S, condition);
il.MarkLabel(exit);
il.Emit(OpCodes.Ldloca_S, current);
il.Emit(OpCodes.Call, t.GetMethod("ToString", Type.EmptyTypes));
il.Emit(OpCodes.Ret);
var fac = (Func<int, string>)dm.CreateDelegate(typeof(Func<int, string>));
//计算100的阶乘
Console.WriteLine(fac(100));

#15

来学习的

#16

顶

#17

tj le?

#18

up...

#19

up

#20

太牛啦 
值得学习！

#21

学习中

#22

的确有点难度，不多通过递归的话，可能有点麻烦

#23

mark

#24

恩，有点难度，顶一下吧

#25

学习。。。

#26

哥们。。怎么这么长呀。。Java好友有这样的类。。专门放置长类型的。。

#27

这是一个控制台的程序，输出的是科学计数法表示的数
class Program
    {
        public double  Factorial(int i)
        {
            if (i < 1)
            {
                i = 1;
                return i;
            }
            return i * Factorial(i - 1);
        }
        static void Main(string[] args)
        {
            Program p = new Program();
            Console.WriteLine(p.Factorial(100).ToString ());           
        }

就用递归就好了，干嘛考虑那么复杂

#28

学习了

#29

mark

#30

mark

#31

这个不错，学习了

#32

该回复于2009-09-01 10:42:18被版主删除

#33

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;
        } 
static void Main(string[] args)
        {
            uint[] arr = CalculateLargeNumber(100);
            string str = "";
            for (int i = arr.Length-1; i >=0 ; i--)
            {
                str += arr[i].ToString();
            }
            Console.WriteLine(str);
            Console.ReadKey();
        }

O(∩_∩)O哈哈~

#34

学习了      

#35

一起学习。好东西。

#36

学习一下，在算法上我很缺乏

#37

up

#38

跟我以前写过的大整数相乘是一样的~~

#39

该回复于2009-11-16 09:00:29被版主删除

#40

学习,收藏了

#41

http://blog.csdn.net/hikaliv/archive/2009/06/04/4242988.aspx
计算 10000！ 以内的所有阶乘，用字符串保存结果，我在此博文有引述

#42

恩，这个帖子好啊，呵呵

#43

我也不太清楚楚这个

#44

该回复于2009-07-21 10:21:20被版主删除

#45

。。——   最后的数值用字符串存储，长度不够撒，可以考虑用递归思想

#46

up

#47

递归就行了。例：

ulong Factorial(uint para)
{
    ulong uVal=1;
    if(para>1)
    {
      uVal=para* Factorial(para-1);
    }
    return uVal;
}

剩下的就是调用的事了，在输入结果时用.ToString()输出就行了。
楼上的各位仁兄搞那么复杂，窃以为没有必要。

#48

顶一下

#49

C++版本 自己改
#include <iostream> 
using namespace std; 
void main() 
{ 
int Data[40]; 
    int Digit; 
    int i,j,r,k; 
    int N; 
    for(i=1;i <40-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]>10) 
                    Digit++; 
                    Data[r+1] += Data[r]/10; 
                    Data[r] = Data[r]%10; 
                } 
            } 
        } 
        printf("%d! = ",i); 
        for(k=Digit;k>0;k--) 
        printf("%d",Data[k]); 
        printf("\n"); 
    } 
    system("pause"); 
} 

#50

说到阶乘，大家都关注于递归，为什么没有人关心优化呢？
10000！真的有必要计算10000次吗？花点心思，能优化很多地方的