Форум умных людей

Все знают задачу про 10 мешков с золотыми монетами, в одном из них фальшивые. Предлагаю подумать и усложить задачу когда: всего мешков с золотыми монетами m, среди них есть n мешков с фальшивыми монетами. Золотая монета весит 10 гр, фальшивая 9 гр. Есть электронные весы, которые показывают вес с точностью до грамма. Считаем, в мешках неограниченное количество монет.  Нужно за одно взвешивание найти все мешки с фальшивыми монетами. Задачу необходимо решить самым оптимальным рядом (использовать минимальное количество монет при взвешивании)

Н7у тогда и применять - новое старое оптимальное решение
Из всех сундуков/мешков по порядку берем монеты начиная от 1 и кончая М - взвешиваем все разом - в зависимости от результата получаем номера фальшивых вместилищ.
ПыСы: - с весами монет 9 и 10 - вроде существует только 1 вариант попадания в неблагоприятное расположение монет, т.е. сложность с идентификацией 10-го сундука. :wall:

Показать скрытый текст

 

ответ как в старой доброй не подходит. Если брать с первого мешка одну монету, со второго две, с третьего 3, с m мешка m монет. Ложим это на весы. Получаем разницу например 4. Так как фальшивых мешков больше одного, т.е. n, то вариантов фальшивых мешков может быть много. Т.е.

1. 4 мешкок
2. 1 и 3 мешок

Если разница будет больше, например 10, вариантов будет еще больше.

может поможет великая теорема Ферма? с 1 мешка берём одну монету, со 2 мешка берем 8 монете, с 3 берём 27 , и тд.По разнице определить где могут быть фальшивые, так как никакие совпадения невозможны.Не хочу расписывать варианты так как лень, может чистые програмисты помогут?

Применить Ферма конечно можно. Но очень сложно применить... Это решение не оптимально. Так как на если будет мешков больше 15 будет просто очень сложно оперировать числами. А если  фальшивых мешков будет тоже много, то надо будет подбором вычислять из каких чисел получается сумма. Например, мешков 10:
Числа ферма: 1, 5, 7, 17, 257, 65537, 4294967297, 18446744073709551617.... и т.д ещё больше
проще взять тогда просто например 1, 10, 100, 1000, 10000, 100000, и т.д. Но тоже не оптимально.
Нужно самое оптимальное и "экономное" с точки зрения расхода монет решение.

2, 3, 8, 16 это подбор... нужна формула :)

Что есть одно взвешивание на электронных весах? Это взвешивыаешь,подбавляешь вес, подбавляешь...,подбавляешь и тд ,пока не снимешь груз и не начнёшь следующее взвешивание. Если с каждого мешка ложить последовательно по одной монете и смотреть на дисплей , то это самый экономный вариант и есть. :D

:ogo:
Как в принципе ипринятоделать на любом базаре. Но на назве в таких задачах используются "коммерческие" весы т.е. для каждой возможности вывести цифирьку на экран - на посмотреть или распечатать на чеке надо бросить монетку, коих обычно столько же, кокое количество взвешиваний разрешена в задаче.  :cool4: Практически как в банкоматах НАДРАбанка

Одно взвешивание - это когда насобирал какое-то количество монет, положил один раз на весы получил вес и всё. Добавлять по одной монеты нельзя.

У нас этих задач решено уже столько, что их тоже нужно мерить мешками  :peace:
Просто посмотрите в поиске по тегу "взвешивания"

Вот, к примеру,  один из топиков  (http://nazva.net/forum/index.php/topic,3136.msg58885.html#msg58885)