Как поменять переменные местами без третьей 1с
Задача об обмене двух целочисленных переменных значениями (без использования третьей) является одним из классических программистских ребусов.
Как сделать это в PHP, используя минимальное количество символов?
Критерий победы — минимальное количество символов. При прочих равных условиях ответ, опубликованный раньше, побеждает. Подведение итогов через 24 часа.
Пожалуйста, указывайте в ответе количество символов, чтобы проще было выявить победителя.
Комментарий, о причине выбора победителя:
Лидирующий ответ @PashaPash (0 символов) фактически не меняет переменных, поэтому не участвует в конкурсе.
Ответ от @Naumov (10 символов), вместо обмена переменных просто присваивает им новые значения. Ну и его длина не является постоянной, а зависит от значений переменных. Рассматривать этот ответ в рамках конкурсной программы я не буду.
@Qwertiy, потому что пора развивать сообщество в этом направлении. А то сейчас PHP = кака-код . Пора это менять, задавая хорошие, интересные вопросы. Гольф - один из путей.
@AK, ничего не имею против качественных вопросов по реальным задачам. Просто хотелось хоть как-то разбавить скучно-однообразные вопросы по PHP
@Sergiks, стабильно работает везде, начиная с PHP@4.3.0. Пруф (перед запуском стоит ткнуть галочку "eol versions")
Трюк, как я понимаю, заключается во времени вычисления аргументов минуса. Унарный плюс, образуя выражение, по всей видимости, первым разрешается в значение. И, видимо, это значение кладётся в неявную переменную. А поскольку минус получает свои аргументы по ссылке, без плюса не работает. Аааргх
А это потому что у них принципиально разные левые аргументы и группировка по выражениям происходит в неравных условиях. У - левый аргумент может быть любым выражением, а у = исключительно lvalue . Поэтому = слева от минуса выполнится позже него (т. к. справа от него может быть выражение, с операторами, с которыми он может конкурировать за приоритет), а справа -- раньше (поскольку там lvalue должен быть непосредственно рядом, в упор).
Мой зевок, неправильно проверил. Действительно, работает. Но приоритет операторов ведь ставит + и – раньше = ! Почему это работает? : )
@Sergiks, это действительно интересно. Вот тут сказано, что у = действительно меньший приоритет, однако в замечании приведен пример, это опровергающий.
@DmitriySimushev list() – не арифметический оператор ) Я про ваше решение, своё с умножением и делением и Алексея Шиманского.
Совсем альтернативный вариант:
Повторное присвоение значений переменным - в целом плохая идея.
- В плане читабельности кода - глядя на первое присвоение значений переменным тяжепо понять, чему ж они будут равны в конце метода. Особенно актуально для языков с нестрогой типизацией.
- В плане производительности - процессору гораздо удобнее просто начать брать значение из другого места, чем терять время на перекладывание значений из одного куска памяти в другой, и обратно.
Гораздо лучше просто заменить использование переменных в том коде, который расположен ниже места, где вы собирались вписать swap.
PHP, 0 символов
на мой взгяд очень спорное утверждение. Представьте что нам по какой-то причине нужно, что а было меньше b иначе - поменять местами. Тогда по вашему, нам нам нужно писать 2 ветви кода под if/else вместо обмена?
А если, грубо говоря, у меня подряд идут три цикла foreach для вывода результата из бд в шаблон, в виде таблиц, но использую специально некоторую переменную $nomer_po_porjadku чтоб обозначить номер по порядку в них в первом столбце. тогда нужно для трех таблиц и циклов три разные переменные заводить все равно, а не обнулять первую и переиспользовать?
@АлексейШиманский: В C++ локальные переменные внутри цикла таки не видны снаружи. Ну и да, переиспользовать переменные — плохая идея, потому что создаёт излишние зависимости между частями кода. Поверьте, компилятор умеет гораздо лучше нас с вами переиспользовать области памяти под ненужные переменные.
@VladD локальные переменные внутри цикла таки не видны снаружи . либо я не понял, либо)) .. я говорю про $nomerPp = 1; foreach($something as $item) < doSmth; echo '
17, 19, 23 и 42 символа
в общем для оригинальности 28 символов
Самый простой способ взаимно менять значения переменных — использование swap(a, b) или же аналогичного стандартного метода. Тем не менее, важно понимать как работает операция по обмену значений двух переменных, что мы покажем на нескольких примерах.
Для начала продемонстрируем неправильную реализацию и выясним, что в ней не так.
Ошибочная реализация
Если вы попытаетесь выполнить обмен значений этим способом, то увидите, что теперь в обеих переменных хранится значение переменной b . Происходит это ввиду построчного выполнения кода. Первая операция присваивания сохраняет значение переменной b в переменную a . Затем вторая — новое значение a в b , иными словами значение b в b . Таким образом, мы полностью теряем содержание контейнера a .
Теперь обратимся к правильной реализации.
С использованием буфера
Буфером в данном случае называется дополнительная используемая память. Давайте разберёмся зачем она здесь нужна. Если помните, в неправильной реализации мы потеряли значение переменной a после первой операции присваивания, в связи с чем в обеих доступных переменных осталось значение b . Чтобы этого избежать нам понадобится ещё одна переменная — c . В таком случае правильный алгоритм будет выглядеть так:
Для наглядности разберём его пошагово:
- Присваиваем переменной c значение переменной a . Сейчас в a записана a , в b — b , а в c — a .
- Присваиваем переменной a значение переменной b . Теперь в a хранится b , в b — также b и в c — a .
- Присваиваем переменной b значение переменной c . Сейчас в a находится старое значение b , в b — a , ну и в c остаётся a .
Как вы видите, переменная c после выполнения алгоритма не нужна, поэтому далee в программе её можно не использовать и даже вовсе удалить из памяти.
Сразу стоит заметить, что это самое краткое и экономное решение задачи, но можно использовать и больше переменных, не так ли?
Нам повезло, что сейчас вопрос экономии оперативной памяти не стоит так остро, как 20-30 лет назад. Тем не менее, в те времена swap был востребован не меньше, поэтому умные люди нашли способ заменить значения двух переменных без ввода третьей.
Арифметика
Сложение / вычитание
Для лучшего восприятия снова разберём алгоритм построчно:
- Присваиваем переменной a сумму значений переменных a и b . Сeйчас в a записано значение a + b , а в b всё ещё b .
- Переменной b присваиваем разность между новым значением переменной a и переменной b . В a также хранится a + b , но в b уже a .
- Наконец, присваиваем переменной a результат вычитания b из обновлённого значения a . Получается, что в a теперь содержится b , а в b — a .
Для C-подобных языков сокращённая запись этого алгоритма выглядит так:
Умножение / деление
Аналогичный способ решения задачи получается при замене сложения умножением и вычитания делением:
В сокращённом варианте:
Вычитание / Сложение
Вообще, в математике действие вычитания отсутствует и является сложением положительного и отрицательного чисел. Отсюда следует, что мы можем поменять местами операции сложения и вычитания:
Обратите внимание, что в последней строке знак у переменной a изменился, а саму строчку можно записать иначе: a = b - a; .
Такой же принцип можно использовать поменяв местами деление и умножение.
Недостатки арифметического метода
Главным недостатком является большее количество операций, в чём можно убедиться посчитав операции сложения, вычитания и присваивания. Тeм болee, что умножeниe и дeлeниe болee «дорогостящиe». Заметной потеря скорости становится в ситуации, когда трeбуeтся менять значения большого количества пeрeмeнных.
Второй важный нeдостаток это область применения — числа. Согласитесь, менять значения пeрeмeнных, содержащих объeкты попросту нe получится без перегрузки операции. Впрочeм, дажe с числами могут возникнуть проблемы — арифметика для вeщeствeнных чисeл можeт выполняться некорректно, что приведёт к неожиданному результату.
Eстeствeнно, существует и менее очевидный способ рeшeния задачи без использования дополнительной памяти. Он основан на свойствах логических операций и работает с битовым представлением числа, а значит быстрее арифметического метода.
Битовые операции
Данный алгоритм основан на следующем свойстве операции XOR («исключающее или»): a XOR b XOR a = b .
Для любитeлeй коротких записeй приведём код одной строчкой. XOR в C-подобных языках замeняeтся знаком ^ :
Однако помните о точках следования. Из-за них этот код может вести себя непредсказуемо и давать разные результаты, поэтому никогда не используйте его в production коде.
Обязательно посмотрите более подробный разбор решения через битовые операции от Г. Лакмана Макдауэлла, автора известного сборника задач с собеседований, который есть в одной из наших книжных подборок.
Это классическая задача, которую любят предлагать на собеседованиях, и она достаточно проста. Пусть a0 — это исходное значение a , а b0 — исходное значение b . Обозначим diff разницу а0 - b0 .
Давайте покажем взаимное расположение всех этих значений на числовой оси для случая, когда a > b :
Присвоим а значение diff . Если сложить значение b и diff , то мы получим a0 (результат следует сохранить в b ). Теперь у нас b = а0 и a = diff . Все, что нам остается сделать, — присвоить b значение а0 - diff , а это значение представляет собой b - a .
Приведенный далее код реализует этот алгоритм:
Можно решить эту задачу с помощью битовой манипуляции. Такой подход позволит нам работать с разными типами данных, а не только с integer .
Этот код использует операцию XOR . Проще всего понять, как работает код, взглянув на два бита — р и q . Давайте обозначим как р0 и q0 исходные значения.
Если мы сможем поменять местами два бита, то алгоритм будет работать правильно. Давайте рассмотрим работу алгоритма пошагово:
- p = p0^q0 /* 0 если р0 = q0, 1 если р0 != q0 */
- q = p^q0 /* равно значению р0 */
- 3. p = p^q /* равно значению q0 */
В строке 1 выполняется операция p = p0^q0 , результатом которой будет 0, если p0 = q0 , и 1, если p0 != q0 .
В строке 2 выполняется операция q = p^q0 . Давайте проанализируем оба возможных значения p. Так как мы хотим поменять местами значения p и q, в результате должен получиться 0:
- p = 0 : в этом случае p0 = q0 , так как нам нужно вернуть p0 или q0 . XOR любого значения с 0 всегда дает исходное значение, поэтому результатом этой операции будет q0 (или p0 ).
- p = 1 : в этом случае p0 != q0 . Нам нужно получить 1, если q0 = 0 , и 0, если p0 = 1 . Именно такой результат получается при операции XOR любого значения с 1.
В строке 3 выполняется операция p = p^q . Давайте рассмотрим оба значения p . В результате мы хотим получить q0 . Обратите внимание, что q в настоящий момент равно p0 , поэтому на самом деле выполняется операция p^p0 .
- p = 0 : так как p0 = q0 , мы хотим вернуть p0 или q0 . Выполняя 0^p0 , мы вернем p0(q0) .
- p = 1 : выполняется операция 1^p0 . В результате мы получаем инверсию p0 , что нам и нужно, так как p0 != q0 .
Остается только присвоить p значение q0 , a q — значение р0 . Мы удостоверились, что наш алгоритме корректно меняет местами каждый бит, а значит, результат будет правильным.
Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Поменять значения двух переменных
Рассмотрим, как поменять местами значения двух переменных в коде программы. Статья предназначена тем, кто только начинает делать первые шаги в программировании.
Как только вы начнете писать свою второю в жизни программу (первая — вывод слов Hello World), вы столкнетесь с необходимостью обмена значениями между двумя числовыми переменными, поскольку манипуляции с данными непременно это предполагают. В примерах кода, которые приводятся в статье мы оперируем с целочисленными переменными типа int, но данные примеры легко адаптировать под любой вид числовых переменных: byte, long, float, double и т.п. Для этого вам будет достаточно заменить все ключевые слова int, на требуемый тип данных.
Поменять значения двух переменных
Прежде чем писать программный код, давайте подумаем, как поменять значения двух переменных в принципе. Решим данную задачу у себя в голове. А затем формализуем выработанный алгоритм действий.
Начнем с тезиса о том, что переменные в программе имеют содержимое. Они содержат информацию. Для того, чтобы провести какую-либо аналогию с жизнью, нужно подумать: а какие предметы что-нибудь в себе содержат? Первое, что приходит на ум — это ёмкость с жидкостью.
Пусть у нас есть два стакана: в одном налито молоко, а в другом кока-кола. Как нам перелить содержимое одного стакана в другой (нельзя же смешивать эти два совершенно несовместимых продукта) [заметили аналогию? ведь содержимое двух переменных нам тоже нужно поменять местами]? Ответ очевиден — понадобится третий (пустой) стакан. С помощью него удастся перелить содержимое одного стакана в другой. Вот так:
- Перелить молоко из первого стакана в третий.
- Перелить кока-колу из второго стакана в первый.
- Из третьего стакана перелить молоко во второй стакан. Готово!
Иллюстрация действий приводится на рисунке ниже.
Возвращаясь к программированию, делаем вывод, что для того, чтобы поменять значения двух переменных, понадобится промежуточная третья.
Пусть даны переменные a и b, и их значения нужно поменять местами. Нам понадобится промежуточная временная третья переменная, назовем её temp (сокращение от английского слова temporary — временный). Чтобы выполнить замену, придется также выполнить три действия:
Реализуем описанный выше алгоритм действий и составим программу обмена значениями двух переменных величин. Ниже представлен её код:
У меня другой вопрос, можно ли это как-то засунуть в метод? Написал так:
Но переменные x и y не меняются местами, по крайне мере в методе Main. Можно сделать так:
Но это выглядит как-то коряво и неуместно, потому что я хочу, чтобы метод только менял местами введенные с клавиатуры значения, а где и когда их вывести я хочу решать сам.
Вы забыли указать параметрам модификатор ref , поэтому они передаются по значению и на переменные вне метода никакого влияния не оказывают
@АндрейNOP насколько я знаю, в шарпе только через лямбду такое можно делать, простое приравнивание кортежей не пройдет
4 ответа 4
Всё дело в том, что ты передаешь копии переменных в метод Swap . Чтобы иметь возможность передавать ссылку есть ключевое слово ref .
Т.е. метод будет выглядеть так:
Есть также параметр out. Разница между ref и out тут: ref и out
А что значит передаю копии? То есть я как бы даю значения этих переменных методу SwapNumbers, в методе Main они остаются те же, а метод SwapNumbers при этом не возвращает измененные значения?
@AlexVause, верно. Некоторые типы данных являются ссылочными, а некоторые типами значения. Например, int и char типы-значения, т.е. при передаче в метод или куда-то ещё передается именно то, что в переменной хранится. А вот ссылочные типы (например, класс) это типы, у которых берется не значение, а именно адрес места в памяти(как адрес улицы на которой вы живете. Могут прийти к вам по адресу и поселиться жить у вас, вместо покупки своего дома).
При передаче в метод по значению (по умолчанию) в метод передается копия переменной, соответственно в вашем коде значения x и y не изменяются.
При указании модификатора ref переменные передаются в метод по ссылке, а не по значению. В этом случае при изменении значений переменной в методе будет изменено значение и в вызывающем методе.
Можно в острые скобки (не знаю как их принято называть) вписываем тип переменной и всё.
"попался вопрос про обмен значениями переменных без использования третьей." И в методе Main у вас всё равно будут старые значения для x и y .
На самом деле не особо важен сам алгоритм. В данный момент я разбираюсь с темами методов и областями видимости, поэтому просто хотелось понять, как приложить конкретный метод к введенным значениям.
Читайте также: