优化大乘法模C++

我想让我的程序能够更快地处理大数乘模乘法。这是我当前的代码：优化大乘法模C++

#include <iostream> 
#include <stdio.h> 

using namespace std; 

int main() 
{ 
    long multiply = 1; 
    char x; 
    while ((x = getchar()) != '\n') 
    { 
     multiply = (multiply*(x-64))%26; 
    } 
    if (multiply < 10) 
     printf("0%d\n", multiply); 
    else 
     printf("%d\n", multiply); 
    return 0; 
}

来源

2015-09-17 Luis V

（首先，我得到一个警告，因为你使用符号%d打印long，也许你可以只使用int，它不会让因为最高值的差是26.）

我想你可以通过使用无符号整数类型来提高速度，因为modulo对于无符号整数有点简单。（难以确定只是从看生成的组件... https://goo.gl/LAc42f）

来源

2015-09-17 02:12:43

我做了更正，并将其更改为unsigned int，但我仍然超出了时间限制。我不知道这是否真的是速度，或者是否让我上传程序时导致程序冻结。 –

我想你可以摆脱'iostream'包括？ iiuc有一些静态初始化的东西，当你包含这个头文件时会被添加到你的程序中。但在这里应该是非常小的...什么时间限制？ –

为什么你读到“\ n”？你确定他们给你的输入是“\ n”吗？我没有在声明中看到。我想它说第一行...嗯... –

我的猜测是getchar是你的瓶颈。您可以尝试在同一时间在更大的块阅读：

#include <cstdio> 
#include <cctype> 

#define BUFFER 2048 
#define OFFSET ('A' - 1) 
#define MODULUS 26 

using namespace std; 

int main() 
{ 
    char buffer[BUFFER]; 
    int count, done = 0, multiply = 1; 
    while (!done && (count = fread(buffer, sizeof(char), BUFFER, stdin))) 
    { 
     for (int i = 0; i < count; i++) 
     { 
      if (isupper(buffer[i])) 
      { 
       multiply *= (buffer[i] - OFFSET); 
       multiply %= MODULUS; 
      } 
      else 
      { 
       done = 1; 
       break; 
      } 
     } 
    } 
    printf("%02d\n", multiply); 
    return 0; 
}

而且固定了printf和去除幻数。它适用于测试用例。值得注意的

一个项目，如果模运算后得到的结果为零，那么就在持续没有意义的，因为你的产品永远是后为零，所以你可以做一个快捷方式有：

#include <cstdio> 
#include <cctype> 

#define BUFFER 2048 
#define OFFSET ('A' - 1) 
#define MODULUS 26 

using namespace std; 

int main() 
{ 
    char buffer[BUFFER]; 
    int count, done = 0, multiply = 1; 
    while (!done && multiply && (count = fread(buffer, sizeof(char), BUFFER, stdin))) 
    { 
     for (int i = 0; multiply && i < count; i++) 
     { 
      if (isupper(buffer[i])) 
      { 
       multiply *= (buffer[i] - OFFSET); 
       multiply %= MODULUS; 
      } 
      else 
      { 
       done = 1; 
       break; 
      } 
     } 
    } 
    printf("%02d\n", multiply); 
    return 0; 
}

阅读块和快捷方式优化可能是你需要超过时间限制。

来源

2015-09-17 03:12:42

优化大乘法模C++

回答

相关问题