Рубрика «Занимательные задачки»

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

Прежде всего — немного истории. Работая на должностях тимлида и техлида мне порой приходилось проводить собеседования, соответственно нужно подготовить несколько теоретически вопросов, ну и пару несложных задач, на решение которых не должно было бы уйти больше 2х-3х минут. Если с теорией все просто — мой любимый вопрос это: «чему равен typeof null?», по ответу сразу можно понять, кто сидит перед тобой, джун — просто правильно ответит, а претендент на сеньера, еще и объяснит почему. То с практикой — сложнее. Я долго не мог придумать нормальное задание, не изъезженное, типа fizz-buzz, а что-нибудь свое. По этому я на собеседованиях давал задания, которые сам проходил, устраиваясь на текущую работу. О первом из них и пойдет речь.
Читать полностью »

Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.

Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.

Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Читать полностью »

Парадоксы о сжатии данных - 1 Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 11), математическими выражениями («два в двадцатой» для 1048576), строковыми выражениями («пять девяток» для 99999), именами собственными («число зверя» для 666, «год смерти Тьюринга» для 1954), или произвольными их комбинациями. Годится любое обозначение, по которому собеседник сможет однозначно определить, о каком числе речь. Очевидно, что сообщить собеседнику «факториал восьми» эффективнее, чем эквивалентное обозначение «сорок тысяч триста двадцать». Здесь возникает логичный вопрос: какое обозначение для заданного числа самое короткое?

Философ Бертран Рассел в 1908 опубликовал «парадокс Берри», который затрагивает вопрос обозначений чисел с противоположной стороны: какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.

Значит, этому числу будет соответствовать обозначение «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв», в котором всего 78 букв! С одной стороны, это число обязано существовать; с другой, если это число существует, то его обозначение ему не соответствует. Парадокс!Читать полностью »

Я начал погружение в мир IT лишь три недели назад. Серьезно, три недели назад я даже не понимал синтаксиса HTML, а знакомство с языками программирования заканчивалось школьной программой по Pascal 10-летней давности. Однако я решился поехать в IT-лагерь, для детей которого было бы неплохо сделать бота. Я решил, что это вряд ли так сложно.

С этого начался длинный путь, в рамках которого я:

  • развернул облачный сервер с Ubuntu,
  • зарегистрировался на GitHub,
  • выучил базовый синтаксис JavaScript,
  • прочитал тонну статей на английском и русском языках,
  • сделал, наконец, бота,
  • написал эту статью, наконец.

Выглядел итоговый результат примерно так:

Руководство: как сделать простого бота для Телеграм на JS для новичка в программировании - 1
Читать полностью »

(Управляющие карты)
(Посвящается Международному году Периодической таблицы химических элементов)

image
(Цветок Менделеева, Источник)

Помнится, мы проходили утку. Это были сразу три урока: география, естествознание и русский. На уроке естествознания утка изучалась как утка какие у нее крылышки, какие лапки, как она плавает и так далее. На уроке географии та же утка изучалась как житель земного шара: нужно было на карте показать, где она живет и где ее нет. На русском Серафима Петровна учила нас писать «у-т-к-а» и читала что-нибудь об утках из Брема. Мимоходом она сообщала нам, что по-немецки утка так-то, а по-французски так-то. Кажется, это называлось тогда «комплексным методом». В общем, все выходило «мимоходом».

Вениамин Каверин, Два капитана

В приведенной цитате Вениамин Каверин мастерски показал недостатки комплексного метода обучения, однако в некоторых (может быть, довольно редких) случаях элементы этого метода бывают оправданы. Один из таких случаев — это Периодическая таблица Д.И.Менделеева на уроках школьной информатики. Задача программной автоматизации типовых действий с таблицей Менделеева наглядна для школьников, начавших изучать химию, и разбивается на многие типовые химические задачи. В то же время в рамках информатики эта задача позволяет в простой форме продемонстрировать способ управляющих карт, который можно отнести к графическому программированию, понимаемому в широком смысле слова как программирование с помощью графических элементов.
Читать полностью »

Сегодня — 4 апреля — в 13 часов по Москве начнется финал Международной студенческой олимпиады по программированию (ICPC), в котором примут участие 10 российских команд. Их представляют университеты из пяти городов: Москвы, Санкт-Петербурга, Екатеринбурга, Саратова и Архангельска. Сильнейшие зарубежные соперники — Стэнфорд, Шанхайский транспортный университет и MIT.

Финал ICPC 2019

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

Сегодня в португальском городе Порту пройдет финал международных соревнований по программированию ICPC 2019. В нем примут участие представители Университета ИТМО и другие команды из вузов России, Китая, Индии, США и других стран. Расскажем подробнее.

«Сражение в прямом эфире»: финал ICPC в Порту - 1Читать полностью »

Как волонтёры со всего мира создают прямой эфир ICPC-2019 - 1

Меня зовут Лида Перовская, я работаю в Яндексе, а ещё с 2015 года помогаю организовывать прямой эфир International Collegiate Programming Contest. ICPC — студенческий чемпионат мира по программированию — проводится ежегодно с 1970-х. Это чуть ли не единственная олимпиада подобного уровня, которое развивается благодаря усилиям сотен волонтёров со всего мира. Сегодня я расскажу читателям Хабра о том, как устроена моя работа на ICPC изнутри. А ещё приглашаю посмотреть трансляцию мероприятия (4-го апреля в 12:00 по московскому времени) и попробовать собственные силы в решении задачек одновременно с участниками.

Для нас — волонтёров — важно, чтобы мероприятие было интересным и полезным и для участников, и для зрителей. Но сделать это непросто. На один только финал заявлено 135 команд из 110 стран, в каждой команде по три человека, и все они участвуют одновременно! Кого, когда и как пускать в эфир? Какой код показывать? Как комментировать, чтобы это было полезно?

Читать полностью »

image

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

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

От парсера афиши театра на Python до Telegram-бота. Часть 2 - 1

Продолжаем историю о разработке Telegram-бота для поиска билетов — HappyTicketsBot, начало можно почитать в первой части.
Во второй расскажу о самом боте, поделюсь кодом, а также идеями, которым скорее всего не суждено стать реальностью. Большая часть функционала к моменту создания бота уже была написана в формате скрипта, поэтому основной задачей стояло наладить интерфейс взаимодействия с пользователем через Telegram-messenger. Получилось не так болтологически, как в 1й части, так что attention — много кода.

Спойлер: HappyTicketsBot так и не улетел крутиться на иностранный сервер, он локальный и русский, но однажды запуск (верю) состоится =)
Читать полностью »