同一算法的 C++ 和 Python 版本给出不同的结果

C++ and Python version of the same algorithm giving different result

以下代码是一个算法,用于确定整数三角形的数量,其中最大边小于或等于 MAX,并且中位数为整数。 Python 版本有效,但对于更大的 N 来说太慢了,而 C++ 版本要快得多,但没有给出正确的结果。

当MAX为10时,C++和Python都是return 3.

当MAX为100时,Python returns 835 and C++ returns 836.

当MAX为200时,Python returns 4088 and C++ returns 4102.

当MAX为500时,Python returns 32251 and C++ returns 32296.

当MAX为1000时,Python returns 149869 and C++ returns 150002.

这是 C++ 版本:

#include <cstdio>
#include <math.h>

const int MAX = 1000;

int main()
{
    long long int x = 0;
    for (int b = MAX; b > 4; b--)
    {
        printf("%lld\n", b);
        for (int a = b; a > 4; a -= 2){
            for (int c = floor(b/2); c < floor(MAX/2); c+=1)
            {
                if (a+b > 2*c){
                    int d = 2*(pow(a,2)+pow(b,2)-2*pow(c,2));
                    if (sqrt(d)/2==floor(sqrt(d)/2))
                        x+=1;
                }
            }
            }
    }
    printf("Done: ");       
    printf("%lld\n", x);
}

这是原始 Python 版本:

import math

def sumofSquares(n):
    f = 0
    for b in range(n,4,-1):
        print(b)
        for a in range(b,4,-2):
            for C in range(math.ceil(b/2),n//2+1):
                if a+b>2*C:
                    D = 2*(a**2+b**2-2*C**2)
                    if (math.sqrt(D)/2).is_integer():
                        f += 1
    return f

a = int(input())
print(sumofSquares(a))
print('Done')

我对 C++ 不太熟悉,所以我不知道是什么原因导致的(可能是溢出错误?)。

当然,欢迎对算法进行任何优化!

看来问题可能出在这里:

(sqrt(d)==floor(sqrt(d))) 

问题是您的 c(python 中的 C)变量的范围不匹配。为了使它们等同于您现有的 C++ 范围,您可以将 python 循环更改为:

for C in range(int(math.floor(b/2)), int(math.floor(n/2))):
    ...

要使它们等同于您现有的 python 范围,您可以将 C++ 循环更改为:

for (int c = ceil(b/2.0); c < MAX/2 + 1; c++) {
    ...
}

根据哪个循环最初是正确的,这将使结果匹配。