将pascal代码改写为c ++,以便它可以尽可能高效地工作

问题描述 投票:-6回答:3

所以我在有Pascal代码的地方完成了此任务,我需要弄清楚结果如何。那不是问题,因为我知道pascal,但是我需要它在1秒或更短的时间内运行,数字最大为10 ^ 9。

readln(N);
counter:=0;
for i:=N-1 downto 1 do begin
    counter:= counter + 1;
    if N mod i = 0 then break;
end;
writeln(counter);

这是我的代码

#include <iostream>

using namespace std;

int main()
{
    int x;
    int counter = 0;
    cin>>x;
    for (int i = 2; i <= x; i++){
        if (x % i == 0){
            counter = x - x / i;
            break;
        }
    }
    cout<<counter;
    return 0;
}

但是它仍然不能完全获得最高分。

c++ pascal
3个回答
2
投票

重述问题:1)计算F = X的最大固有因子2)输出X-F

而不是直接搜索最大的适当因子,而是应用三个琐碎的优化(也许需要更高级的方法,但是首先看看三个琐碎的优化是否足够)。

A)查找S = X的最小因子大于1。输出X-(X / S)B)特例C)偶数的特殊情况

int largest_proper_factor(int X)
{
   if ( X % 2 == 0 ) return X/2;  // Optimize even

   // Note the add of .5 is only needed for non compliant sqrt version that
   // might return a tiny fraction less than the exact answer.
   int last = (int)(.5 + std::sqrt( (double) X )) );

   for ( int i=3; i<=last; i+=2 ) // big savings here because even was optimized earlier
   {
      if ( X % i == 0 ) return X/i;
   }
   return 1;  // special case for prime
}

0
投票

[10 ^ 9之类的数字通常表示比赛问题,需要创造性的思考而不是快速的CPU ...

请参阅N mod i = 0表示N可被i整除。因此,循环会在N与其除数之一(可能加一...对其进行检查)之间计数。哪一个仍然适合您。


-1
投票

好吧,我得到了我想要的结果:

#include <iostream>
using namespace std;
int main()
{
    int x;
    int counter = 0;
    cin>>x;
    for (int i = 2; i <= x; i++){
        if (x % i == 0){
            counter = x - x / i;
            break;
        }
        if (x / 4 == i){
            i = x - 1;
        }
    }
    cout<<counter;
    return 0;
}

谢谢所有帮助我的人:)

© www.soinside.com 2019 - 2024. All rights reserved.