c++ - 需要您的意见 Project Euler Q 8

Question

有更好的方法吗？

http://projecteuler.net/problem=8

我添加了一个条件来检查数字是否 >6(消除小产品和 0)

#include <iostream>
#include <math.h>
#include "bada.h"
using namespace std;
int main()
{
    int badanum[] { DATA };
    int pro=0,highest=0;
    for(int i=0;i<=996;++i)
    {
        if (badanum[i]>6 and badanum[i+1] > 6 and badanum[i+2] >6 and badanum[i+3]>6 and badanum[i+4]>6)
        {
            pro=badanum[i]*badanum[i+1]*badanum[i+2]*badanum[i+3]*badanum[i+4];
            if(pro>highest)
            {
                cout << pro << " " << badanum[i] << badanum[i+1] << badanum[i+2] << badanum[i+3] << badanum[i+4] << endl;
                highest = pro;
            }
            pro = 0;
        }
    }
}

bada.h 只是一个包含 1000 位数字的文件。

#DEFINE DATA <1000 digit number>

http://projecteuler.net/problem=8

Answer 1

如果实际上减慢速度

• 导致 CPU 执行的并行管道分支
• 也如前所述，它会使结果无效
• 不管你的解决方案是否与它应该的相同(对于其他数字，它不能)

在算法方面你可以这样做:

1. 如果你有足够快的除法你可以降低计算量

   char a[]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450\0";
   
   int i=0,s=0,m=1,q;
   for (i=0;i<4;i++)
       {
       q=a[i  ]-'0'; if (q) m*=q;
       }
   for (i=0;i<996;i++)
       {
       q=a[i+4]-'0'; if (q) m*=q;
       if (s<m) s=m;
       q=a[i  ]-'0'; if (q) m/=q;
       }
   

2. 您还可以为 mul、div 操作创建一个表以提高速度(但并非在所有情况下都更快)

       int mul_5digits[9*9*9*9*9+1][10]={ 0*0,0*1,0*2, ... ,9*9*9*9*9/9 };
       int div_5digits[9*9*9*9*9+1][10]={ 0/0,0/1,0/2, ... ,9*9*9*9*9/9 };
       // so a=b*c; is rewritten by a=mul_5digits[b][c];
       // so a=b/c; is rewritten by a=div_5digits[b][c];
   

   • 当然不是值 0*0 而是必须添加中性值 = 1 !!!

   • 当然 values i/0 必须添加 neutral value = i !!!

     int i=0,s=0,t=1;
     for (i=0;i<4;i++)
         {
         t=mul_5digits[t][a[i  ]-'0'];
         }
     for (i=0;i<996;i++)
         {
         t=mul_5digits[t][a[i+4]-'0'];
         if (s<t) s=t;
         t=div_5digits[t][a[i  ]-'0'];
         }
     

AMD 3.2GHz、64 位 Win7、32 位 App BDS2006 C++ 上的运行时测量:

0.022ms classic approach
0.013ms single mul,div per step (produce false outut if there is none product > 0 present)
0.054ms tabled single mul,div per step (is slower for my setup)

附言。

所有代码改进都应进行衡量，以便您了解是否真的加快了速度。
因为对一个编译器/平台/计算机来说更快的东西对另一个编译器/平台/计算机来说可能更慢。
使用至少 0.1 毫秒的分辨率。
为此，我更喜欢使用 RDTSC 或 PerformanceCounter。