Взвешиваем два раза по две монеты, второй раз меняя 2 монеты местами.

например:

1,2 против 3,4
1,3 против 2,4

получили результат

1,2 < 3,4
1,3 < 2,4
фальшивая монета №1


Если наоборот, то фальшивая монета которая ушла

Если разніе значения больше менше - неповезло




нет пост 32

Вы не хотите внимательно исследовать все случаи, а не самые простые "частные"

Что делать, если мы взвесили две кучки по 4 шт., и весы отклонились? Причем мы не знаем, в какой из двух куч фальшивая монета. Знаем только, что в этих двух.

А, ну тогда проще. Скатываемся в троичную систему Записваем от 1-го до 12-и в троичной, меняем 2 на 0 а 0 на 2, и т.д. Долго объяснять, но суть в этом?

Объединяю два своих поста в один:
1. кидаем по 4 монеты. Вес равный.
2. добавляем по одной монете в каждую чашу.
3. если равновесие сохраняется, значит монета-одна из двух оставшихся. Берём любую и взвешиваем с одной из монет, которая на весах. Если вес одинаковый-значит фальшивка осталась не взвешенной
А если вес не равный, значит одна из двух монет (последних)-фальшивая.
Стало быть берём одну из этих двух монеток и взвешиваем с любой из первых восьми(4+4)
Если первая по весу одинаковая-значит вторая-фальшивка.

Кидаем по 4 монеты. Вес неравный. Дальше?


Самый простой вариант - тупо перебором и комбинированием. Но вообще есть алгоритм для N взвешиваний

Кстати, есть миф, что людей, которые решали эту задачу в течение двух часов - брали работать на Лондонскую фондовую биржу

Сообщение отредактировал King - Apr 27 2009, 23:18

Изначально ты высказывал такую теорию:
В идеале, когда мы взвесили 2 кучки по 4 монетки они должны быть равны по весу. Тогда мы точно знаем, что фальшивая монета в третьей нетронутой кучке.


Целенаправленно ввёл в заблуждение

Сообщение отредактировал VGS - Apr 27 2009, 23:20

Я сказал, что это идеальный частный случай. Мы задачу решаем или как?)

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

Так, допустим у нас кучки 1234, 5678, 9,10,11,12. Перевес /

Мы знаем, что 9-10-11-12 - правильные монеты.

На второе взвешивание берем в левую чашу например монету 1 и 3 штуки из правой чаши. Например, 6-7-8. В правой остается монета 5, плюс мы к ней добавим 3 монеты из стопудово честных. Получается, что если перевес останется, то левандосовская либо монета 1 (тяжелая), либо монета 8 (легкая). Если выровнялось, то выходит, что гнали монеты, которые мы забрали из левой чаши. А если перекосило в другую сторону, получается, что козлина, которую мы ищем, находится среди 6-7-8.

Если перевес остался - берем наманую монету и вешаем с 1. Если ровно - фальшивая 8. Если перекос - все понятно, причем даже станет понятно, легкая она или тяжелая. Если ищем среди 2-3-4, то знаем, что фальшивая тяжелее, так как весы выровнялись, значит берем 2 и 3 и смотрим. Если ровно - мы искали 4. Если перевес - мы искали тяжелую. Ну с монетами 6-7-8 та же херня тока наоборот.

Вроде ниче не напутал.

Боря, ты засранец, я сто лет ручкой по листу не писал)

Сообщение отредактировал kevindark - Apr 27 2009, 23:30

Перевирая известного классика:
"Пишите, Шура, пишите" )))

Ты уже близок к финальному решению
У тебя получается 4 взвешивания итого. Но ход мыслей абсолютно верен)

Ладно, чтобы не мучался Второе взвешивание не по 4 монеты

Сообщение отредактировал King - Apr 27 2009, 23:57

Не понял, почему 4??! три.. первым определяем эталонную кучку, вторым определяем одну из трех комбинаций, в которых есть левая монета, третьим определяем монету...

6-7-8 не найти за одно взвешивание....

Как это не найти? Я ж написал как) Почему это может быть не так?

Смотри, 6-7-8 переставили, перекосило в другую сторону.
Как нам извлечь за одно взвешивание неправильную монету из 6-7-8?
Одна монета лишняя.

Взвешиваем 6 и 7. Если ровно, 8 - фальшивка. При перекосе фальшивка та, что легче.

Все верно, сорри, невнимательно прочитал один из постов (засыпал уже)

Поздравляем Кевина!

1-е взвешивание:
1-2-3-4 / 5-6-7-8

2-е взвешивание:
если
1-6-7-8 / 5-9-10-11, то
Либо монета 1, либо монета 5 фальшивые.

если
1-6-7-8 = 5-9-10-11, то
фальшивка в 2-3-4 и она тяжелее.

если
1-6-7-8 \ 5-9-10-11, то
фальшивка в 6-7-8 и она легче.

Дальше все просто.

Второй вариант решения:
Нумеруем шары 1, 2, 3, 4, ... 12.

Делим на три части по 4 шары: (1 2 3 4) (5 6 7 8 ) (9 10 11 12)
1. Взвешиваем первые две группы (1 2 3 4) и (5 6 7
Если они равны, то искомый шар точно в третьей группе.
2. Взвешиваем шары по два (9 10) и (1 12) - тут шар 1 точно не искомый. Если они равны, то искомый шар 12. Если нет, то запоминаем состояние весов (тяжелее/легче).
3. Взвешиваем шары (9 10). Если они равны, то искомый шар 11.
Если состояние весов не изменилось, то искомый шар 9. Если состояние весов изменилось, то искомый 10.

Если после первого взвешивания группы разного веса, то запоминаем состояние весов.
2. Взвешиваем по три шара (1 2 5) и (3 6 12). Если они равны, то шар 4 или 8 искомый. Шар 12 точно не искомый.
3. Взвешиваем шары (4 12). Если равны, то искомый шар 8. Если нет, то искомый шар 4. Finish.

Если состояние весов изменилось после второго взвешивания, то искомый шар 3 или 5.
3. Взвешиваем (3 12) получаем решение. Равны - искомый 5, неравны - искомый 3.
3. Если состояние не изменилось, то взвешиваем шары (1 12). Если равны - искомый 2, если нет - искомый 1.

Плюс второго алгоритма, что таким способом проще писать алгоритм для M шаров и N взвешиваний.

Сообщение отредактировал King - Apr 28 2009, 11:40

А_А_А_А_А_А_А_ - мозК поламал!!!