【每日编程-394期】哈工大上机题（三）

计算1！+2！+3！+……+n！的最后6位。已知n>=25时最后6位全0；

输入格式：

输入n

输出格式：

输出计算结果

输入样例：

32

输出样例：

940313

解决方法：

（1）算法的基本思想：

只需要计算后6位，且题目提供条件n>=25时后6位全0。

      我们需要手动对1！+2！+……+n！进行求和运算，运算过程中只需要对后6位进行运算，这就转化为了求n！的后6位的问题。

这里直接暴力计算的话会出现溢出的问题，所以我们程序来模拟手动加法、乘法运算，只计算后6位。

（2）代码实现：

#include 
using namespace std;

void factorial(int n, int *fac);    //求n的阶乘,只返回后6位结果
void getResult(int n, int *result); //返回阶乘和的后6位

int main(void)
{
    int result[6]; //存放结果
    int fac[6];
    int n;
    cout << "请输入n:" << endl;
    cin >> n;
    getResult(n, result);
    for (int i = 0; i < 6; i++)
    {
        cout << result[i];
    }
    cout << endl;
    system("pause");
    return 0;
}

void factorial(int n, int *fac)
{
    if (n >= 25)
    {
        for (int i = 0; i < 6; i++)
        {
            fac[i] = 0;
        }
    }
    else
    {
        int low;  //存放个位
        int high; //存放十位
        int temp = 1;
        //初始化fac
        for (int i = 0; i < 5; i++)
        {
            fac[i] = 0;
        }
        fac[5] = 1;
        int cf = 0;
        while (temp <= n)
        {
            int result_low[6];  //低位计算结果
            int result_high[6]; //高位计算结果
            low = temp % 10;
            high = (temp / 10) % 10;
            cf = 0;
            //先乘低位
            for (int i = 5; i >= 0; i--)
            {
                int t;
                t = fac[i] * low + cf;
                if (t >= 10)
                {
                    cf = t / 10;
                    result_low[i] = t % 10;
                }
                else
                {
                    result_low[i] = t;
                    cf = 0;
                }
            }
            cf = 0;
            //乘高位
            for (int i = 5; i >= 0; i--)
            {
                int t;
                t = fac[i] * high + cf;
                if (t >= 10)
                {
                    cf = t / 10;
                    result_high[i] = t % 10;
                }
                else
                {
                    result_high[i] = t;
                    cf = 0;
                }
            }
            //计算结果的个位
            fac[5] = result_low[5];
            cf = 0;
            for (int i = 4; i >= 0; i--)
            {
                int t = result_low[i] + result_high[i + 1] + cf;
                if (t >= 10)
                {
                    fac[i] = t % 10;
                    cf = t / 10;
                }
                else
                {
                    fac[i] = t;
                    cf = 0;
                }
            }
            temp++;
        }
    }
}

void getResult(int n, int *result)
{
    if (n >= 25)
    {
        getResult(24, result);
    }
    else
    {
        for (int i = 0; i < 6; i++)
        {
            result[i] = 0;
        }
        int fac[6];
        int cf = 0; //进位
        int temp = 1;
        while (temp <= n)
        {
            cf = 0;
            factorial(temp, fac);
            for (int i = 5; i >= 0; i--)
            {
                int t;
                t = result[i] + fac[i] + cf;
                if (t >= 10)
                {
                    result[i] = t % 10;
                    cf = t / 10;
                }
                else
                {
                    result[i] = t;
                    cf = 0;
                }
            }
            temp++;
        }
    }
}

编写一个程序，从键盘输入n个非零整数（0<n<1000），将这n个数中各位数字取出来相加，并按照从小到大的次序依次输出这些数字和。例如，497的各位数字和为20（4+7+9），1069的各位数字和为16（1+0+6+9）。< span=""></n<1000），将这n个数中各位数字取出来相加，并按照从小到大的次序依次输出这些数字和。例如，497的各位数字和为20（4+7+9），1069的各位数字和为16（1+0+6+9）。<>

输入格式：

输入的整数之间以空格分隔，输入为0时结束。

输出格式：

在一行上从小到大输出计算结果，整数之间用1个空格分隔，最后换行。

输入样例：

497 1069 68 71 137 0

输出样例：

8 11 14 16 20