Форум «Всё о Паскале» _ Задачи _ число N можно представить в виде 2 квадратов?
Автор: DruiD 5.10.2006 23:21
Дано число n . Возможно ли записать его в виде суммы 2 квадратов натуральных чисел?
Автор: volvo 5.10.2006 23:30
Цитата
Любое натуральное число, дающее в остатке 1 при делении на 4, можно представить в виде суммы двух квадратов.
Проверяй, подходит ли данное тебе число под это условие...
Автор: мисс_граффити 6.10.2006 1:54
я думаю, тут задача на другое... именно на циклы - то есть на перебор. кроме того, условие достаточное, но не необходимое. (у нас же не сказано, что числа разные. так что 8=2^2+2^2 по условию задачи подходит, а по этому условию - нет, т.к. остаток равен 0. или даже 20 - остаток равен 0, но 4^2+2^2=20. или 26. или 40... ряд можно продолжить )
что-то типа
Код
for j:=1 to trunc(sqrt(i/2)) do begin b:=i-sqr(j); if ((b<>0) and (frac(sqrt(b))=0)) then fl:=true; {ну или сразу вывести что-то типа "можно представить"} end;
i - это заданное число.
Автор: lapp 6.10.2006 10:02
Цитата(мисс_граффити @ 5.10.2006 22:54)
кроме того, условие достаточное, но не необходимое. (у нас же не сказано, что числа разные. так что 8 ... ряд можно продолжить
.. до бесконечности . Да любая сумма квадратов одинаковой четности сразу выпадает..
Цитата(мисс_граффити @ 5.10.2006 22:54)
что-то типа
Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка b на равенство нулю не нужна. Во-вторых, проверка типа real на равенство нулю не годится... Я бы был проще и вообще постарался избежать извлечений корня. Типа так:
Код
var N,i,j:integer; begin Write('Number? ');ReadLn(N); for i:=1 to N do for j:=i to N do if N=i*i+j*j then WriteLn(N,' = ',i,'^2 + ',j,'^2'); WriteLn('Over'); ReadLn; end.
Код, конечно, крайне неоптимальный. Первое, что можно сделать - запоминать значение i*i. Затем - лучше ограничить циклы. Можно и квадраты запоминать в массив.. Вот первый шаг по оптимизации:
Код
var N,i,ii,j,m:integer; begin Write('Number? ');ReadLn(N); m:=N div 2+1; for i:=1 to m do begin ii:=i*i; for j:=i to m do if N=ii+j*j then WriteLn(N,' = ',i,'^2 + ',j,'^2'); end; WriteLn('Over'); ReadLn; end.
Думаю, остается еще громадный простор для полета мысли..
Автор: volvo 6.10.2006 14:41
Цитата
Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка b на равенство нулю не нужна
Ну, тогда и цикл
for i:=1 to m do begin ii:=i*i; for j:=i to m do if N=ii+j*j then WriteLn(N,' = ',i,'^2 + ',j,'^2'); end;
Лучше начинать не с 1 (по i), а с нуля, ибо если с 1-цы, то теряем представление, например, 9 = 0^2 + 3^2
Автор: мисс_граффити 7.10.2006 0:17
Цитата(lapp @ 6.10.2006 7:02)
Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка b на равенство нулю не нужна. Во-вторых, проверка типа real на равенство нулю не годится...
1.
Цитата
Возможно ли записать его в виде суммы 2 квадратов натуральных чисел?
ноль - это натуральное число?! в срочном порядке ищу учебник по математике за 5 класс... 2. опять же - всегда была уверена, что разность 2 целых чисел есть целое число....
оптимизировать можно до бесконечности... не спорю. если условие поставленно именно так ("можно ли представить", а не "как можно представить"), по-хорошему, надо выскакивать из цикла после обнаружения первой же пары чисел.
Автор: volvo 7.10.2006 0:44
Юля, не торопись искать этот учебник. В русской математической школе 0 - НЕ является натуральным числом. А во французской, например, 0 - такое же натуральное число, как и 1... (Хотя это, по-моему, уже выходит за пределы обсуждения даной темы)...
Автор: мисс_граффити 7.10.2006 1:41
Цитата(volvo @ 6.10.2006 21:44)
Юля, не торопись искать этот учебник. В русской математической школе 0 - НЕ является натуральным числом. А во французской, например, 0 - такое же натуральное число, как и 1... (Хотя это, по-моему, уже выходит за пределы обсуждения даной темы)...
что-то с русской школой не все так однозначно... "натуральные числа - это те числа, которые используются при счете". правда, в другом месте: "целые числа - это натуральные числа, противоположные им и 0".
...что-то вместо того, чтобы отправить человека читать FAQ, развиваем огромное обсуждение. пора останавливаться ответов на поставленный вопрос уже даже несколько.
Автор: lapp 7.10.2006 4:41
Я всегда считал (как меня учили), что натуральные числа начинаются с единицы. Видимо, я недопрочел условие задачи. Но я не хочу сказать, что решение неправильное, просто в таких задачах мне всегда интересно сделать минимальный код, выглядящий красиво - вот я и повелся.. Правда, оптимизация часто этому противоречит. Но, согласись, что с точки зрения использования циклов решение с перебором квадратов все же предпочтительнее..
Автор: мисс_граффити 7.10.2006 14:06
Цитата(lapp @ 7.10.2006 1:41)
Но, согласись, что с точки зрения использования циклов решение с перебором квадратов все же предпочтительнее..
с этим я не спорю просто как-то задели 2 необоснованные претензии... решила прояснить ситуацию.
Автор: мисс_граффити 7.10.2006 17:25
Цитата(volvo @ 5.10.2006 20:30)
Проверяй, подходит ли данное тебе число под это условие...
ой.... оно мало того, что не необходимое, так еще и не достаточное 21/4=5 ост.1 1+20 4+17 9+12 16+5
Автор: volvo 7.10.2006 17:36
мисс_граффити А какое натуральное число при возведении в квадрат даст 17? или 20?
*Пошел за букварем...
Автор: мисс_граффити 7.10.2006 17:42
Цитата(volvo @ 7.10.2006 14:36)
мисс_граффити А какое натуральное число при возведении в квадрат даст 17? или 20?
*Пошел за букварем...
вот и я о том, что никакое. 21 под это условие подходит (остаток, как положено), а представить не получается
Автор: volvo 7.10.2006 17:52
Sorry, это касаемо только ПРОСТЫХ нечетных чисел... Теорема Ферма, понимаешь
Цитата
Теорема 2. Для того чтобы нечетное простое число было представимо в виде суммы двух квадратов, необходимо и достаточно, чтобы оно при делении на 4 давало в остатке 1.