Логика

[sema]

Меламори, по чему до 13? есть прикол с 16-ю. Задача № 2 http://bspu.ab.ru/Department/WMiP/Me.../logika_b.html

[Smic]

Меламори, по чему до 13? есть прикол с 16-ю. Задача № 2 http://bspu.ab.ru/Department/WMiP/Me.../logika_b.html

Это не прикол. Это просто совсем другая задача.

[sema]

Smic, они все похожие есть даже с 40 монетками.

[Smic]

sema, они похожи только наличием двоичного поиска (весы) и тем, что в них используются монетки. Но ищется в каждой задаче разное.

[sema]

Не могли бы Вы представить это решение?

с 12-ю решение.

{1,2,3,4,5,6,7,8,9,10,11,12} - множество всех монеток
Lk - множество монеток на левой чашке весов при k-м взвешивании
Rk - тоже для правой чашки
Н - множество хороших монеток
н - хорошая монетка
ф - фальшивая монетка

I взвешивание

L1 = {1,2,3,4}, R1 = {5,6,7,8}
возможны два случая:
1) Весы в равновесии
Н = {1,2,3,4,5,6,7,8}, ф принадлежит {9,10,11,12}
Нужно найти среди четырех монеток фальшивую за два взвешивания. Этот случай можно свести к взвешиванию II' (см. ниже).

2) Весы отклонились в какую-либо сторону, тогда
H = {9,10,11,12}, ф принадлежит {1,2,3,4,5,6,7,8}

II взвешивание

L2 = {3,4,6,7}, R2 = {2,8,н,н}
возможны 3 случая:
2.1)Весы в равновесии, значит
ф принадлежит {1,5}
За одно взвешивание среди них можно найти фальшивую, сравнив любую из них с н
2.2)Весы отклонились в ту же сторону, что и при первом взвешивании, значит фальшивая монета среди тех, которые не перекладывались в соседнюю чашку, т.е.
ф принадлежит {3,4,8}
2.3)Весы отклонились в сторону противоположную первому взвешиванию, значит фальшивая монета среди тех, которые были переложены на соседнюю чашку, т.е.
ф принадлежит {2,6,7}

Случаи 2.2 и 2.3 очень похожи.
Мысленно снимем с каждой из чашек по две хороших монетки. Имеем: на одной из чашек две "подозрительных" монетки, на другой одна "подозрительная" и одна заведомо хорошая.
Пусть для определенности
L2' = {a,b}, R2' = {c, н}. Это обобщенное взвешивание II'. Мы его не проводим, но знаем результат из взвешивания II.

III Взвешивание

L3 = {a}, R3 = {b}
Возможны три случая:
а) Весы в равновесии ==> фальшивая монетка c
б) Весы отклонились в ту же сторону, что и при взвешивании II' ==> фальшивая монетка а
в) Весы отклонились в противоположную сторону по сравнению с взвешиванием II' ==> фальшивая монетка b

[sema]

sema, они похожи только наличием двоичного поиска (весы) и тем, что в них используются монетки. Но ищется в каждой задаче разное.

гы так их обычно программерам задают )))

[Smic]

Случаи 2.2 и 2.3 очень похожи.
Мысленно снимем с каждой из чашек по две хороших монетки

С одной чашки это можно сделать, т.к. сниамются две заведомо хорошие монетки, положенные вместо монеток 1 и 5. Но как Вы найдете две хорошие монеты из четырех, лежащих в чаше весов, в которую Вы не добавляли заведомо хорошие монеты? Не катит это решение....

[sema]

Smic, ты что думаешь это мое решение? у меня от такого мозги заклить может

[Smic]

sema, теория задачи о двоичном поиске - вещь простая и обойти ее "практически невозможно".....

[sema]

Smic, Вообще вариантов/попыток решения масса, но ты не одинок в своем мнении, что задача решения не имеет

[Smic]

sema, я рад за тех, кто со мной согласен в данном вопросе....

[sema]

Smic, ну так нарисовал бы доказуху, что за 3 взвешивания задачка решения не имеет

[Smic]

Smic, ну так нарисовал бы доказуху, что за 3 взвешивания задачка решения не имеет

Так вот она:

Решения при такой постановке нет. Для гарантированного нахождения требуется Log(10) по степени 2, т.е. более трех взвешиваний.

И называется она "двоичный поиск". И из теории решения этой задачи известно, что минимальное число попыток, необходимое для гарантированного нахождения с помощью двоичного поиска нужного элемента из множества N элементов требуется Log(N) по степени 2 попыток.

Просто каждый акт двоичного поиска (взвешивание) сужает область поиска в два раза. Исходя из этого, надо посчитать, за сколько попыток двоичного поиска (взвешиваний) множество из N элеменотов сужается до величины, меньшей 1. И число таких попыток равно Log(N) по степени 2, округленному до ближайшего целого сверху. К случае с 10-ю монетками это число равно 4.

[Меламори]

Для 10 монет. Мож раскритикуете, но я пока не вижу засады в сем решении.
Обозначения - см. пост 65

10 монет {0;1;2;3;4;5;6;7;8;9;}
L1={0;1;2} R1={3;4;5}
Варианты:
I) равновесие, Н={0;1;2;3;4;5}, ф={6;7;8;9}
L2={6;7} R2={1;2}
варианты:
1) равновесие, ф={8;9}
L3={8} R3={1}, если равны, ф={9}, нет, ф={8}
2) перевешивает одна чаша, ф={6;7}
L3={6} R3={1}, если равны, ф={7}, нет, ф={6}
II) Перевешивает 1 чаша, ф={0;1;2;3;4;5}, Н={6;7;8;9}
L2={0;3} R2={1;4}
варианты:
1) равновесие, ф={2;5}
L3={2} R3={1}, если равны, ф={5}, нет, ф={2}
2) одна чаша перевешивает, та же, что и при 1 взвешивании, ф={0;4}, L3={0} R3={9}, если равны, ф={4}, нет, ф={0}
3) одна чаша перевешивает, другая, чем при 1 взвешивании, ф={1;3}, L3={1} R3={9}, если равны, ф={3}, нет, ф={1}

Smic, Ваше слово!

[динка]

Меламори

Фигня в том, что в задании нет указания на то, что ф.м. тяжелее...

1 из них или легче, или тяжелее

[sema]

прально мало кто учитывает, что она может быть тяжелее или легче

[Smic]

Ошибка здесь. После второго взвешивания:

2) одна чаша перевешивает, та же, что и при 1 взвешивании, ф={0;4}

Если Вы при после первого взвешивания при неуравновешенных чашах убираете по одной монете с каждой чашки и производите второе взвешивание, то у Вас может быть две возможных ситуации:
1. положение чаш не изменилось, значит у вас на чашах весов 4 монеты, одна из которых фальшивая, для того что бы определить какая, нужно еще 2 взвешивания, итого 4.
2. чаши уравновесились, значит у Вас на руках две убранные монеты, одн из которых фальшивая. Необходимо еще одно взвешивание, чтобы определить какая.
Т.е. Вам нужно все равно не менее 4-х взвешиваний.

[Меламори]

Если положение чаш не изменилось, то значит, что мы и убрали не фальшивку (2 и 5), и переложили не фальшивку (1 и 3), остаются - 0 и 4.
Если изменилось на противоположное, значит переложили фальшивку. А перекладывали - 1 и 3.
Если стало равновесие, то убрали фальшивку (2 и 5)

[Меламори]

Следите за номерами монет.

[Smic]

Следите за номерами монет.

Это ни к чему не приведет. Математику не обманешь.

[Smic]

Если положение чаш не изменилось, то значит, что мы и убрали не фальшивку (2 и 5), и переложили не фальшивку (1 и 3), остаются - 0 и 4.
Если изменилось на противоположное, значит переложили фальшивку. А перекладывали - 1 и 3.
Если стало равновесие, то убрали фальшивку (2 и 5)

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

[Меламори]

Пока я у себя ошибки не вижу.
Во втором взвешивании из 6 монет на весах (3+3) мы 2 убираем, а 2 меняем местами. Смотрим, что получилось. А получается 3 варианта по 2 монеты.
Вот вам и математика.

[Меламори]

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

Не так. Если переложили, но ничего не поменялось, значит переложенные монеты - нормальные, а фальшивка среди других.

[Smic]

Меламори, Вы правы, а я неправ. И неправ в том что пытался свести эту задачу к простому двоичному поиску на неупорядоченном множестве. Ваше решение показало, что при неуравновешенных весах после первого взвешивания дальнейший двоичный поиск осуществляется на упорядоченном множестве (весы неуравновешены) двух подмножеств, каждое из которых состоит из трех элементов. Именно это обстоятельство я и не учел, что привело к моей ошибке.

[Меламори]

Ваше решение показало, что при неуравновешенных весах после первого взвешивания дальнейший двоичный поиск осуществляется на упорядоченном множестве (весы неуравновешены) двух подмножеств, каждое из которых состоит из трех элементов.

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

Чес слово, с трудом сейчас осознаю оба этих выражения

[Smic]

Чес слово, с трудом сейчас осознаю оба этих выражения

Все просто. Перед первым взвешивании Вы не знали точно, содержат выбранные Вами 6 монеток фальшивую или нет. И первое взвешивание позволило определить две группы монет, числом не более 3, содержащие фальшивую монету. Второе взвешивание позволило (в худшем случае) группу из 2-х монет, содержащую фальшивую. После этого достаточно одного взвешивания одной из этих монет с нефальшивой, что бы определить фальшивую. Истинно двоичный поиск был бы в случае, если взвешивание производил весовщик, который выдавал бы Вам после каждого взвешивания просто набор монет, содержащий фальшивую:
1.после превого взвешивания - либо 4 монеты, либо (при худшем раскладе) 6. 2.после второго (для худшего расклада после првого) - либо 2, либо (при худшем раскладе при втором взвешивании) 4.
3.После третьего (для худшего расклада при втором) - либо фальшивую, либо (при худшем раскладе) 2.
4. И тогда при худшем раскладе для первых трех взвешиваний нужно четвертое, чтобы найти фальшивую.

[Nass]

Вот решение задачи про 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 тяжелее.

[Smic]

Nass, рекурсивный алгоритм был бы изящнее.

[Меламори]

рекурсивный алгоритм

Это как?

[Smic]

Это как в стихотворении "В доме, который построил Джек".