Помогите с задачей C++. Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2

Question

Задача: Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2. Есть главная функция, принимает N, и должна эту N прогнать через функцию coupleXY(int num). Подскажите как эти циклы сделать, что бы они находили x, y, где N = x^2+y^2.

#include <iostream>
#include <cmath>

using namespace std;

// Функция которая возвращает такие значения x и y, которые x^2+y^2 = num 
int coupleXY(int num)
{
    int x = 0;
    int y = 0;
    
    while((pow(x,2) + pow(y,2)) == num)
    {
        while(y<num)
        {
        if( (pow(x,2) + pow(y,2)) == num )
            {
            return x,y;
            }
        y++;
        }

    x++;
    }

    // return x,y;  
}

// Главная функция, принимает N, и вызывает функцию, выводя её результат
int main()
{
    int N, resultX, resultY;
    
    cout << "Set natural number N: ";
    cin >> N;
    resultX, resultY = coupleXY(N);
    cout<<"\nx^2+y^2 = N, if "<<endl;
    cout<<"x = "<<resultX<<endl;
    cout<<"y = "<<resultY<<endl;
    return 0;
}

Answer 1

Ну если просто починить ваш код, без улучшений, то для начала вы не можете вернуть два числа return x, y; их можно вернуть по ссылке:

void coupleXY(int num, int& x, int& y)

Потом первый цикл у вас должен идти пока x^2 + y^2 != num иначе у вас сразу завершается функция при первой же проверке.

Так же для ограничения x нужно добавить условие && x < num в первый цикл.

Внутри 1 цикла перед 2, нужно обнулять y для того, чтобы для нового x попробовать найти y.

И наконец если x и y будут равны num, то это значит, что x и y найдены не были и лучше будет приравнять их к -1, как сигнал, что они не были найдены.

Вот пример вашего кода:

void coupleXY(int num, int& x, int& y)
{
    x = 0;
    y = 0;

    while ((pow(x, 2) + pow(y, 2)) != num && x < num)
    {
        y = 0;
        while (y < num)
        {
            if ((pow(x, 2) + pow(y, 2)) == num)
            {
                return;
            }
            y++;
        }
        x++;
    }
    if (x == num && y == num) {
        x = -1;
        y = -1;
    }
}

Вот небольшая оптимизация кода выше:

void coupleXY(int num, int& x, int& y)
{
    x = 0;
    y = 0;
    int temp = 0;
    while (temp < num)
    {
        while (temp < num) {
            ++y;
            temp = x * x + y * y;
        }
        if (temp == num)
            return;
        ++x;
        y = 0;
        temp = x * x;
    }
    x = -1;
    y = -1;
}

Оптимизация состоит в том, что теперь если мы проходим не пока x < num и y < num, а пока x*x + y*y <= num. Так же лишние операции умножения были убраны.

Answer 2

Обычный перебор выглядит примерно так:

pair<int,int> coupleXY(int N)
{
    //for(int x = 0; 2*x*x <= N; ++x)  // Если можно 0
    for(int x = 1; 2*x*x <= N; ++x)    // Если 0 нельзя
    {
        int y = sqrt(N-x*x)+0.5;
        if (x*x+y*y == N) return make_pair(x,y);
    }
    return make_pair(-1,-1); //
}

int main()
{
    int N;
    cin >> N;
    auto v = coupleXY(N);
    if (v.first < 0) cout << "No solutions\n";
    else cout << v.first << "^2 + "
              << v.second << "^2 == " << N << endl;
}

Принимаем x <= y, тогда понятно, что максимальное значение x не может превышать sqrt(N/2). Второе значение искать перебором - долго, смысла нет, проще оценить корень и убедиться, что он [не]подходит.

В С++ возврата сразу двух значений из функции нет, это вам не Go, но можно возвращать их в виде структуры, или стандартного класса pair. Можно и через указатели/ссылки, но... ну вот не люблю я этот метод :) То, что делали вы - с запятой - как ни смешно, может компилироваться, но вот семантика тут совершенно иная - почитайте об операторе "запятая"...

Для ARHovsepyan :)

for(int x = 1, z = 1; 2*z <= N; ++x, z+=2*x-1)    // Если 0 нельзя
{
    int y = sqrt(N-z)+0.5;
    if (z+y*y == N) return make_pair(x,y);
}

Answer 3

Простой перебор основанный на формуле (n+1)^2 = n^2 + 2*n + 1, корень в цикле не вычисляется, также сразу отбрасываются варианты для которых нет решения:

#include <iostream>
#include <cmath>

std::pair<int,int> coupleXY(int N) {
    if (N & 1 && N % 4 != 1) return std::make_pair(0, 0);
    int x = 2 * (int)std::sqrt(N / 2);
    int y = x;

    for(int diff = N - x * x / 2; x > 0; ++diff) {
        if (diff > 0) {
            y += 2;
            diff -= y;
        } else if (diff < 0) {
            x -= 2;
            diff += x;
        } else {
            return std::make_pair(x / 2, y / 2);
        }
    }

    return std::make_pair(0, 0);
}

int main() {
    int N;
    std::cin >> N;
    auto v = coupleXY(N);
    if (v.first) {
        std::cout << v.first << "^2 + " << v.second << "^2 == " << N << std::endl;
    } else {
        std::cout << "No solutions\n";
    }
}

БЛОГ НА HUSL

Помогите с задачей C++. Дано натуральное число N. Определить, если это возможно, пару x,y таких натуральных чисел, что N = x^2+y^2

Ответы (3 шт):