сумма квадратов
Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain
можно ли заданное натуральное число М представить в виде суммы двух квадратов натуральных чисел? Какие буду предложения?
Тебе что нужно получить, готовый код или методику проверки суммы квадратов?
А если число само является квадратом натурального числа, то его можно представить как сумму самого себя и ноля?
Ноль ведь тоже является квадратом самого себя, как и единица.
А если число само является квадратом натурального числа, то его можно представить как сумму самого себя и ноля?
Ноль ведь тоже является квадратом самого себя, как и единица.
Поумнеть несложно, куда труднее от дури избавиться.
Decoder писал(а):Тебе что нужно получить, готовый код или методику проверки суммы квадратов?
А если число само является квадратом натурального числа, то его можно представить как сумму самого себя и ноля?
Ноль ведь тоже является квадратом самого себя, как и единица.
Ага, только 0 - это не натуральное число.
-
Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Тонко подмеченоazrael писал(а):Ага, только 0 - это не натуральное число.
Вообще не каждое натуральное число можно представить в виде суммы квадратов двух натуральных чисел. Сей факт достаточно интуитивен для тех, кто в школе решал много задачек на прямоугольные треугольники и знает, что такое Пифагорова тройка. Строго доказательства я сходу не приведу, но, я думаю, достаточно указать контрпример для того, чтобы утверждение было опровергнуто
Пример - число 3.1*1 + 1*1 = 2
1*1 + 2*2 = 5
Все остальные пары будут давать числа, большие, чем 5, так что и 3 (как и 4) представить в виде суммы квадратов нельзя.
Зато, господа, скажу по секрету, что всякое натуральное число (оказывается), можно представить в виде разности квадратов. Доказательство достаточно прозрачное. Нужно рассмотреть отдельно чётные и нечётные числа. Для чётных рассмотреть разность квадратов двух чисел X и X+2. Для нечётных рассмотреть разность квадратов двух чисел X и X+1. Раскрыть скобки и всё станет ясно.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Суть в том, что любой квадрат натурального числа - есть сумма арифметической прогрессии вида
1 + 3 + 5 + 7 + ... и т.д.
Т.е. если ряд чисел начинается с 1 и каждый следующий элемент ряда больше предыдущего на 2, то сумма чисел этого ряда всегда будет являться квадратом натурального числа. Это значение будет равно квадрату числа элементов прогрессии.
К примеру, если в прогрессии имеется 5 элементов: 1, 3, 5, 7, 9, то их сумма будет равна 5*5 = 25.
Следовательно, сумма квадратов двух натуральных чисел является суммой двух прогрессий.
Чтобы определить, является ли натуральное число суммой двух квадратов, нужно от исходного числа последовательно отнимать элементы прогресии, а полученную разницу проверять, является ли она квадратом целого числа или нет. Есть числа, которые можно разложить на сумму квадратов несколькими способами, например: число 50 можно представить как сумму 49+1 или как 25+25. По условию задачи достаточно всего одного варианта.
Таким образом, нужно написать лишь цикл, в котором значение исходного числа будет последовательно уменьшаться на элементы прогрессии 1, 3, 5, ... и так до тех пор, пока результат не окажется равен квадрату целого числа или не достигнет половины значения исходного числа.
1 + 3 + 5 + 7 + ... и т.д.
Т.е. если ряд чисел начинается с 1 и каждый следующий элемент ряда больше предыдущего на 2, то сумма чисел этого ряда всегда будет являться квадратом натурального числа. Это значение будет равно квадрату числа элементов прогрессии.
К примеру, если в прогрессии имеется 5 элементов: 1, 3, 5, 7, 9, то их сумма будет равна 5*5 = 25.
Следовательно, сумма квадратов двух натуральных чисел является суммой двух прогрессий.
Чтобы определить, является ли натуральное число суммой двух квадратов, нужно от исходного числа последовательно отнимать элементы прогресии, а полученную разницу проверять, является ли она квадратом целого числа или нет. Есть числа, которые можно разложить на сумму квадратов несколькими способами, например: число 50 можно представить как сумму 49+1 или как 25+25. По условию задачи достаточно всего одного варианта.
Таким образом, нужно написать лишь цикл, в котором значение исходного числа будет последовательно уменьшаться на элементы прогрессии 1, 3, 5, ... и так до тех пор, пока результат не окажется равен квадрату целого числа или не достигнет половины значения исходного числа.
спасибо други! Вариант с прогрессией мне очень понравился! Огромное спасибо!!!
WinMain, браво! Неординарное решение!