C++ и Python версия одного и того же алгоритма, дающая разные результаты

Следующий код представляет собой алгоритм для определения количества целочисленных треугольников с наибольшей стороной, меньшей или равной MAX, которые имеют целочисленную медиану. Версия Python работает, но слишком медленно для больших N, в то время как версия C++ намного быстрее, но не дает правильного результата.

Когда MAX равен 10, C++ и Python оба возвращают 3.

Когда MAX равен 100, Python возвращает 835, а C++ возвращает 836.

Когда MAX равен 200, Python возвращает 4088, а C++ возвращает 4102.

Когда MAX равен 500, Python возвращает 32251, а C++ возвращает 32296.

Когда MAX равен 1000, Python возвращает 149869, а C++ возвращает 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++, поэтому я понятия не имею, что может произойти, что является причиной этого (может быть, ошибка переполнения?).

Конечно, любые оптимизации алгоритма приветствуются!

Источник

2 ответа

Решение

Проблема в том, что диапазон для вашего c (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++) {
    ...
}

В зависимости от того, какой цикл изначально верен, это приведет к совпадению результатов.

Источник

Некоторые проблемы могут быть здесь:

(sqrt(d)==floor(sqrt(d)))
Источник
Другие вопросы по тегам