С Новым годом! Форум программистов, компьютерный форум, киберфорум
Игры разума
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.86/14: Рейтинг темы: голосов - 14, средняя оценка - 4.86
67 / 4 / 3
Регистрация: 11.09.2012
Сообщений: 244
Записей в блоге: 6
1

Пять пиратов(очень сложная задача)

18.09.2012, 18:13. Показов 2866. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Считаю эту задачу довольно таки сложной. Так как не смог ее понять и подобрать ответ. Хотя мне и давали подсказки.
Ответ я знаю, и он довольно большой. Но сам сразу говорю, решить не смог( Очень долго парился



Сама задача:
Пять пиратов на острове должны разделить между собой сотню золотых монет. Они делят свою добычу так: старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала. Самый старший пират (из тех, кто выжил) предлагает новый план, за него голосуют по тем же правилам, а потом или делят добычу, или убивают старшего пирата. Процесс продолжается до тех пор, пока какой-то план не будет принят. Допустим, вы — старший пират. Как вы предложите разделить добычу? (Все другие пираты — жадные, мыслят очень логично, и все они хотят жить.)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.09.2012, 18:13
Ответы с готовыми решениями:

очень сложная задача
не получается ничего

Очень сложная задача с равномерным распределением
Есть 5 переменных $a $b $c $d $e которые нужно равномерно распределять по наборам переменных....

Очень сложная задача по Си для избранных
Программе задаётся целое число.Программа должна осуществлять вывод на экран всех переменных...

Задача для тех , кто хочет сломать мозг [Очень сложная]
Завтра экз. , баллов нехватает , если не докажу прогу , то енд. Очень прошу помочь. Вся сложность в...

7
174 / 84 / 2
Регистрация: 06.05.2012
Сообщений: 324
18.09.2012, 18:31 2
MaxStein,
спойлер
дать монет по 10 двоим младшим , я думаю , что согласятся.
0
67 / 4 / 3
Регистрация: 11.09.2012
Сообщений: 244
Записей в блоге: 6
18.09.2012, 18:37  [ТС] 3
Ок_сана, Нет, не правильно.
Ок_сана
Нужно не думаю, а быть точно уверенным. Говорю же, очень сложная задача мне показалась
0
137 / 126 / 14
Регистрация: 03.07.2012
Сообщений: 355
18.09.2012, 19:30 4
Кликните здесь для просмотра всего текста
Отказаться от своей доли. А двум любым пиратам дать по 50 монет. Эти двое точно проголосуют за это
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
18.09.2012, 19:33 5
Ответ
Себе взять 34 монеты двум другим по 33, а двоим ничего
0
Комп_Оратор)
Эксперт по математике/физике
8950 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
18.09.2012, 19:55 6
У меня так вышло:
вроде бы...
Старший из 5-ти может выжить, если предложит последнему и предпоследнему по старшинству, по 2 монеты, а себе оставит остальное.

Я предположил, что старший не участвует в голосовании, иначе всё по-другому будет.
0
67 / 4 / 3
Регистрация: 11.09.2012
Сообщений: 244
Записей в блоге: 6
18.09.2012, 20:07  [ТС] 7
Ну близко близко. смысл почти тот.

Кому не лень читать:
Ответ
Чтобы найти решение, нужно понять, что ситуацию с n пиратов можно анализировать на основе ситуации с n — 1 пиратов и т.д., пока вы не доберетесь до «базовой ситуации», решение в которой будет абсолютно ясным.
Базовая ситуация — это один выживший пират. Очевидно, что единственный пират предложит отдать ему все монеты. Ход сделан!
А что если пиратов двое? Старшему из них придется предложить, как делить добычу. В условии головоломки говорится, что предложение принимается, если «по крайней мере половина пиратов» за него проголосует. Это значит, что достаточно одного голоса старшего пирата, чтобы предложение было принято. Следовательно, если пиратов всего двое, то старшему из них бояться нечего, и он может не беспокоиться о том, что думает его товарищ. Будучи жадным негодяем, старший пират предложит отдать все сто монет ему. Результаты голосования будут такими: один голос «за» и один «против» — это значит, что предложение будет принято.
Может показаться, что старший пират всегда получит то, чего он хочет. Не совсем так. Представьте, что он решил воспользоваться тем же трюком, если пиратов трое. Давайте пронумеруем пиратов, начиная с самого младшего: №1, №2, №3. План раздела добычи должен предложить номер 3. Если он предложит такой план: «Все достается мне, а вы, ребята, ничего не получите», то следующий пират в этой последовательности (№2) точно проголосует против подобного предложения. Пират №2 знает, что он сам получит все, если останутся только два пирата после того, как №3 будет убит. Решающим оказывается голос пирата №1. Он ничего не получает, если проголосует за план пирата №3 , но также ничего не получит, если проголосует против, если останутся только два пирата. У него нет никаких причин, чтобы предпочесть один вариант другому.
Итак, если №3 умен, как это предполагается в головоломках, он попытается получить поддержку пирата №1. Нужно также учесть, что пират №3 жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны пирата №3 будет дать №1 одну золотую монету, №2 — ничего, а ему самому — оставшиеся девяносто девять монет! Поскольку №1 также рассуждаете логично, но поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если пират №3 будет убит. Пират №1 проголосует за план раздела добычи (как и №3, конечно), и это предложение будет принято двумя голосами против одного несмотря на все проклятия накачавшегося с горя ромом пирата №2.
Теперь рассмотрим ситуацию с четырьмя пиратами. Четыре — это опять четное число. Это значит, что самому старшему пирату достаточно всего одного голоса, кроме его собственного, чтобы его предложение прошло. Ему нужно ответить на вопрос: «Какой из голосов остальных трех пиратов окажется самым дешевым?»
Вернемся к ситуации с тремя пиратами. Пират №2 не получает в ней ничего, поэтому если пират №4 предложит ему хотя бы что то, то для пирата №2 будет логично проголосовать «за».
И получив голос пирата №2, пират №4 может совсем не беспокоиться о том, что думают №1 и №3. План пирата №4 будет таким: ни одной монеты для №1, одна монета для №2, ни одной монеты для №3 и девяносто девять монет для него самого.
Теперь модель нам ясна. В каждом случае самый старший пират должен «купить» ровно столько голосов, сколько ему необходимо, и как можно дешевле. Все остальные деньги достанутся ему самому.
Теперь применим эту модель к ситуации с пятью пиратами, о которой речь и идет в задаче. Вы пират №5. Вам нужно три голоса: ваш собственный и еще два. Таким образом, вам нужно что то дать двум пиратам, которые больше всего проиграют, если пиратов останется только четверо. Это пираты №1 и №3. Оба не получат ничего, если вас убьют и останется всего четыре пирата. Обоих можно убедить проголосовать за ваш план, если он им что нибудь сулит. Ваше предложение: ничего не давать пирату №4, дать одну монету №3, ничего не дать №2 и дать одну монету №1. Оставшиеся девяносто восемь монет вы оставите себе.

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

Один(самый старший или кто-нить ещё) медленно отделяет от кучи по монете остальные смотрят как только кто-нить из стоящих кричит стоп ему отдают отделённую кучу, и так пока не останется 1 пират и тот кто отделял монеты. тогда один из уже получивших монеты начинает отделять из оставшейся кучи а те двое по тому же принципу смотрят и кричат стоп. подобная задача уже встречалась
0
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
22.09.2012, 21:01 8
Ответ
Зачем предлагать младшим? Они не могут быть убиты по таким правилам в принципе и будут надеяться забрать всё. А раз так, то проголосуют против, как и второй с третьим, так как они не хотят отдавать им ничего. А вот если предложить разделить всё поровну между вторым и третьим, то они голосуют за и сам педложивший не может голосовать против, это 60% и план принят.
0
22.09.2012, 21:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.09.2012, 21:01
Помогаю со студенческими работами здесь

Минимизацию функции..Очень сложная
Грузовик должен перевозить H тонн груза в течение суток между пунктами ,расстояние между ними ...

Не очень сложная проблема связанная с count!
Столкнулся с проблемой метода count он не выводит кол-во элементов в списке по переменной: l = a1...

Очень сложная задачка, программисты, сюда!
Я загадал два двузначных числа. Ваша задача – отгадать их. Я сообщаю вам: 1) Правую цифру первого...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru