1

Задача: Дано натуральное число 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;
}
1
  • 2
    return x,y; - а что ж вы только y возвращаете? :) Вы вообще-то учебник читали?
    – Harry
    18 янв 2021 в 7:10

3 ответа 3

8

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

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);
}
8
  • 1
    И еще тут нет лишнего вызова pow для расчета квадрата. 18 янв 2021 в 7:44
  • @ARHovsepyan А еще можно вообще на возведении в квадрат сэкономить :) - см. дополнение.
    – Harry
    18 янв 2021 в 8:53
  • можно отбросить некоторые случаи сразу без перебора
    – TigerTV.ru
    18 янв 2021 в 9:56
  • 1
    @TigerTV.ru Ну да, вы правы... но это уже в определенном смысле не программная оптимизация , а оптимизация самого алгоритма :) Которая, впрочем, обычно наиболее существенная.
    – Harry
    18 янв 2021 в 10:50
  • 1
    @TigerTV.ru Так я и не возражаю :) Что я мог - сделал. Вы можете больше - you are welcome! Покажите, как решать задачу с использованием материала, на который вы ссылаетесь - это ваша находка, ваше решение - напишите его.
    – Harry
    18 янв 2021 в 12:38
4

Ну если просто починить ваш код, без улучшений, то для начала вы не можете вернуть два числа 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. Так же лишние операции умножения были убраны.

8
  • 1
    А смысл перебора x до num? До корня - за глаза, а из симметрии задачи - до корня от половины. Да и какой смысл во вложенном цикле?
    – Harry
    18 янв 2021 в 7:21
  • @Harry пожалуйста читайте внимательней. "Ну если просто починить ваш код, без улучшений". Вы правда думаете, что я так написал просто потому, что не догадываюсь как сделать лучше? 18 янв 2021 в 7:22
  • Спасибо большое, заработало, ещё и узнал как возвращать два числа по ссылкам)
    – ktep222
    18 янв 2021 в 7:22
  • Просто если вы учите, то имеет смысл убирать не только неверный синтаксис, но и учить решать задачи хотя бы на ноготь мизинца оптимальнее, чем самый тупой подход. Это - тоже обучение. В том, что вы не дурак, я как-то не сомневаюсь, но почему вы опускаетесь в ответах до уровня спрашивающего без попыток подтянуть его к своему уровню хоть немного - не понимаю... Вы показываете, как правильно держать микроскоп при забивании гвоздей, как не пораниться осколками стекла и т.п. - но не показываете ему молоток...
    – Harry
    18 янв 2021 в 7:27
  • @Harry спасибо что разъяснили конечно, но я дал ответ, автору этот ответ помог. У меня нет времени учить кого-то, когда я сам еще учусь. Но только не учите меня, как давать ответы. Я сам все прекрасно понимаю, но сейчас я решил ответить сухо. 18 янв 2021 в 7:29
2

Простой перебор основанный на формуле (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";
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.