算法题007 计算n的阶乘

阶乘的计算

阶乘的定义

　　n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

 

简单的程序代码（可以算较小的阶乘）

　　没有考虑变量表达范围，假设所得结果用long型表示。

　　这里需要注意的是0的阶乘应该是1.

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    int n = 0;
    long result = 0;

    while( cin >> n)
    {
        if(n > 0)
        {
            result = n;
            while(n > 1)
            {
                result *= (n-1);
                --n;
            }
        }
        else if (n == 0)
        {
            result = 1;
        }

        cout << result << endl;
    }

    return 0;
}

 

　　这个程序的主要问题就是long的选取，long型是4个字节，32位，因为是带符号的，能表示的范围最大不超过2的31次方，即不超过10的10次方。

　　即long型可以表示的数肯定是十进制下的10位数之内的。

　　而14的阶乘就已经是一个11位数了。

　　（事实上13的阶乘就已经超过了long的表示范围，因为13的阶乘的最高位是6，而2的31次方最高位是2。）

　　所以这个程序只能计算12以下的数的阶乘。

　　考虑过将数据类型进一步改为long double，得到的结果是科学计数法显示的，只有有限的有效数字，精度不高，并且当n进一步增大再次超过表示范围的时候呢？所以还是需要另外的处理办法。

 

 

大数阶乘运算　　

　　当n大于等于20时，因为运算结果超出了long型的表示范围，所以必须采取大数字的一般处理方法：用数组表示。

　　程序如下，自己写的，没有仔细研究文后的参考资料。　

#include <iostream>
using namespace std;



int main(int argc, char* argv[])
{
    int n = 0;
    int number[21] = {0};
    int bitCount = 0;//记录所用到的位数下标

    while( cin >> n)
    {
        bitCount = 0;
        if(n > 0)
        {
            //先把n用数组表示，0号元素为个位
            int copyOfN = n;

            for(int i = 0; copyOfN > 0; copyOfN/=10, ++i)
            {
                number[i] = copyOfN % 10;
                bitCount = i;

                //cout << "number: " << number[i] << endl;
                //cout << "bitCount: "<<bitCount <<endl;
            }

            //然后进行阶乘运算

            while( --n > 0)
            {
                int carry = 0;
                for(int i = 0; i<= bitCount; ++i)
                {
                    int temp = number[i] * n + carry;

                    number[i] = temp % 10;
                    carry = temp / 10;

                }
                while(carry > 0)
                {
                    //如果有多余的进位，则说明数组需要添加位数
                    //注意，这里由于把第二个乘数当做整体处理，而不是一位一位处理，所以进位可能也不只是一位
                    number[++ bitCount] = carry % 10;
                    carry /= 10;
                }
                
            }


            //最后输出运算结果
            for(int i = bitCount; i >= 0; --i)
            {
                cout << number[i];
            }
            cout << endl;
        }
        else if (n == 0)
        {
            cout << 1 << endl;
        }
        else
        {
            cout << "负数没有阶乘！" << endl;
        }



    }


    return 0;
}

　　还是需要细心一些的。

　　主要检查循环变量是否更新，对于进位的理解是否正确等。

　　结果用计算器验证过，并且在九度上提交通过：http://ac.jobdu.com/problem.php?pid=1067

 

其他参考资料

　　大数运算（采用数组模拟）：

http://www.cnblogs.com/dolphin0520/archive/2011/07/16/2108006.html

http://www.cnblogs.com/yuzhaoxin/archive/2011/11/19/2205221.html

http://confach.cnblogs.com/archive/2005/07/14/192703.html

http://www.cnblogs.com/lsx54321/archive/2012/07/20/2601618.html

http://www.cnblogs.com/phinecos/archive/2009/10/06/1578411.html