Пара задач с олимпиады

[ummasha]

Хотите информатическую?
Поменять местами значение 2 переменных, не используя дополнительную переменную или указатели

Я вспомнила, как это сделать (правда, не на Паскале).
Есть 2 переменные: А и В. Поменять их местами можно за 3 действия.
1) А:=А+В; А:=А xor В;
2) В:=А-В; В:= А xor В;
3) А:=А-В; А:=А xor В;

 

[Dr. Evil]

В Паскале это делается почти так же:

А:=А+В;
В:=А-В;
А:=А-В;

 

[ummasha]

Спасибо

 

[Vladimir_S]

Ах вы умницы оба - ну будет вам от Darkcosinus! Я, знаете ли, тоже с чего-то подобного начал - и понеслось: a+b - нельзя (вдруг числа в формате BYTE и оба в районе 250), a-b - тоже нельзя (а вдруг одно из чисел отрицательное) ну и т.п. Сплошной type mismatch. Короче говоря, никак нельзя, потому что всегда можно подобрать такой тип данных и значения, чтобы получился type mismatch! Всё жду, чтобы Darkcosinus выложил, наконец, абсолютно универсальное решение для всех типов данных и всех, даже самых немыслимых, значений параметров. Да вот что-то молчит.

 

[ummasha]

Не, на курсах нам это объяснили с точки зрения подходов к программированию:
а) пространственный: есть место под дополнительную переменную, используют программисты Майкрософта
б) временной: есть время подумать над задачей + можно сэкономить место на диске.

 

[Dr. Evil]

Владимир, мне давали именно такой подход решения. Безусловно лучшим подходом будет использование дополнительной переменной, но так нельзя.

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

 

[Vladimir_S]

Владимир, мне давали именно такой подход решения. Безусловно лучшим подходом будет использование дополнительной переменной, но так нельзя.

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

А Вы просто пройдитесь по теме почти от начала, с #4, там все мои решения и перепалка с Darkcosinus'ом. И про отрицательные числа тоже.

 

[Dr. Evil]

А-а-а ) Понял. В вашем решении изначально было одно усложнение, с которым я не согласен -- зачем присваивать х=y-2*x ?

Действительно, я понял, что данный алгоритм имеет свои ограничения, но какое его не имеет. ИМХО Darkcosinus не прав в одном -- он же не указал, какой именно тип данных использовался для переменных, а потом именно по типу данных и начал придираться )

Теперь осталось дождаться официального вердикта )

 

[Vladimir_S]

А-а-а ) Понял. В вашем решении изначально было одно усложнение, с которым я не согласен -- зачем присваивать х=y-2*x ?

Так я просто, не стремясь к оптимизации, выдал первое пришедшее в голову решение. Мысль шла примерно так - получить величины х+у и х-у а потом из них - новые значения параметров. Действительно, громоздко. Но, тем не менее, решение правильное. Ниже я предложил другое, вроде Вашего - он (Darkcosinus) опять придрался!

Действительно, я понял, что данный алгоритм имеет свои ограничения, но какое его не имеет. ИМХО Darkcosinus не прав в одном -- он же не указал, какой именно тип данных использовался для переменных, а потом именно по типу данных и начал придираться )
Теперь осталось дождаться официального вердикта )

Вот и я про то же.

 

[ummasha]

Вот еще одна задача из книжки: найти все натуральные числа a,b,c из интервала от 1 до 20, для которых выполняется равенство:а2+ b2 = c2

Program KR_2_Var1_2;
Var a,b,c:integer;
Begin
For a:=1 to 20 do
For b:=1 to 20 do
For c:=1 to 20 do
If sqr(a)+sqr(b)=sqr(c) then writeln(a,' ',b,' ',c);
readln;
end.

Задача решается без всяких проблем, НО: в книжке вместо этого было а*а+b*b=с*с. И это "типа" квадраты чисел?

 

[Vladimir_S]

Вот еще одна задача из книжки: найти все натуральные числа a,b,c из интервала от 1 до 20, для которых выполняется равенство:а2+ b2 = c2

Program KR_2_Var1_2;
Var a,b,c:integer;
Begin
For a:=1 to 20 do
For b:=1 to 20 do
For c:=1 to 20 do
If sqr(a)+sqr(b)=sqr(c) then writeln(a,' ',b,' ',c);
readln;
end.

Задача решается без всяких проблем, НО: в книжке вместо этого было а*а+b*b=с*с. И это "типа" квадраты чисел?

В книжке, Маша, всё правильно. Тут есть одна тонкость. Употребив функцию SQR, Вы преобразовали целочисленный формат (Integer, Word, Byte...) в вещественный (Real, Extended...), что "не есть хорошо" хотя бы потому, что в этом формате операция проверки на равенство может, в зависимости от аппаратной реализации, оказаться не совсем корректной, поскольку в "дальних" разрядах может висеть "мусор", и как на него среагирует транслятор, неведомо (например, 2 может преобразоваться во что-нибудь вроде 2.0000000005298307645). Я в своих программах вообще избегаю таких действий, заменяя их при необходимости чем-нибудь вроде if Round(a*100000)=Round(b*100000) then ...

 

[ummasha]

Да, в школе ничего такого не говорили...((( Ну тогда сделаю так, как вы сказали.
Спасибо, что ответили

 

[ummasha]

Вставила в Паскаль If Round(a*100000)+Round(b*100000)=Round(c*100000) then ... вместо If sqr(a)+sqr(b)=sqr(c), но вместо суммы квадратов чисел получилась просто сумма чисел (((

И еще. Иногда у меня не получалось определить четность/нечетность элемента с помощью операций вроде i mod 2=0 или i mod 2=1, а с помощью функций odd(x) или not odd(x) все получалось.

 

[Vladimir_S]

Вставила в Паскаль If Round(a*100000)+Round(b*100000)=Round(c*100000) then ... вместо If sqr(a)+sqr(b)=sqr(c), но вместо суммы квадратов чисел получилась просто сумма чисел (((

И еще. Иногда у меня не получалось определить четность/нечетность элемента с помощью операций вроде i mod 2=0 или i mod 2=1, а с помощью функций odd(x) или not odd(x) все получалось.

Маша, ну я же не про то совсем! А про то, что ВНЕ ЗАВИСИМОСТИ ОТ ЗАДАЧИ конструкции типа if a=b then для ВЕЩЕСТВЕННЫХ (Real) чисел применять рискованно - может не сработать, поэтому лучше перевести параметры в целочисленный формат операцией ROUND. В данном случае достаточно if Round(SQR(a)) + Round(SQR(b)) = Round(SQR(c)) then... Умножение на 10 или 100 или 100000 или еще на что-нибудь подобное нужно лишь для смещения разряда. Например, допустим в программе числа a и b получили значения 0.00753 и 0.0755, а Вы хотите проверить их на равенство. Просто Round не годится, потому что Round(a)=Round(b)=0, а вот Round(a*100000)=753, Round(b*100000)=755. А вообще - чем Вас не устраивает вариант, приведенный в книжке?

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

 

[ummasha]

Программа:

Program KR_2_Var1_2;
Var a,b,c:integer;
Begin
For a:=1 to 20 do
For b:=1 to 20 do
For c:=1 to 20 do
If Round(a*100000)+Round(b*100000)=Round(c*100000) then writeln(a,' ',b,' ',c);
readln;
end.

В чем же проблема? (((

 

[Vladimir_S]

Программа:

Program KR_2_Var1_2;
Var a,b,c:integer;
Begin
For a:=1 to 20 do
For b:=1 to 20 do
For c:=1 to 20 do
If Round(a*100000)+Round(b*100000)=Round(c*100000) then writeln(a,' ',b,' ',c);
readln;
end.

В чем же проблема? (((

Маша, ну не торопитесь и не суетитесь - прочитайте внимательно, что написано в предыдущем посте. Сейчас в программе оператор If действительно сравнивает просто сумму двух чисел с третьим, а не сумму квадратов с квадратом третьего, как требуется.

 

[Vladimir_S]

Вообще я чувствую, что лучше пройти этот момент еще раз и обстоятельно.
Итак, в книжке предложена конструкция
If а*а+b*b=с*с then...
и она у Вас вызвала, как я понял, недоумение. Надеюсь, Вы помните, что умножение числа само на себя это и есть возведение в квадрат, поэтому решение абсолютно верное. Но Вы предложили другое:
If sqr(a)+sqr(b)=sqr(c) then...
которое вроде бы делает то же самое. В чем же разница? А в том, что в результате действия функции SQR получается ВЕЩЕСТВЕННОЕ (Real) число. Т.е. если число a имеет тип Integer, то и число a*a тоже будет иметь тип Integer, а вот число SQR(a) будет иметь тип Real, что не всегда удобно, и я объяснил, почему.

 

[ummasha]

Спасибо огромное за все объяснения, Vladimir_S! Вы мне очень помогли! )))
PS: скоро будут еще задачи

 

[Darkcosinus]

Собственно, по моей задачке ummasha правильно написала решение - нужно использовать побитовую операцию XOR

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

 

[Vladimir_S]

Собственно, по моей задачке ummasha правильно написала решение - нужно использовать побитовую операцию XOR

Ах вот оно как? XOR, говорите? Ну сейчас порезвимся! А если числа вещественные и дробные? Комплексные? Type mismatch!!!