Как стать автором
Поиск
Написать публикацию
Обновить
63.48

Занимательные задачки

Разминаем мозги

Сначала показывать
Порог рейтинга
Уровень сложности

Бумажный геймдев: как увлечь ребёнка без интернета и гаджетов

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров3.2K

Привет, Хабр! Как вы думаете: что общего между написанием сложного кода и игрой с семилетним ребёнком? Отвечу как молодой отец и сотрудник ИТ-компании: оба процесса занимают неопределённо много времени и порой заставляют вас усомниться в своём интеллекте. Если за помощью с кодом всегда можно обратиться к Stack Overflow или (простите!) к ИИ-ассистентам, то ребёнок требует вашего персонального внимания. Считайте, что вы один на один с естественной нейросетью, которая находится в стадии обучения, но уже активно лезет в продакшен. А ещё эта нейронка часто капризничает и требует поиграть, игнорируя ваши дедлайны.

Оставлять ребёнка надолго перед экраном — не лучшая идея (хотя продавцы очков и контактных линз, а также психологи будут вам благодарны). Поэтому ищем другие варианты. Если ваш ребёнок уже освоил азы шантажа («Пап, а я тогда не усну!») и базовые алгоритмы манипуляции («А мама разрешает!»), пора переходить к ассиметричным ответным мерам. Нам помогут не столько старые, сколько добрые игры на бумаге, которые слегка изменились со времён нашего детства.

Главное в этих играх — листок и ручка фантазия!  Они не требуют зарядки, не содержат микроплатежей и помогают развивать мышление лучше, чем очередная «нейро» игра из магазина. Давайте поближе познакомимся с этими шедеврами офлайнового безчипового геймдева!

Читать далее

Новости

Project Euler. Векторное программирование и задача номер 1

Уровень сложностиСредний
Время на прочтение3 мин
Количество просмотров2.7K

Добавляем щепотку векторного программирования в задачки проекта Эйлер. Заодно разбираемся, как эффективно реализовать деление на константу.

Читать далее

Как выбрать оффер? Задача о разборчивой невесте и правило 37%

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров12K

В течение месяца вы проходите собеседования, получаете офферы — и хотите выбрать лучший. Но каждый оффер живёт недолго: если не согласитесь вовремя, к нему уже не вернуться. Как действовать, чтобы выбрать самый лучший?


Это версия классической задачи о разборчивой невесте. У неё есть красивая оптимальная стратегия — правило 37\%. Возможно, вы о нём слышали. Но знаете ли вы, почему оно работает? И как вообще до него додуматься?


Часто алгоритмы — это эвристики, без гарантии оптимальности. Но в этой задаче всё иначе. Мы шаг за шагом переоткроем правило  37 \% и докажем, что он действительно лучший

Недавно я узнал о Теореме о Шансах — более общем подходе, который, неожиданно, работает гораздо проще, чем классическое доказательство. По-русски о ней еще никто не писал

В статье мы разберём эту теорему, выведем правило 37\% и увидим, как в задаче естественно появляется число e — и какой у него смысл на самом деле

Эта задача стоит того, чтобы пройти её до конца. Будет понятно, красиво и интересно

К правилу 37%

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

Уровень сложностиПростой
Время на прочтение5 мин
Количество просмотров23K

Вот удивительный эксперимент, который вы можете попробовать провести у себя дома: соберите несколько игрушечных блоков и положите их на стол. Возьмите один блок и медленно, сантиметр за сантиметром, продвигайте его за край стола, пока он не окажется на грани падения. Если у вас есть терпение и твёрдая рука, у вас должно получиться сбалансировать его так, чтобы ровно половина свисала с края. Стоит сдвинуть его ещё дальше, и гравитация победит. Теперь возьмите два блока и начните сначала. Укладывая один блок на другой, как далеко вы сможете завести конец верхнего блока, чтобы он высунулся за край стола?

Читать далее

Сотворение мира за 20 минут на JavaScript, или минималистичная модель эволюции

Уровень сложностиПростой
Время на прочтение17 мин
Количество просмотров9.3K

Впервые про моделирование эволюции я прочитал в 13 лет в статье «Жить и умереть в компьютере» (Техника — Молодежи, №5 1993 год). Она произвела на меня столь неизгладимое впечатление, что я тут же загорелся идеей создать что-то подобное.

Однако никак не удавалось проработать законы мира. Как организмы будут «смотреть» на окружающий мир? Как общаться? Как атаковать? Как кушать друг друга? Наконец, как будет устроен их «мозг»? Реализовать виртуальную машину, как в статье из журнала, или использовать что-нибудь проще, типа конечного автомата или схемы из блоков И-НЕ?

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

Запустить эволюцию

Винтик и Шпунтик, часть 3: лемма Бернсайда и генерация орбит

Уровень сложностиСредний
Время на прочтение26 мин
Количество просмотров1.5K

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

Читать далее

Последовательность Фибоначчи как ЛРП или что делать, если хочется найти период у бесконечной последовательности?

Уровень сложностиПростой
Время на прочтение3 мин
Количество просмотров2.2K

Эта заметка про поиск так называемого периода Пизано, то есть периода последовательности Фибоначчи по простому модулю. Про сам этот период написано довольно много, но моё домашнее задание было достаточно конкретным, продемонстрировать связь порядка и периода. Я же, в качестве бонуса, опишу стратегию поведения и для случая когда правило "порядок это период" не актуально.

Читать далее

Задача о пересечении интервалов (или зачем программисту MК стабильная сортировка)

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров7.1K

В программировании микроконтроллеров эпизодически приходится решать задачу о выявлении пересечения интервалов.

На первый взгляд простая задачка, однако, как оказалось, реализовать такое в коде - это вовсе нетривиальная задачка. Но обо всём по порядку...

В этой заметка я представил свой алгоритм определения пересечений интервалов и его разбор.

Читать далее

Винтик и Шпунтик, часть 2: гиперкубы, шляпы и фартуки

Уровень сложностиСредний
Время на прочтение26 мин
Количество просмотров1.4K

Это вторая часть моих наработок по решению задачи про Винтика и Шпунтика в рамках челленджа @vvvphoenix. В первой части мы выразили ответ в виде формулы включений-исключений. Хотя в подобных формулах и получается огромное число слагаемых, часто оказывается, что либо они почти все равны нулю, либо объединяются в сравнительно небольшое число групп одинаковых, либо ещё что-нибудь. И в итоге огромная формула вычисляется чуть ли не на бумаге. В этой части мы будем сворачивать и оптимизировать нашу формулу для ускорения вычислений.

Читать далее

Задача о Выборе Билетов

Уровень сложностиПростой
Время на прочтение6 мин
Количество просмотров1.8K

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

Я решил положить этому конец и распетлять задачу при помощи ЭВМ.

Постановка задачи

Надо доехать из города A в город C. При этом надо совершить пересадку в городе B. На сайтах есть множество билетов в направлении A->B и B->C. Надо выбрать два билета так чтобы:

1--минимальное время пересадки

2--минимизировать стоимость поездки

3--минимизировать общее время в пути

Надо написать программу. Буквально загружаешь все доступные в продаже билеты, запускаешь программу и получаешь целеуказание на самый оптимальный комплект билетов.

Читать далее

От театральной импровизации до навыка для Алисы: как я сделал голосовую игру про принцесс, драконов и рыцарей

Уровень сложностиПростой
Время на прочтение6 мин
Количество просмотров1.1K

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

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

Читать далее

Теорема Борсука-Улама, диаметральные точки Земли и дележка украденного ожерелья

Время на прочтение5 мин
Количество просмотров5.3K

Привет, меня зовут Диана. Я математик и автор хабраблога МТС. В прошлый раз рассказывала о поверехностях второго порядка, а сегодня хочу обсудить изящную топологичекую теорему, у которой есть внезапные приложения в жизни — географии, экономике и политике. Ее следы можно найти в алгоритмах дележки, когда нужно распределять по долям какой-то неоднородный ресурс — данные, вычислительные мощности, бюджет. Например, с ее помощью можно разделить участки земли между фермерами, учитывая разные параметры: площадь, тип почвы, удаленность от дороги и прочее. Она такая немножко Сейлор Мун — за добро и справедливость.

Этот пост мог бы иметь кликбейтное название в духе «На противоположной стороне Земли сейчас такая же погода, как у вас!», но это не совсем верно. Почему — объясню ниже. А пока предлагаю разобраться с официальными формулировками и переложить их на понятный язык. Еще в тексте будут ссылки на связанные проблемы, которые научат нас грамотно резать бутерброды и причесывать ежей — в общем, надеюсь, получилось познавательно!

Читать далее

Задача про рукопожатия

Уровень сложностиПростой
Время на прочтение2 мин
Количество просмотров5.5K

Существует классическая задача:

«Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?»

Эта задача представляет интерес только лишь потому, что её нынче задают при устройстве на работу. Поэтому надо уметь её решить и объяснить решение.

Читать далее

Ближайшие события

Задача с эмодзи

Уровень сложностиСредний
Время на прочтение8 мин
Количество просмотров8K

Сложность текста: 2-3/5

Необходимые знания: должно быть достаточно основ теории многочленов, например, формул Виета

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

Интернет переполнен «математическими задачками с эмодзи». Они более-менее продуманы, поэтому в них легко запутаться, и у людей получаются разные ответы, что вызывает споры и обсуждения, делая посты виральными и так далее...

Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?».

Читать далее

Постоянная Капрекара: алгоритм, который всегда сводится к одному числу

Время на прочтение4 мин
Количество просмотров17K

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

В 1949 году индийский математик Даттарая Капрекар обнаружил интересную закономерность у четырёхзначных чисел. При выполнении определённых действий с четырёхзначными числами (кроме тех, в которых все цифры одинаковые) всегда получается одно и тоже число.

Читать далее

Задача про мышей и отраву

Уровень сложностиПростой
Время на прочтение6 мин
Количество просмотров12K

Есть 1000 одинаковых колб с прозрачной жидкостью.

В 999 колбах вода, а в одной случайной - отрава.

Если мышь попробует отраву, то она погибнет через 1 час.

Как найти отравленную колбу за минимальное время?

Читать далее

Как проверить в C, является ли выражение константой

Время на прочтение9 мин
Количество просмотров3.7K

Вот вам маленькая задачка на программирование: реализуйте такой макрос, который принимает в качестве аргумента числовое выражение (числа могут быть целыми или с плавающей точкой) и:

Читать далее

Винтик и Шпунтик, часть 1: формула включений-исключений

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров2.9K

В данной серии статей я изложу мои наработки по решению задачи про Винтика и Шпунтика в рамках челленджа @vvvphoenix. Наработок достаточно много, и изложение их всех в одной статье получилось бы слишком объемным, либо же пришлось описывать всё достаточно сжато. Ни того, ну другого не хотелось бы, поэтому разбиваю изложение на части. Пока планируется 4 части, возможно в ходе их написания появятся идеи для новых частей или новые продвижения в решении задачи. И тогда частей будет больше. Данная первая часть скорее вводная, в которой я опишу такой подход к подсчету числа вариантов в различных комбинаторных задачах, как "формула включения-исключения".

Читать далее

Как специально написать чрезвычайно медленный код

Время на прочтение7 мин
Количество просмотров16K

Раз в несколько лет я устраиваю в нашей исследовательской группе челлендж «Напиши медленный код». Цель – написать код с минимально работоспособным количеством инструкций на цикл (IPC) с условием, чтобы этот код выполнялся на заранее подобранном сервере с архитектурой x86.

На первый взгляд, это абсурд В сущности, так и есть. Однако есть в этой безумной задаче и некоторая методическая ценность. Инженеры, проектирующие процессоры, прилагают все усилия ради достижения наивысшего возможного IPC… даже для очень неэффективного кода. Так и задумано, что писать код с очень высоким показателем IPC непросто. Следовательно, челлендж «Напиши медленный код» оказывается заковыристым упражнением, вынуждающим задумываться, как именно работает процессор, и как применить себе на пользу его острые углы.

Читать далее

История о недостающих метриках: странности с замыканиями в Rust

Время на прочтение8 мин
Количество просмотров1.6K
Как один нюанс, связанный с обработкой замыканий в Rust, привёл к потере метрик в нашей компании, и какие уроки мы из этого извлекли

В потоковой базе данных у вас должны быть в распоряжении точные метрики – это не просто плюс, а важнейшая предпосылка для отслеживания производительности, выявления узких мест и обеспечения ровного функционирования системы в режиме реального времени. Метрики можно сравнить с циферблатами на приборном щитке автомобиля. Именно по ним вы получаете оперативную обратную связь и узнаёте, что творится «под капотом». Один из ключевых показателей, который необходимо отслеживать — это скорость извлечения данных с того уровня, где они хранятся. В системе реального времени такая функция неоценима.

Нам довелось столкнуться с загадочной ситуацией: одна из наших метрик, характеризующая хранение данных, якобы оставалась на нуле, даже когда нам было точно известно, что через систему прокачиваются данные. Всё равно, что вести машину со сломанным спидометром — мы же едем, но не знаем, с какой скоростью. В результате нам пришлось устроить настоящее расследование и углубиться в наш код на Rust. В результате мы узнали много нового о том, как в Rust раньше обрабатывались замыкания.
Читать дальше →
1
23 ...

Вклад авторов