时间戳

首页 > 解决方案 > 使阶乘程序更快？

c++ - 使阶乘程序更快？

问题描述

我一直在尝试将此提交到一个有编程课程的网站，但法官一直告诉我这个程序执行时间太长：/

问题陈述：

编写一个程序，从标准输入中读取一个非负整数n，计算十进制数和十进制中的个数n!，并将结果写入标准输出。在输入的第一行有一个 integer D (1≤D≤30)，表示要考虑的案例数。对于每个条目的情况。您的程序应该在单独的行上打印两个数字（由一个空格分隔）：n!十进制系统中的十位和个位。

输入输出：

输入 输出
2
1 0 1
4 2 4 
#include <iostream>

using namespace std;

int d,n;

int main()
{
    cin>>d;
    for(int i=0; i<d; i++)
    {
        cin>>n;
        int silnia = 1;
        for(int j=n; j>1; j--)
        {
            silnia=silnia*j;
        }
        if(silnia == 1) cout<<0<<" "<<silnia<<"\n";
        else cout<<(silnia/10)%10<<" "<<silnia%10<<"\n";
    }
    return 0;
}

标签： c++optimizationfactorial

解决方案

您可以摆脱内部循环，因为n! == (n - 1)! * n：

  cin >> d;

  int factorial = 1;

  cout << 0 << " " << 1 << "\n";

  for (int i = 1; i < d; ++i) {
    /* we operate with last two disgits: % 100 */
    factorial = (factorial * i) % 100;

    cout << factorial / 10 << " " << factorial % 10 << "\n";
  }

编辑：另一个问题是

  silnia=silnia*j;

线。阶乘增长迅速：

  13! = 6227020800 > LONG_MAX (2147483647)

这就是为什么我们应该使用模算术：我们不保留阶乘本身（可能非常大），而是保留它的最后两个数字（注意% 100），保证在00..99范围内：

  factorial = (factorial * i) % 100;

甚至（如果i可以很大）

  factorial = (factorial * (i % 100)) % 100;

推荐阅读