Вид для печати
Имеет смысл только убирать по одной (или по две) монете с каждой чаши весов, уменьшая тем самым число монет, оставшихся на весах и содержащих фальшивую. Перекладывание монет в худешм случае (ничего не поменялось в положении весов) забирает одно взвешивание, но не сужает круг поиска.Цитата:
Сообщение от Меламори
Пока я у себя ошибки не вижу.
Во втором взвешивании из 6 монет на весах (3+3) мы 2 убираем, а 2 меняем местами. Смотрим, что получилось. А получается 3 варианта по 2 монеты.
Вот вам и математика.
Не так. Если переложили, но ничего не поменялось, значит переложенные монеты - нормальные, а фальшивка среди других.Цитата:
Перекладывание монет в худешм случае (ничего не поменялось в положении весов) забирает одно взвешивание, но не сужает круг поиска.
Меламори, Вы правы, а я неправ. И неправ в том что пытался свести эту задачу к простому двоичному поиску на неупорядоченном множестве. Ваше решение показало, что при неуравновешенных весах после первого взвешивания дальнейший двоичный поиск осуществляется на упорядоченном множестве (весы неуравновешены) двух подмножеств, каждое из которых состоит из трех элементов. Именно это обстоятельство я и не учел, что привело к моей ошибке.
:)Цитата:
Ваше решение показало, что при неуравновешенных весах после первого взвешивания дальнейший двоичный поиск осуществляется на упорядоченном множестве (весы неуравновешены) двух подмножеств, каждое из которых состоит из трех элементов.
Чес слово, с трудом сейчас осознаю оба этих выражения :)Цитата:
...разумное исчерпание трансцендентных мотивов обрушивает человека в полярную ночь иррациональности...
Все просто. Перед первым взвешивании Вы не знали точно, содержат выбранные Вами 6 монеток фальшивую или нет. И первое взвешивание позволило определить две группы монет, числом не более 3, содержащие фальшивую монету. Второе взвешивание позволило (в худшем случае) группу из 2-х монет, содержащую фальшивую. После этого достаточно одного взвешивания одной из этих монет с нефальшивой, что бы определить фальшивую. Истинно двоичный поиск был бы в случае, если взвешивание производил весовщик, который выдавал бы Вам после каждого взвешивания просто набор монет, содержащий фальшивую:Цитата:
Чес слово, с трудом сейчас осознаю оба этих выражения
1.после превого взвешивания - либо 4 монеты, либо (при худшем раскладе) 6. 2.после второго (для худшего расклада после првого) - либо 2, либо (при худшем раскладе при втором взвешивании) 4.
3.После третьего (для худшего расклада при втором) - либо фальшивую, либо (при худшем раскладе) 2.
4. И тогда при худшем раскладе для первых трех взвешиваний нужно четвертое, чтобы найти фальшивую.
Вот решение задачи про 12 монет как алгоритм для составления программы:
Пронумеруем монеты как 1, 2, …, 12. Взвешивание обозначим как V.
а) 1,2,3,4 V 5,6,7,8 Если >, то е), если <, то к), если =, то б).
б) 9,10,11 V 1,2,3 Если >, то г), если <, то д), если =, то в).
в) 12 V 1 Если >, то 12 тяжелее, если <, то 12 легче, = не может быть.
г) 9 V 10 Если >, то 9 тяжелее, если <, то 10 тяжелее, если =, то 11 тяжелее.
д) 9 V 10 Если >, то 10 легче, если <, то 9 легче, если =, то 11 легче.
е) 1,2,5,6 V 3, 7, 9,10 Если >, то з), если <, то и), если =, то ж).
ж) 4 V 10 Если >, то 4 тяжелее, если < не может быть, если =, то 8 легче.
з) 1,7 V 10, 11 Если >, то 1 тяжелее, если <, то 7 легче, если =, то 2 тяжелее.
и) 5,3 V 10, 11 Если >, то 3 тяжелее, если <, то 5 легче, если =, то 6 легче.
к) 1,2,5,6 V 3, 7, 9,10 Если >, то н), если <, то м), если =, то л).
л) 4 V 10 Если <, то 4 легче, если > не может быть, если =, то 8 тяжелее.
м) 1,7 V 10, 11 Если >, то 7 тяжелее, если <, то 1 легче, если =, то 2 легче.
н) 5,3 V 10, 11 Если >, то 5 тяжелее, если <, то 3 легче, если =, то 6 тяжелее.
Nass, рекурсивный алгоритм был бы изящнее.
Это как?Цитата:
рекурсивный алгоритм
Это как в стихотворении "В доме, который построил Джек".
Возможно, хотя мне это кажется уже лишними наворотами, рекурсию целесообразно использовать для более сложных алгоритмов, а тут все просто.Цитата:
Сообщение от Smic
Кстати, этот алгоритм не мой. Мое решение более запутано, я не стала его публиковать, что бы голову всем не морочить :) Этот алгоритм мне понравился, тем что он очень понятный и его можно адаптировать под любое количество монет до 13.
Вот задачка попроще, логическая, не для программирования:
Есть стена, высотой 100 м. На верху и на высоте 50 м на ней закреплены крючки. Вы находитесь на вершине, у вас есть веревка длинной 75 м и нож. Длиной узлов можно пренебречь (+1,5 м веревки). Как спуститься вниз?
Nass, что является условием "выживания": длина веревки которая привязывает тебя к крюку, не должна превышать высоту крюка на стене или что-то другое?
Не програмист. Но по-моему можно решить гораздо легче:
Дано: 13 монет, одна из которых легче остальных и весы.
Задача: за 3 взвешивания найти её.
Решение:
1е взвешивание: (6v6 +1 в стороне) по 6 монет на каждой чаше. Если равновесие, то легче монета, которая не на весах ( 6+6=12 :-) ) В противном случае легкая монета в той кучке, которая легче. Взвешиваем её...
2е взвешивание: (3v3)по 3 монеты .... Какая кучка легче - там и легкая монета. Взвешивам эту кучку...
3е взвешивание: (1v1 +1 в стороне) по 1 монете на чаше и одна не на весах. Если на весах равновесие, легкая монета не на весах. В противном случае выбираем монетку на весах :-)
Можно, если "облегчить" условия задачи:Цитата:
Но по-моему можно решить гораздо легче
В исходной задаче неизвестно, в какую сторону (большую или меньшую) отличается вес фальшивой монеты.Цитата:
Дано: 13 монет, одна из которых легче остальных
а... ну тата я не знаю.... :-)
Привет Всем!
Зашёл сюда впервые (знакомые посоветовали), понравились пока темы “Реклама” и “Логика” (кой на чём прокололся, каюсь).
С 12 монетами легко, а как с 13 так и не понял.
И хочется про верёвку написать (долго всё ж думал).
Отрезаем сразу 25 метров, один конец привязываем к крюку, на втором делаем петлю, пропускаем в неё 50-ти метровую верёвку и связываем её концы. спускаемся на этой конструкции до высоты 50-ти метров, развязываем узел и имеем 50-ти метровую верёвку, на которой и спускаемся до земли (или где там стена построена).
И идём пить пиво.
Надеюсь всё верно.
И спасибо девушке которая такую тему создала!!!
Да не за что :)
Задача:
Мама старше своего сына на 21 год. Через шесть лет она будет старше его в пять раз.
Вопрос:
Где папа?
На маме
Сол, ну и где папа?
Это в догонку к слонам и жирафам.
Вопрос: Что такое "Два крыла два колеса"
Ответ: Муха на велосипеде.
Вопрос: Как узнать есть ли муха в холодильнике?
Ответ : Прикладывать ухо к холодильнику не стоит, лучше посмотрите не стоит ли рядом с холодильником мухин велосипед! :cool:
Tigra_buh, Меламори уже ответила:Цитата:
Сол, ну и где папа?
Цитата:
На маме
Абсолютно кстати правильно ответила! Если решить несложную пару уравнений, то получим возраст сына (минус 9 месяцев) :-))) Ну и где в это время может быть папа? :yes: :yes: :yes:
Следующая задачка (довольно сарая, услышал её лет 10 назад):
Пастух с сыновьями рано утром отправился на рынок продавать свежее мясо.
Весов с делениями у него небыло. Были только показывающие равновесие (с двумя чашами, типа аптекарские).
По пути на рынок он нашел на дороге булыжник весом в 40 кг. и разбил его на четыре куска. Определить вес этих кусков, если при помощи них он мог взвесить мяса от 1 до 40 кг (1,2,3,...,38,38,40) кладя на чаши весов части булыжника...
PS: К условиям задачи не придираться:
-типа, откуда он узнал,что булыжник весит 40 кг.
- как он смог разделить булыжник на части
- ...причем части весили ровное кол-во кг.
- и т.п.
Это не важно. :-) Важно найти вес каждой части. Дерзайте.
PPS: Просьба кто ответ знает, сразу его не писАть. Пусть народ пошевелит извилинами...
Удачи.
inc.
MOLE,
1, 3, 9 и 27 кг?
Маладец!!!! Верно.
Какие все умные!!!!
Троичная система счисления, однако...Цитата:
Сообщение от Меламори
Эта совсем для детей, как оказалось.
Надо: продолжить ряд букв.
О, Д, Т, Ч, П, Ш,...
И ещё одна (не сомневаюсь что кому-то известна, а может и многим).
Муж с женой собираются в театр. Жена долго одевается, наконец выходит из комнаты. Увидев её, муж произносит следующюю фразу:
- Ты уже раздевайся и мы пойдём, или одевайся и мы остаёмся.
Вопрос: В чём была жена? :wow:
Блин, Сол, я не первую не смог решить, не вторую.... :-/
Давай еще денек клерки подумают и колись с решением... :-)
С, В, Д, Д, О, Д...Цитата:
Сообщение от Сол
Абсолютно верно, почему не скажу пока, может кто ещё хочет подумать.Цитата:
С, В, Д, Д, О, Д...
ps: Кстати, в своё время, я тоже не решил ни первую, ни вторую :hmm:
мне только тапочки приходят на ум.Цитата:
Сообщение от Сол
Это как, в театр босиком, да? :wow:
Может какие-то драгоценности?...
снять тапочки, одеть туфли.Цитата:
Сообщение от Сол
или халат.
А ответ то у вас есть? И он публиковаться будет? Или пока сами не додумаемся?
Ладно, публиковаться - так публиковаться.
Внимательно читаем вопрос.
Жена была в шоке. Как любой нормальный человек, на её месте.Цитата:
В чём была жена?
Последовательность букв - это первые буквы цифр:
Один
Два
Три
Четыре
Пять
Шесть
...
