число N можно представить в виде 2 квадратов?, циклы Опции

[DruiD]

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

Сообщение отредактировано: DruiD - 5.10.2006 19:26

[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 - это заданное число.

Сообщение отредактировано: мисс_граффити - 5.10.2006 21:56

[Lapp]

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

.. до бесконечности . Да любая сумма квадратов одинаковой четности сразу выпадает..

что-то типа

Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка 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]

Во-первых, в условии нет указания, что одно из чисел не должно быть нулем, так что проверка 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

[мисс_граффити]

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

1.

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

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

оптимизировать можно до бесконечности... не спорю.
если условие поставленно именно так ("можно ли представить", а не "как можно представить"), по-хорошему, надо выскакивать из цикла после обнаружения первой же пары чисел.

Сообщение отредактировано: мисс_граффити - 6.10.2006 20:20

[volvo]

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

[мисс_граффити]

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

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

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

[Lapp]

Я всегда считал (как меня учили), что натуральные числа начинаются с единицы. Видимо, я недопрочел условие задачи.
Но я не хочу сказать, что решение неправильное, просто в таких задачах мне всегда интересно сделать минимальный код, выглядящий красиво - вот я и повелся.. Правда, оптимизация часто этому противоречит.
Но, согласись, что с точки зрения использования циклов решение с перебором квадратов все же предпочтительнее..

[мисс_граффити]

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

с этим я не спорю
просто как-то задели 2 необоснованные претензии... решила прояснить ситуацию.

[мисс_граффити]

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

ой.... оно мало того, что не необходимое, так еще и не достаточное
21/4=5 ост.1
1+20
4+17
9+12
16+5

[volvo]

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

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

[мисс_граффити]

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

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

вот и я о том, что никакое.
21 под это условие подходит (остаток, как положено), а представить не получается

[volvo]

Sorry, это касаемо только ПРОСТЫХ нечетных чисел... Теорема Ферма, понимаешь

Теорема 2. Для того чтобы нечетное простое число было представимо в виде суммы двух квадратов, необходимо и достаточно, чтобы оно при делении на 4 давало в остатке 1.