Али Баба и 40 разбойников
Всем привет! Да озарит вас летнее Петербургское солнце :)
Лытдыбр
У меня дачный отпуск, поэтому могу тряхнуть стариной и написать в ЖЖ, который вроде ещё не умер, хотя и пал под натиском ВКонтакта и прочих FB. О моей счастливой жизни в роли молодого кормящего отца знают все близкие, поэтому я решил написать не об этом, а о чём-то интересном. Т.е ( Read more... )
Comments 3
На троих просто, на 40 замучаешься :)
Один делит на три кучки. Каждый выбирает какую хочет. Если выбрали разные, автоматически разделилось.
Если нет, двое вместе выбирают самую маленькую. Если совпали в выборе самой маленькой, ее отдают делившему, а остальные две делят заново по простому алгоритму.
Если и в выборе самой маленькой не совпали, то большую откладывают и делят пополам между собой, а каждую из "маленьких" делит пополам деливший разбойник. Каждый из двух других выбирает бОльшую часть из той кучки, которую он считал бОльшей. Две оставшиеся "маленькие" части "маленькой" кучи забирает деливший.
Думаю это не оптимальный алгоритм. Даже на 3х человек куча шагов, что ж на 40 будет? Постою тут, послушаю умных людей %)
Reply
Решение для 3 разбойников верное, правда в таком исполнении не понятно, как его обобщить на 40 разбойников. А делений... да, делений будет много, никуда не деться.
Можно в оставшееся время подумать, как всё же сформулировать решение, чтобы была видна возможность обобщения. Ибо так, с ходу, думаю не видно, как же делить на 4х.
Reply
https://einwill.livejournal.com/69863.html
Reply
Leave a comment