Пpиданое султана

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

Ответ: алгоритм - пропустить 37 дочерей, при этом "приметить" лучшую из них. Потом осматривать остальных и остановиться на первой, которая окажется лучше, чем "примеченная". Если таковой не окажется - взять сотую (а что ж ещё делать в этом случае). - (наведите курсор)

Катерина

предыдущая  | "Пpиданое султана" | следующая
Авторизируйтесь что бы добавить свой комментарий