Обновить

Собеседование по алгоритмам: разноцветные соседи Есть двадцать клеток, каждая из которых либо белая, либо чёрная....

Время чтения1 мин
Охват и читатели3.7K
Всего голосов 3: ↑3 и ↓0+3
Комментарии17

Комментарии 17

Подпишусь на ответы)

Если белые и черные клетки встречаются только один раз (проверила, покликав на клетки), то нам поможет бинарный поиск.

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

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

Ну да, так и есть. А какой у Вас подход?

Что то типа метода бисекции

ага!

Метод дихотомии не подвёл ни разу. Было где-то 8 попыток.

Бинарный поиск, хорошо, а как из условия понять что переход белое -> черное только один?

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

Напомнило классическую историю о 64 блокерах и продаванах чудо софта по предсказанию рынка. Типа, в первый месяц отправили по 32 прогноза на рост и 32 на падение, потом оставшимся верно угаданным по 16, потом по 8 потом по 4, и паре последних уверившихся в 6 абсолютно точных прогнозов продали суперсофт по миллиону долларов за экземпляр. Бинарный поиск рулит, но ваша программка жульничает выдавая всегда наихудший вариант для угадателя.

Красивая история, ага =) Я бы не сказал, что программа жульничает: как и во многих подобных играх, тут нужно обыграть противника, который может играть оптимально (что бы это ни значило).

По описанию думал, что клетки "либо чёрные, либо белые", а по факту последовательность белых, которые где-то переходят в последовательность чёрных.

Первую задачу в 5 кликов не решить, вторую - легко.

Ну, это пазл себя так ведёт. Но за пять кликов обе версии решаются.

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

Бинарный поиск. Неважно, что там с количеством переходов и количеством соседей одного цвета. После любого клика в середине мы получаем два полуотрезка, у одного из которых концы разного цвета. Над ним и издеваемся на следующем шаге. Для 20 клеток надо roundup(log2(20-1)) = 5 попыток.

А можно сделать так, чтобы цвета не подстраивались под мой поиск? Я чуть не сошёл с ума, пытаясь понять, почему по статистике мой путь поиска не сокращался.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации