Помощь - Поиск - Пользователи - Календарь
Полная версия: число N можно представить в виде 2 квадратов?
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
DruiD
Дано число n . Возможно ли записать его в виде суммы 2 квадратов натуральных чисел? blink.gif
volvo
Цитата
Любое натуральное число, дающее в остатке 1 при делении на 4, можно представить в виде суммы двух квадратов.
Проверяй, подходит ли данное тебе число под это условие...
мисс_граффити
я думаю, тут задача на другое...
именно на циклы - то есть на перебор.
кроме того, условие достаточное, но не необходимое. (у нас же не сказано, что числа разные. так что 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
Цитата(мисс_граффити @ 5.10.2006 22:54) *

кроме того, условие достаточное, но не необходимое. (у нас же не сказано, что числа разные. так что 8 ...
ряд можно продолжить

.. до бесконечности yes2.gif . Да любая сумма квадратов одинаковой четности сразу выпадает..
Цитата(мисс_граффити @ 5.10.2006 22:54) *

что-то типа

Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка b на равенство нулю не нужна.
Во-вторых, проверка типа real на равенство нулю не годится... sad.gif
Я бы был проще и вообще постарался избежать извлечений корня. Типа так:
Код
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.

Думаю, остается еще громадный простор для полета мысли.. smile.gif
volvo
Цитата
Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка 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
мисс_граффити
Цитата(lapp @ 6.10.2006 7:02) *

Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка b на равенство нулю не нужна.
Во-вторых, проверка типа real на равенство нулю не годится... sad.gif

1.
Цитата
Возможно ли записать его в виде суммы 2 квадратов натуральных чисел?

blink.gif ноль - это натуральное число?!
в срочном порядке ищу учебник по математике за 5 класс...
2. опять же - всегда была уверена, что разность 2 целых чисел есть целое число....

оптимизировать можно до бесконечности... не спорю.
если условие поставленно именно так ("можно ли представить", а не "как можно представить"), по-хорошему, надо выскакивать из цикла после обнаружения первой же пары чисел.
volvo
Юля, не торопись искать этот учебник. В русской математической школе 0 - НЕ является натуральным числом. А во французской, например, 0 - такое же натуральное число, как и 1... (Хотя это, по-моему, уже выходит за пределы обсуждения даной темы)...
мисс_граффити
Цитата(volvo @ 6.10.2006 21:44) *

Юля, не торопись искать этот учебник. В русской математической школе 0 - НЕ является натуральным числом. А во французской, например, 0 - такое же натуральное число, как и 1... (Хотя это, по-моему, уже выходит за пределы обсуждения даной темы)...

что-то с русской школой не все так однозначно...
"натуральные числа - это те числа, которые используются при счете".
правда, в другом месте: "целые числа - это натуральные числа, противоположные им и 0".

...что-то вместо того, чтобы отправить человека читать FAQ, развиваем огромное обсуждение. пора останавливаться smile.gif ответов на поставленный вопрос уже даже несколько.
Lapp
Я всегда считал (как меня учили), что натуральные числа начинаются с единицы. Видимо, я недопрочел условие задачи.
Но я не хочу сказать, что решение неправильное, просто в таких задачах мне всегда интересно сделать минимальный код, выглядящий красиво - вот я и повелся.. smile.gif Правда, оптимизация часто этому противоречит.
Но, согласись, что с точки зрения использования циклов решение с перебором квадратов все же предпочтительнее.. smile.gif
мисс_граффити
Цитата(lapp @ 7.10.2006 1:41) *

Но, согласись, что с точки зрения использования циклов решение с перебором квадратов все же предпочтительнее.. smile.gif

с этим я не спорю smile.gif
просто как-то задели 2 необоснованные претензии... smile.gif решила прояснить ситуацию.
мисс_граффити
Цитата(volvo @ 5.10.2006 20:30) *

Проверяй, подходит ли данное тебе число под это условие...

ой.... оно мало того, что не необходимое, так еще и не достаточное
21/4=5 ост.1
1+20
4+17
9+12
16+5
volvo
мисс_граффити blink.gif blink.gif А какое натуральное число при возведении в квадрат даст 17? или 20?

*Пошел за букварем...
мисс_граффити
Цитата(volvo @ 7.10.2006 14:36) *

мисс_граффити blink.gif blink.gif А какое натуральное число при возведении в квадрат даст 17? или 20?

*Пошел за букварем...

вот и я о том, что никакое.
21 под это условие подходит (остаток, как положено), а представить не получается sad.gif
volvo
Sorry, это касаемо только ПРОСТЫХ нечетных чисел... Теорема Ферма, понимаешь smile.gif

Цитата
Теорема 2. Для того чтобы нечетное простое число было представимо в виде суммы двух квадратов, необходимо и достаточно, чтобы оно при делении на 4 давало в остатке 1.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.