Задача
Найдите все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.
Входные данные
Одно натуральное число $n$ $( n \leqslant 10000)$.
Выходные данные
Выведите в одной строке в возрастающем порядке все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 5 | 5 |
| 2 | 10 | 5 10 |
| 3 | 13 | 5 10 13 |
| 4 | 20 | 5 10 13 17 20 |
| 5 | 30 | 5 10 13 17 20 25 26 29 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cmath> using namespace std; bool check(int n) { for (int i = 1; i * i < n; i++) // перебор всех i { double j = sqrt (n - i * i); if ((j == floor(j)) and (j != i)) // проверка j целое или дробное { return true; // комбинация найдена - возвращаем true } } return false; // комбинация не найдена - возвращаем false } int main() { int n; cin >> n; // считываем число, до которого будем искать for (int k = 5; k <= n; k++) // проверка для каждого k if (check(k)) cout << k << " "; return 0; } |
Решение
Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.
Ссылки
Условие задачи на e-olymp
Код программы на ideone
Очень странное решение.
Если вы выбрали первое число i и знаете результат — n, то зачем же решать уравнение перебором всех j?
Спасибо за комментарий. Исправила
Нормально.
Только удалите j = 0; и описывайте переменные при их первом использовании если это возможно j = sqrt (n - i * i);. Во всяком случае, как можно ближе к их первому упоминанию.
Да!
Еще один момент. Методически верно было бы cделать так, чтобы функция не сама печатала, а выводила логическое значение — представимо или нет. Тогда это действительно будет функция проверки, которую можно использовать не только для печати. По такому принципу построены все функции стандартной библиотеки. Например функция возвращает синус угла, а не печатает его.
Я попробую сделать подробный разбор, поскольку задача в сто раз интереснее, чем кажется на первый взгляд.