Модуль: Математическая шкатулка_Обучение


19. TUZ_2-19 Сумма двух квадратов


TUZ_2-19 Сумма двух квадратов

TUZ_2-19 Сумма двух квадратов
Дано натуральное число n, и требуется найти два натуральных числа, сумма квадратов которых равна n.
Например, если n равно 145, то ответом будет пара чисел (12, 1).
Если есть несколько ответов, то следует выбрать ответ с наибольшим максимальным числом.
Например, для n = 50 есть два возможных ответа: (7, 1) и (5, 5). Поскольку 7 больше 5, правильный ответ: (7, 1).
Ваша задача: написать функцию, которая принимает положительное целое число n и возвращает два числа, сумма квадратов которых равна n.
Если таких чисел нет, функция должна вернуть None.
В табл. 2.19 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.19. Некоторые ожидаемые результаты для задачи суммы двух квадратов
n Ожидаемый результат
50 7,1
145 12, 1
1480 38, 6
540 None

Алгоритм
.Алгоритм находит основания второй степени, сначала выбирая максимальное значение для первого основания, а затем проверяя все значения- кандидаты для второго основания. Если значение-кандидат для второго основания дает пару оснований, удовлетворяющих условиям, то функция возвращает эту пару. Вот подробное описание шагов алгоритма.
1. Принимается целое положительное число n.
2. Вычисляется максимальное значение первого основания как квадратный корень из половины числа n.
3. Создается набор возможных значений для второго основания от 1 до значения первого основания.
4. Перебираются возможные значения второго основания.
5. Для каждого возможного значения второго основания вычисляется разность между n и квадратом второго основания.
6. Вычисляется квадратный корень разности.
7. Проверяется равенство квадрата корня разнице.
8. Если равно, то возвращается пара оснований, сумма квадратов которых равна n.
9. Если такой пары не существует, возвращается None.
 

Предложенный алгоритм можно "усовершенствовать".
Для этого достаточно разбить все натуральные числа на четыре группы (используя остатки по модулю 4)
Не трудно вспомнить, что:
  • если n - четное,  то n2 кратно 4
  • если n - нечётное, то n2 по модулю 4 имеет остаток равный 1
Пусть Х=А2+В2, тогда : 
  • если X  кратно 4, то  А и В должны быть чётными и Х//4=(А//2)2+(В//2)2
  • если Х сравнимо с 1 по модулю 4, то А и В имеют разную чётность 
  • если Х сравнимо с 2 по модулю 4, то А и В должны быть нечётными 
  • если X сравнимо с 3, то Х - нечётное, значит А, В числа разной чётности, а тогда А2+В2 по модулю 4 дает остаток 1.
    Значит, для чисел вида 4k+3 разложение в сумму квадратов невозможно
Возможны и дальнейшее исследование внутренних случаев.
Для получения "целого" квадратного корня можно использовать метод isqrt() библиотеки math


time 10000 ms
memory 256 Mb

Комментарий учителя

     

Обсуждения (0)
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Решения (0)

Решения:

Нет доступных решений