階乘的增長和解決方案

2019-11-17 02:17:03

字體：大中小

來源：轉載

供稿：網友

階乘的增長和解決方案

階乘的增長

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

下面以一段代碼測試下：

int total = 1;            for (int i =

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

結果如下：

可以發現，在17就明顯出問題了，再仔細觀察，在14的時候也有問題，14的階乘居然沒有13的階乘大。我們再用C#的checked關鍵字驗證一下，發現運算到13的時候就出現溢出了。

大家都知道“指數爆炸”，在int類型的取值范圍內，我們取2的指數最多可以取到30，但是階乘最多只能取到12。可見，階乘的增長比指數快多了。在網上找了一張各個函數增長率的圖，如下：

大整數階乘的解決

乘法本質上是加法運算，回顧我們小學的知識。被乘數乘上乘數就是乘數的各位依次與被乘數相乘再求和。例如：11*11=10*11+1*11。這樣我們就可以將大數的乘法化為小數的乘法與加法。只要乘數不大于int的最大值的九分之一即可（超過九分之一則會發生溢出）。這樣就可以利用乘法計算階乘了。

代碼

下面是我所寫的乘法類，代碼較簡單，關鍵部分有注釋，就不詳細解釋了。

/// <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）。在此就不提供代碼實現了。

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