Можно ли заданное натур. число М представить в виде суммы 2-х ква

← →
Опять я (2012-09-09 17:30) [0]

Можно ли заданное натур. число М представить в виде суммы 2-х квадратов натуральных чисел. Например 25=3^2+4^2?

Задача детская, но я не могу понять.

← →
Юрий Зотов © (2012-09-09 17:56) [1]

3, 4, 5, 6, 7...

← →
Опять я (2012-09-09 17:57) [2]

Помогите! Подтолкните к решению!

← →
Юрий Зотов © (2012-09-09 17:57) [3]

Правда, 4 = 2^2 + 0^2, поэтому 4 из этого ряда надо убрать.

← →
Опять я (2012-09-09 18:04) [4]

Вот получаем мы число 665 и что с ним делать?

← →
Юрий Зотов © (2012-09-09 18:14) [5]

> Опять я (09.09.12 17:57) [2]
> Помогите! Подтолкните к решению!

Дык... пример показывает, что в общем случае решения нет. То есть, не любое число можно представить таким образом.

А проверка "в лоб" простая. Имеем: X^2 + Y^2 = M, причем M известно. Надо найти пару X и Y, либо убедиться, что такой пары не существует.

Объявляем X:integer и Y:extended. Делаем цикл по X от нуля до TRUNC(SQRT(M)). На каждом витке цикла вычисляем Y:
Y = SQRT(M - X^2)
и проверяем Y на целочисленность. Если Y целое, то пара найдена, если цикл кончился - такой пары нет.

← →
Pavia © (2012-09-09 18:15) [6]

function Foo(n:Integer):Boolean; var i,j:Integer; begin result:=False; for i:=1 to бесконечность do for j:=1 to бесконечность do if i*i+j*j=n then result:=True; end;

> Вот получаем мы число 665 и что с ним делать?

передать в процедуру.

← →
Юрий Зотов © (2012-09-09 18:26) [7]

procedure TForm1.Button1Click(Sender: TObject); var M, X: cardinal; Y: extended; begin M := StrToInt(Edit1.Text); for X := 0 to Trunc(Sqrt(M)) do begin Y := Sqrt(M - X * X); if Y = Trunc(Y) then begin Caption := Format("%d^2 + %d^2 = %d", [X, Trunc(Y), M]); Exit end end; Caption := "Нет такой пары" end;

← →
Опять я (2012-09-09 18:40) [8]

Спасибо, понятно.

Нам задают какие-то странные задачи,

Вот:

напечатать все цифры числа 3^512

← →
Опять я (2012-09-09 18:41) [9]

Понятно, такое число не может вместить не один тип!
Даже Int64 или как его там в Pascal.

← →
Sha © (2012-09-09 18:51) [10]

> Опять я (09.09.12 18:41) [9]

умножение в столбик проходят в начальной школе

← →
Опять я (2012-09-09 18:56) [11]

Я бы сделал:

Result:= Power(3, 512);

Но это никуда не лезет.

В смысле столбиком?

← →
Юрий Зотов © (2012-09-09 19:02) [12]

> напечатать все цифры числа 3^512
> Понятно, такое число не может вместить не один тип!

Значит, надо подумать и найти другой способ. Например, можно использовать то, что число должно 512 раз делиться на 3, после чего должна получиться 1. Ну и признак делимости на 3 тоже может пригодиться: число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. И т.п.

← →
Inovet © (2012-09-09 19:03) [13]

> [11] Опять я (09.09.12 18:56)
> В смысле столбиком?

Всмысле, что не надо весь результат хранить, могли задать и 3^2^32  суть та же.

← →
Юрий Зотов © (2012-09-09 19:12) [14]

> Опять я (09.09.12 18:40) [8]
> Нам задают какие-то странные задачи,
> напечатать все цифры числа 3^512

Не странные, очень хорошие задачи. Развивают алгоритмическое мышление, а оно программисту необходимо.

← →
Pavia © (2012-09-09 19:12) [15]

> Понятно, такое число не может вместить не один тип!

Может. Называется массив.

← →
Опять я (2012-09-09 19:37) [16]

> Юрий Зотов © (09.09.12 19:12) [14]

Только не уходите! Пожалуйста! Вы мне очень нужны.

← →
Опять я (2012-09-09 19:39) [17]

Допустим дано число попроще: 2^5 = 32.

Зная число и степень - понятно как его получить.
Но не понятно что делать дальше!

procedure Proc; var i : LongWord; Res: LongWord; begin Res:= 1; For i:= 1 to 5 do Res:= Res * 2; Form1.Caption:= IntToStr(Res); // 32. end;

← →
Юрий Зотов © (2012-09-09 19:49) [18]

> Опять я (09.09.12 19:37) [16]

Только я один? Странно. А другие?

Например, Sha - ОЧЕНЬ сильный алгоритмист. Причем именно в задачах подобного рода, когда решение "в лоб" не прокатывает по памяти, по скорости и т.п. Очень советую к нему прислушиваться - он говорит не просто так, он подсказывает. Только в его подсказки вдуматься нужно.

← →
Юрий Зотов © (2012-09-09 19:58) [19]

> Опять я (09.09.12 19:39) [17]

Подсказали ведь, уже трое. Умножение столбиком надо делать, а результат хранить в массиве, каждый элемент которого содержит одну десятичную цифру.

То же самое мы делаем на бумаге - каждая цифра умножается на 3, начиная с младшей, а если идет перенос, то корректируются старшие цифры.

← →
Sha © (2012-09-09 20:14) [20]

> Опять я (09.09.12 19:39) [17]
> Зная число и степень - понятно как его получить.
> Но не понятно что делать дальше!

Вот так
procedure TMainForm.Button1Click(Sender: TObject); var a: TLong; i: integer; begin; SetLength(a,1); a[0]:=3; i:=1; repeat; a:=Mul(a,a); i:=i+i; until i>=512; //3^512 Memo1.Lines.Add(MulAsStr(a)); end;

получишь ответ:
19323349832288915105454068722019581055401465761603328550184537628902466746415537 00001793942978602935439008232929458611950515350910133294088409804047872863954256 05501337273994827780623224073723381210433996682422765917915046589858829952724365 41441

тебе осталось дописать 20-30 строчек

← →
DVM © (2012-09-09 20:51) [21]

>
> Опять я (09.09.12 17:30)
> Можно ли заданное натур. число М представить в виде суммы
> 2-х квадратов натуральных чисел. Например 25=3^2+4^2?

Следствие из теоремы Ферма-Эйлера:

Натуральное число представимо в виде суммы двух квадратов тогда и только тогда, когда любое простое число вида 4k + 3 входит в его разложение на простые множители в чётной степени.

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0_%E2%80%94_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0

← →
Опять я (2012-09-09 20:58) [22]

Вот еще одна:

Написать программу, которая считывает натур. числа m и n и находит n/m с точностью до 25 знаков, m и n <=1000

Опять не понять. :\.
Задачи по типу: "Создайте телефонную базу" - я решаю, а эти мозги мои выносят.

← →
Юрий Зотов © (2012-09-09 21:04) [23]

> Опять я (09.09.12 20:58) [22]

Тоже столбиком, только уже деление.

← →
Sha © (2012-09-09 21:07) [24]

> Опять я (09.09.12 20:58) [22]

А это деление столбиком.
Все три задачи на умение писать элементарные циклы и немного думать.

← →
Sha © (2012-09-09 21:08) [25]

Юрий Зотов © (09.09.12 21:04) [23]

опередил )

← →
Логопед (2012-09-09 21:09) [26]

> Опять я (09.09.12 20:58) [22]

В школе бывал? Там учат делить без калькулятора.

← →
Inovet © (2012-09-09 21:10) [27]

Почему нет на сложение столбиком? Непорядок, надо с простого начинать.

← →
Давайте будем жрать! (2012-09-09 21:26) [28]

вам лишь бы издеваться… деление в столбик какой-то…

← →
Юрий Зотов © (2012-09-09 21:31) [29]

> Давайте будем жрать! (09.09.12 21:26) [28]

Дружище, смени ник, а? Ну пожалуйста!
Я жрать хочу, а в доме только кофе, а выходить из дома влом. Представь, каково мне твой ник видеть?
:o)

← →
Sha © (2012-09-09 21:34) [30]

вот-вот, он первый издевается

← →
Anatoly Podgoretsky © (2012-09-09 21:46) [31]

> напечатать все цифры числа 3^512

Нормальная задача, непростая конечно, но нормальная.
Хотя постановка плохая, не сказано в каком виде, ведь

1,932334983228891510545406872202e+244

тоже все

← →
Sha © (2012-09-09 21:54) [32]

> Anatoly Podgoretsky © (09.09.12 21:46) [31]

а так 1,9e+244 можно?

← →
Inovet © (2012-09-09 21:54) [33]

> [31] Anatoly Podgoretsky © (09.09.12 21:46)
> ведь
>
> 1,932334983228891510545406872202e+244
>
> тоже все

Это другое число

← →
Германн © (2012-09-09 21:56) [34]

> Inovet © (09.09.12 21:10) [27]
>
> Почему нет на сложение столбиком?

Зато и квадратного корня столбиком тоже нет. :)

← →
Юрий Зотов © (2012-09-09 22:02) [35]

> Sha © (09.09.12 21:34) [30]

Хех, а я его обломил - заказал жратву на дом, через полчаса привезут.
Нам не страшен серый волк, серый волк, серый волк...
:o)

← →
Inovet © (2012-09-09 22:21) [36]

> [35] Юрий Зотов © (09.09.12 22:02)
> заказал жратву на дом, через полчаса привезут.

Вот только б не писать стихи о пицце.:)

← →
Anatoly Podgoretsky © (2012-09-09 22:43) [37]

> Inovet (09.09.2012 22:21:36) [36]

Стихами сыт не будешь.

← →
брат Птибурдукова (2012-09-09 23:03) [38]

> Юрий Зотов © (09.09.12 21:31) [29]
только из уважения к Вам, милейший…

> Зато и квадратного корня столбиком тоже нет. :)
да не... способ есть, дед в своё время учил такому. другое дело, что при теперешнем распространении калькуляторовпользоваться им нет надобности. http://ru.wikipedia.org/wiki/Квадратный_корень

← →
брат Птибурдукова (2012-09-09 23:07) [39]

> Вот только б не писать стихи о пицце.:)
та ну, пицца… я вон казан лагмана сготовил, миску умял — куда той пицце. научиться б ещё к лагману настоящую дунганскую лапшу делать… :-\

← →
Германн © (2012-09-09 23:17) [40]

> да не... способ есть

Я знаю. Я про то что в задании этого нет. :)

← →
Inovet © (2012-09-09 23:19) [41]

> [38] брат Птибурдукова (09.09.12 23:03)
> что при теперешнем распространении калькуляторовпользоваться им нет надобности

Даже кубические извлекают без калькуляторов
http://husa.su/media/cache/be/9b/be9bf521b1a9ffb3c3582142196fc2ed.jpg

← →
Юрий Зотов © (2012-09-10 00:16) [42]

> брат Птибурдукова (09.09.12 23:03) [38]

Спасибо. Ник можно возвращать - оливье и шашлычок под бутылочку пивца были очень кстати.
:o)

> Inovet © (09.09.12 22:21) [36]

Не комильфо писать стихи о пицце -
И всем давно известно, даже в Ницце,
Что Всеволод Вишневский так сказал.

Но если голодом желудок мой томится -
Не все ль ему равно, чем утолиться?
И восемь пицц я, как одну, умял.

Теперь не естся мне, не пьется и не спится,
Битком набит живот и вновь томится.
Зачем? Зачем я на ночь ел ту пиццу?
Ведь знал, что так и будет. Вот тупица!

(Здесь должна быть последняя строчка с рифмой на -ал, -ял, но не могу ее придумать - объелся. Придумайте за меня, добрые люди, сами мы не местные!)
:o)

← →
Sha © (2012-09-10 00:19) [43]

> брат Птибурдукова (09.09.12 23:03) [38]

как знал, брал новый ник

← →
Inovet © (2012-09-10 00:58) [44]

Удалено модератором

← →
Sha © (2012-09-10 01:08) [45]

1 Салат увидел. Вилку в руки взял...

2 В дверь постучали. Я бумагу мял...

3 А завтра напишу о плове. Сегодня аппетит унял.

← →
Германн © (2012-09-10 01:22) [46]

> Юрий Зотов © (10.09.12 00:16) [42]
> оливье и шашлычок под бутылочку
> пивца были очень кстати.

Ну с оливье понятно нет проблем. Но шашлык небось изрядно остыл пока его везли?

← →
Sha © (2012-09-10 02:00) [47]

4 Мозг слипся, силясь мысли о халве прогнать.

← →
Германн © (2012-09-10 02:21) [48]

Удалено модератором

← →
Германн © (2012-09-10 02:55) [49]

Удалено модератором

← →
Inovet © (2012-09-10 03:00) [50]

Удалено модератором

← →
Опять я (2012-09-10 08:02) [52]

Я опять по 1-й задаче:

Там оказывается нужно найти не просто 1 комбинацию из возможных,
а ВСЕ комбинации.

Вот накатал код, но он почему то виснет.

Что не так?

P.S. Делалось в Delphi, но с учетом специфики Turbo Pascal"я.

{ Пояснение решения: Дана формула: X^2 + Y^2 = M. M - Известно, поэтому вычисляем Y по формуле: Y = SQRT(M - X^2). В цикле наращиваем счётчик X, до тех пор, пока Y не окажется целым числом, значит комбинация цифр удовлетворяющих условию - существует. } var Count : LongWord; { Кол-во комбинаций } Results: array [1..255] of { В Turbo Pascal"е нет динамических массивов, } record { поэтому возьмем размерность массива большую чем кол-во возможных комбинаций } X, Y: Integer; end; { Функция проверяет, есть ли уже такая комбинация цифр } function IsCombination(X, Y: LongWord): boolean; var i: LongWord; begin If (Count > 0) then For i:= 1 to Count do If ((Results[i].X = X) and (Results[i].Y = Y)) or { К примеру:(7^2 - 1^2) и } ((Results[i].Y = X) and (Results[i].X = Y)) then { (1^2 - 7^2) - считаются за 1 комбинацию. } begin Result:= True; Exit; end; Result:= False; end; { Функция проверяет цело ли вещественное число } function IsInt(const X: single): boolean; begin Result:= (X = Trunc(X)); end; { Функция проверяет, есть ли комбинация цифр, удовлетворяющих условию: X^2 + Y^2 = M. } function IsTrue(M: LongWord; var OutX, OutY: LongWord): boolean; var Y: single; X: LongWord; begin For X:= 1 to Trunc(Sqrt(M)) do { Начинаем с 1, т.к. числа должны быть натуральными. } begin { Ищем до Trunc(Sqrt(M)), т.к. по условию X^2 + Y^2 = M, X и Y получаются должны быть меньше корня M } Y:= Sqrt(M - Sqr(X)); If (Trunc(Y) <> 0) and { 0 - откидываем, т.к. натуральные числа начинаются с 1. } (IsInt(Y)) then { Y должен быть целым числом. } begin OutX:= X; OutY:= Trunc(Y); Result:= True; Exit; end; end; Result:= False; end; { Функция находит все комбинации цифр, удовлетворяющих условию: X^2 + Y^2 = M. } procedure ScanCombinations(M: LongWord); var X, Y: LongWord; begin Count:= 0; while IsTrue(M, X, Y) do If not IsCombination(X, Y) then { Если не нашли такую комбинацию - добавляем. } begin Inc(Count); Results[Count].X:= X; Results[Count].Y:= Y; end; end; { Использование } procedure TForm1.Button2Click(Sender: TObject); var i: LongInt; begin ListBox1.Clear; ScanCombinations(25); If (Count = 0) then begin ListBox1.Items.Add("NULL"); Exit; end; For i:= 1 to Count do with Results[i] do ListBox1.Items.Add(Format("%d : %d", [X, Y])); end;

← →
брат Птибурдукова (2012-09-10 08:45) [53]

этот пацак говорит на языках, продолжения которых не знает

function IsInt - негодная (в частности - Trunc здесь не к месту)

Зависает - значит while не завершается - ещё раз обдумать алгоритм. Если кажется верным - использовать отладку.

Однако стоит полностью переработать всё, без ненужных усложнений.
Например, ни к чему регистрировать найденные варианты - достаточно рассматривать только варианты, при которых Y не меньше X.
Кроме того, почти всё можно сделать в целых числах (оставить только Trunc(Sqrt(M)))

Задача уместится в десяток строчек.

> Опять я (10.09.12 08:02) [52]

Наступит момент, когда ты почувствуешь, что выучил язык и можешь думать на нем.
Еще через какое-то время тебе будет казаться, что эта фаза лишняя, и можно сразу писать программу.
Это очень опасно. Получить диагноз легко, а снять в три раза дороже.

← →
Опять я (2012-09-10 09:25) [56]

> брат Птибурдукова (10.09.12 08:45) [53]
>
> этот пацак говорит на языках, продолжения которых не знает

В смысле?

> MBo © (10.09.12 08:54) [54]
>
> function IsInt - негодная (в частности - Trunc здесь не
> к месту)

А как же тогда узнать, цело ли вещественное число?

← →
Опять я (2012-09-10 09:34) [57]

Переделал так, все работает:

{ Функция проверяет, есть ли комбинация цифр, удовлетворяющих условию: X^2 + Y^2 = M. } function IsTrue(M: LongWord): boolean; var Y: single; X: LongWord; begin For X:= 1 to Trunc(Sqrt(M)) do { Начинаем с 1, т.к. числа должны быть натуральными. } begin { Ищем до Trunc(Sqrt(M)), т.к. по условию X^2 + Y^2 = M, X и Y получаются должны быть меньше корня M } Y:= Sqrt(M - Sqr(X)); If (Trunc(Y) <> 0) and { 0 - откидываем, т.к. натуральные числа начинаются с 1. } (IsInt(Y)) then { Y должен быть целым числом. } begin If not IsCombination(X, Trunc(Y)) then begin Inc(Count); Results[Count].X:= X; Results[Count].Y:= Trunc(Y); Result:= True; Exit; end; end; end; Result:= False; end; procedure TForm1.Button2Click(Sender: TObject); var i: LongInt; begin ListBox1.Clear; Count:= 0; while IsTrue(50) do; If (Count = 0) then begin ListBox1.Items.Add("NULL"); Exit; end; For i:= 1 to Count do with Results[i] do ListBox1.Items.Add(Format("%d : %d", [X, Y])); end;

Выводит для, к примеру, 50 - (5, 5) и (1, 7)

>А как же тогда узнать, цело ли вещественное число?
Лучше вообще не узнавать - большинство целых чисел точно в single или double непредставимы, и будут на самом деле иметь вид 17.00000000000023 или 20.99999999999865. Заметь, что во втором случае Trunc обрежет до 20.

> Опять я (10.09.2012 09:25:56) [56]

С помощью Trunc не узнать.

Почти целочисленный вариант:
var X, Y, Temp, Sum: Integer; begin Sum := 3125 * 2197; X := 1; Y := Trunc(Sqrt(Sum)); while X <= Y do begin Temp := X * X + Y * Y; if Temp < Sum then Inc(X) else if Temp > Sum then Dec(Y) else begin Memo1.Lines.Add(Format("%d %d", [X, Y])); Inc(X); Dec(Y); end; end;

← →
Опять я (2012-09-10 09:52) [61]

Извините, если уже надоел, я только учусь у спецов.

Похожая задача.

Сколькими способами заданное натур. число N можно представить в виде 2-х кубов натур. чисел.

Я переделал формулу

Y:= LogN(3, M - (Sqr(X) * X));

Ввожу 35 - получаю - 2 и 3. Все правильно.
Ввожу 126 - получю - NULL. По идее должно возвратить - 1 и 5. Но почему то не пашет, почему?

Опять я (10.09.12 09:52) [61]

Ты где учишься ?

> while IsTrue(50) do;

Феерично.

> MBo © (10.09.12 09:48) [60]

Классно.

Из этого легко получить полностью целочисленный вариант,
если сделать 2 цикла, начинающихся с пифагоровой тройки,
и один крутить вверх, а другой вниз. При этом весь алгоритм
потребует 1 деление, 2 умножения и кучу сложений.

> Игорь Шевченко © (10.09.12 10:34) [63]
> > while IsTrue(50) do;
> Феерично.

Не, ну еще можно выжить. Вот если б было
while IsTrue(50) = True do;

> А как же тогда узнать, цело ли вещественное число?

http://delphimaster.net/view/15-1343205350/

← →
Опять я (2012-09-10 11:12) [67]

> Игорь Шевченко © (10.09.12 10:33) [62]
>
> Опять я (10.09.12 09:52) [61]
>
> Ты где учишься ?

В Нархозе. А что?

>
>
> Феерично.

Почему?
Функция будет в цикле пока находятся новые комбинации, как только они
иссякнут, то будет выход из цикла.

Подскажите по последней задаче.

> А что?

Здесь вроде не филиал твои задачи решать. Существуют преподаватели, коллеги по несчастью, etc.

← →
имя (2012-09-10 11:27) [69]

Удалено модератором

← →
Опять я (2012-09-10 11:29) [70]

> Игорь Шевченко © (10.09.12 11:21) [68]
>
>
> > А что?
>
>
> Здесь вроде не филиал твои задачи решать. Существуют преподаватели,
> коллеги по несчастью, etc.
>

Да у меня одногруппники вообще не бум-бум.
Мне им приходится помогать, а не им мне.

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

← →
Опять я (2012-09-10 11:30) [71]

Подскажите по последней задаче.

Только там вместо суммы квадратов - сумма кубов.
Поменял формулу на нужную, и программа перестала работать.

> Препод злой мужик, который любит дотошного докапываться,
> он не поможет.

Печально

Можно ли заданное натур. число М представить в виде суммы 2-х ква Найти похожие ветки