Рубрика «задача» - 3

Сингапурский телеведущий Kenneth Kong взорвал интернет логической задачей.

image

11 апреля 2015 он разместил на своей странице в Facebook задачу на логику для школьной олимпиады. SASMO (Singapore and Asean Schools Math Olympiads) уточнили позже, что задача предназначалась для детей 14 лет (уровень Sec 3).
Читать полностью »

На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Читать полностью »

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

Проблема в том, что за период размещенния случилось две большие вещи:

  • Из-за праздников был сезонный спад, и продажи по городам падали.
  • Реклама должна была дать дополнительные продажи.

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

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

Декомпозиция, задача без полного набора данных, настолки и маркетинг
Без рекламы события шли бы по одному из этих сценариев. По какому — я не знаю.Читать полностью »

Столкновение со стенкой на скорости 100 км/ч, неприятный сюрприз
Две одинаковые машины, каждая из которых движется со скоростью 100 км/ч, сталкиваются лоб в лоб. Равносильно ли это столкновению с бетонной стеной на скорости 200 км/ч?

Абсолютно упругий велосипедист на скорости 100 км/ч сталкивается лоб в лоб с тяжелым поездом, также двигающимся со скоростью в 100 км/ч. Отскочит ли при этом велосипедист со скоростью 300 км/ч?

Если на вопросы вы ответили "нет, да", то вы правы и ничего нового я вам не расскажу. А остальных приглашаю под кат. Никакой софистики там нет.
Читать полностью »

В написанной на днях статье Вернулся невод с тиной морскою я дал ссылку на частотный словарь Википедии. Колличество скачиваний на порядки превзошло все мои ожидания. Я почувствавал огромное духовное родство с читателями Хабра. Одна часть скачавших (как и я!) любит всячески возиться со словами и словарями, а вторая часть (как и я!), увидев на просторах сети интересный артефакт, тут же хватает его и тащит к себе в гнездо, а что с ним делать — потом разберёмся!

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

А для второй части, для тех, кто скачал словарь, а теперь мучительно думает, что делать со свалившимся счастьем, я хочу написать несколько статей. Собственно с этой и начну.
Читать полностью »

Как готовиться к хакерскому турниру Привет!
Меня несколько раз спросили, как лучше готовиться к предстоящему первому турниру по информационной безопасности. Я опросила наших безопасников и админов, в том числе, тестировавших игру, и составила небольшой список ниже. Думаю, это уже будет полезно тем, кто только делает первые шаги в инфобезопасности.

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

Коротко, сюжет будущего турнира: вы должны доказать, сможет или нет кто-либо проникнуть в корпоративную сеть извне и получить информацию, оставшись незамеченным.Читать полностью »

От Аристотеля к Витгенштейну

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

Предисловие

Развитие информатики как науки представляется рекой, которая рождается в далеком прошлом (Евклид, III век до н.э.; Вавилон, XIX век до н.э.; а возможно и раньше) из едва заметных ручейков первых алгоритмических вычислений. Неспешно двигаясь по истории, ручейки объединяются в реку, которая, неся свои воды через века, вбирает в себя притоки из смежных дисциплин, накапливает величественность и мощь и, наконец, срывается ниагарским водопадом из второго в третье тысячелетие, превращаясь в стремительный бурлящий поток, который захватывает и несет с собой из прошлого в будущее миллионы людей.

Размышления о программировании

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

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

Проблема четырёх красок предложенна в 1852 году Фрэнсисом Гутри

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

Стоит отметить две необходимые характеристики этой карты:

  • Граница между любыми двумя областями является непрерывной линией.
  • Каждая область является односвязной.

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

image

Единственным принятым доказательством, является выведенное из идей Альфреда Кэмпе в 1880 году (его изначальное доказательство увидело свет в 1879 году[1]), что любую карту можно раскрасить в 5 цветов.

Почти сорок лет назад, в 1976 году, в Иллинойском университете, Кеннет Аппель и Вольфганг Хакен предоставили доказательство. В качестве доказателства послужила компьютерная симуляция, которая перебирала все возможные конфигурации карт и выявила минимальное количество цветов равных четырем. Алгоритм симуляции пытались многократно упростить, чтобы проверить доказательство, но к сожелению, безуспешно. Эти события вызвали сомнения у многих математиков, тем более, что описание симуляции занимало аж 741 страницу.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js