程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 階乘的增長和解決方案，階乘增長解決方案

階乘的增長和解決方案，階乘增長解決方案

編輯：C#入門知識

階乘的增長和解決方案，階乘增長解決方案

階乘的增長

許多程序設計的書上都有介紹階乘，我相信包括我在內的人都是看過即可，沒有深入的想過其他的問題。比如在整數的范圍內（以C#）為例，階乘究竟可以計算到多大。

下面以一段代碼測試下：

int total = 1;
            for (int i =

; i <= 20; i++)
            {
                total *= i;
                Console.WriteLine("{0}\t{1}",i,total);
            }

結果如下：

/// <summary> /// 乘法類,可用於計數小於Int32.MaxValue十分之一的乘法 /// </summary> public class Multiplication { #region Fields /// <summary> /// 保存乘法結果的數組 /// </summary> private int[] _result = new int[4]; /// <summary> /// 被乘數的最高位 /// </summary> private int _topDigit = 3; /// <summary> /// 最大的被乘數 /// </summary> public const int MaxMultiplier = Int32.MaxValue / 9; #endregion Fields #region Properties /// <summary> /// 獲取結果枚舉器,按從高位到低位 /// </summary> public IEnumerable<int> Result { get { return _result.Skip(_topDigit); } } #endregion Properties #region Public Methods #region Constructs /// <summary> /// 使用被乘數為1構造乘法類 /// </summary> public Multiplication() { //初始化為1 _result[_result.Length - 1] = 1; } /// <summary> /// 使用指定的被乘數構造乘法類 /// </summary> /// <param name="multiplicand">被乘數</param> public Multiplication(int multiplicand) : this() { Multiply(multiplicand); } #endregion Constructs #region Operators /// <summary> /// 重載乘法運算符 /// </summary> /// <param name="multiplication">乘法類</param> /// <param name="multiplier">乘數,不能大於Int32.MaxValue的九分之一</param> /// <returns>進行乘法運算後的乘法類</returns> public static Multiplication operator *(Multiplication multiplication, int multiplier) { return multiplication.Multiply(multiplier); } /// <summary> /// 將指定的被乘數隱式轉換為乘法類 /// </summary> /// <param name="multiplicand">被乘數</param> /// <returns>轉換後的乘法類</returns> public static implicit operator Multiplication(int multiplicand) { return new Multiplication(multiplicand); } /// <summary> /// 將乘法類顯式轉換為int /// </summary> /// <param name="multiplication">乘法類</param> /// <returns>轉換後的int</returns> public static explicit operator int(Multiplication multiplication) { int value = 0; int digit = 1; var result = multiplication._result; for (int i = result.Length - 1; i > multiplication._topDigit - 1; i--) { value += result[i] * digit; digit *= 10; } return value; } #endregion Operators /// <summary> /// 與指定的乘數進行乘法運算 /// </summary> /// <param name="multiplier">乘數,不能大於Int32.MaxValue的十分之一</param> /// <returns>進行乘法運算後的乘法類</returns> public Multiplication Multiply(int multiplier) { Contract.Assert(MaxMultiplier > multiplier); int digit = GetDigits(multiplier); //加上被乘數的位數 for (int i = _topDigit; i < _result.Length; i++) { int d = GetDigits(_result[i]); d += _result.Length - i - 1; //加上權的位數，比如100對應2位，1000對應3位 digit += d; } //擴寬一位,容納權值 digit += 1; //位數不夠，開始重新分配結果數組 if (digit > _result.Length) { var result = new int[digit]; //有效數字長度 int validLength = _result.Length - _topDigit; Array.Copy(_result, _topDigit, result, result.Length - validLength, validLength); _topDigit += digit - _result.Length; _result = result; } //進行運算 for (int i = _topDigit; i < _result.Length; i++) { _result[i] *= multiplier; } Carry(); return this; } #endregion Public Methods #region Private Methods /// <summary> /// 進位 /// </summary> private void Carry() { //從被乘數個數到最高位的前一位,依次進位 for (int i = _result.Length - 1; i > _topDigit - 1; i--) { int carry = _result[i] / 10; _result[i] = _result[i] % 10; _result[i - 1] += carry; } //在被乘數的最高位進位 for (int i = _topDigit - 1; ; i--) { int carry = _result[i] / 10; _result[i] = _result[i] % 10; if (0 != carry) { _result[i - 1] += carry; } else { break; } } UpdateTopDigit(); } /// <summary> /// 獲取數字的位數 /// </summary> /// <param name="number">數字</param> /// <returns>位數</returns> private int GetDigits(int number) { return (int)Math.Ceiling(Math.Log10(number)); } /// <summary> /// 更新最高位 /// </summary> private void UpdateTopDigit() { _topDigit = 0; for (int i = 0; i < _result.Length; i++) { if (_result[i] != 0) { _topDigit = i; break; } } } #endregion Private Methods }

使用方法也很簡單：

/// <summary>
        /// 計算階乘
        /// </summary>
        /// <param name="n">要計算的階乘</param>
        /// <returns>階乘的結果，數字從高位到低位</returns>
        static IEnumerable<int> Factrial(int n)
        {
            var mul = new Multiplication();
            for (int i = 2; i <= n; i++)
            {
                mul *= i;
            }

            return mul.Result;
        }

擴展

正如上面所說，只能計算不超過int.MaxValue九分之一的階乘，如果需要計算更大的階乘，就不能再直接將乘數的每位與被乘數相乘，而是需要進一步的細化，將乘數的每位依次與被乘數的每位相乘求和。例如：11x11=10*11+1*11=（10*10+10*1）+（1*10+1*1）。在此就不提供代碼實現了。

同樣的思路，也可將除法化為減法。