-
Задача N - хз
Есть две интересные задачи на создание алгоритмов.
1. Стандартный алгоритм перемены двух переменных Х и У местами состоит из
а) Z=X
b) X=Y
C) Y=Z
Грубо говоря он меняет местами значения Y и X с помощью вспомогательной переменной Z. Пример:
X=1 Y=2
a)Z=X (Z=1)
b)X=Y (X=2)
c)Y=Z (Y=1)
результат: X=2 Y=1
Первая задача состоит в том, чтобы составить алгоритм перемены значений двух переменных БЕЗ использования вспомогательных переменных.
2. Имеется функция MAX(), которая получает 3 числа и возвращает значение наибольшего из них. Пример:
MAX(1,2,3) = 3 MAX(5,8,8) = 8
Требуется составить алгоритм, который найдет из трех чисел a,b,c МИНИМАЛЬНОЕ, используя только вспомогательные переменные, математические операции и функцию MAX() и не сравнивая числа друг с другом (перевожу для программеров - "If(...) ... Else ..." и подобные вещи использовать нельзя).
Вопросы по поводу принципов составления алгоритмов мона задавать в личку.:jester:
З.Ы. Алгоритм функции MAX(a,b,c):
1) if (a>b) maximum=a
1.1) else maximum=b
2) if (c>MAX) maximum=c
3) return maximum
Алгоритм сравнивает a и b и присваивает значение большего из них
переменной maximum, затем проверяет, если с больше значения этой переменной, то присваивает ей значение с, если же нет, то оставляет ее без изменений.
Для примера возьмем числа 1, 2 и 3 :
1) 2 больше 1, значит maximum=2
2) 3 больше maximum, значит maximum=3
-
-
-
ILS, решение верное, решению второй задачи даже приятель программер поапплодировал. У меня лично немного длиннее получилось, хотя немного проще для проверки.
Masha, вторая решена, правда с некоторыми неточностями, насчет первой выслал обьяснение.
-
Fessaer, я учил программирование, хотя такие задачи передо мной в ходе обучения не ставили :)
-
Merlin, решил обе. Оба решения аналогичны решениям Илса.
-
А к какому полю принадлежать числа во второй задаче? Целые, положительные, реальные?
-
Кинула свои варианты в личку.
-
sirUjin,
По традиции, если не указано иное, числа считаются целыми обычной длины, то есть Int32.
-
Если числа могут быть отрицательными, решение будет совсем другое.
А традиции... Смотря где традиции. Для програмистов на Матлабе, по традиции по умолчанию используется Double
-
sirUjin,
Не знаю, моё решение годится и для отрицательных чисел, и для вещественных.
На большинстве интервью, если задётся задачка на алгоритмику и не оговаривается язык, на котором должно быть решение, ожидается, что претендент напишет решение на С или С++ - их знают даже те, кто никогда не сталкивался с ними по работе, это эдакая программерская латынь.
Вещественные числа не используются по умолчанию хотя бы потому, что, например, в процессорах с 8086 по 386 они отсутствовали как данность и были выведены как функция сопроцессора (серия х87), а непосредственно в основной процессор они были добавлены только с 486.
-
sirUjin, есть решение, пригодное для любых чисел. Как известно, два любых действительных числа можно сравнить, и сказать, какое из них больше, а какое меньше, или признать, что они равны. Думай.
-
У меня боло решение для положительных чисел, но уже нашел для любых, при чем даже элегантнее. :)
Ryzhaya, алгоритмы, вообще-то, чаще пишутся как раз на Матлабе, потому что так легче, можно о памяти и прочем железе не думать, а заниматься непосредственно алгоритмом, а уже потом переводятся на С++. Это я тебе как человек занимающийся алгоритмами говорю :)
-
-
sirUjin, Ryzhaya, оба, обе...
-
Ответы:
1)
x = x + y
y = x - y
x = x - y
2) Самый короткий вариант:
Min = - max(-a, -b, -c)
-
Fessaer,
Не согласна с решением первой задачи. Всё-таки решение через XOR - более правильное, потому что ни при каких случаях не может привести к переполнению.
-
Ryzhaya,в таких ситуациях математические операции + и - предпочтительнее, так как они проще для непосвященного, а пока речь идет об алгоритме, а не о конкретной функции, понятие переполнения отсутствует.. Никто не отменял верность решения через XOR.
