Монеты и взвешивания

[thedeemon]

Пару недель назад увидел у mr_aleph задачку: есть 12 одинаковых с виду монет, одна из них фальшивая - отличается по весу, но неизвестно в какую сторону, нужно за максимум 3 взвешивания на чашечных весах ее найти. Если знать легче она или тяжелее, то решается очень просто, но вот без этой информации у меня быстро найти решение не получилось. Потом еще несколько раз иногда возвращался к ней мыслями, но так и не решил, даже при поддержке других членов семьи.

mr_aleph тогда написал: Но потом меня посетила интересная мысль, что (мета)задача написать программу, которая строит стратегию поиска фальшивой монеты из N монет за M взвешиваний, это хороший программисткий этюд.

С этим я полностью согласен, поэтому решил написать программу, и пусть японский компьютер мне придумывает аргоритм. Задачка получилась довольно интересная, ведь не сразу ясно как именно описать предметную область и как должен выглядеть ответ: программа должна не найти монету, а по заданному числу монет и взвешиваний найти алгоритм решения задачи. В итоге у меня получилось такое решение из сотни строк Окамла с активным применением функций сильно высокого порядка и ленивых вычислений. Для 4 монет и 2 взвешиваний результат работы выглядит так:

Weigh [1 and 2]:
 if left heavier then 
  last weighting [2 and 4]:
   if left lighter then fake is 2
   if equal then fake is 1
 if left lighter then 
  last weighting [2 and 4]:
   if left heavier then fake is 2
   if equal then fake is 1
 if equal then 
  last weighting [2 and 4]:
   if left heavier then fake is 4
   if left lighter then fake is 4
   if equal then fake is 3

А для 9 монет и 3 взвешиваний вот так. Решение исходной задачки с 12 монетами программа выдала вот такое, неоптимальное но вроде рабочее. При поиске решения у меня плохо учитывается симметрия ситуаций, поэтому с ростом числа монет время работы растет очень быстро: решение для 8 монет находится за 0,2 секунды, для 9 - за 1,6с, для 10 - за 38с, а про 12 монет железяка думала 5 часов. :)

В коде очень порадовало место, где делаются выводы из очередного взвешивания:

let not_heavy (l,n,h) = (l,n,false);;
let not_light (l,n,h) = (false,n,h);;
let is_normal (l,n,h) = (false,true,false);;

let eval st w outcome = (* определение нового состояния из заданных состояния, взвешивания и результата *)
  let f = match outcome with
    | LeftLighter -> (function Left -> not_heavy | Right -> not_light | Out -> is_normal)
    | LeftHeavier -> (function Left -> not_light | Right -> not_heavy | Out -> is_normal)
    | Equal       -> (function Left  | Right -> is_normal | Out -> identity) in
  List.map2 f w st;;

Если взвешивание показало, что левая чашка легче, значит на левой не может быть тяжелой монеты, на правой не может быть легкой, а все неучаствовавшие во взвешивании монеты гарантировано нормальные. Аналогично для симметричного случая. Если весы показали равенство, значит на весах все монеты нормальные, а про остальные ничего нового сказать нельзя. Здесь f - функция, которая принимает позицию монеты и возвращает другую функцию, которая из старого состояния информации о монете делает новое. С учетом карринга, это все равно что одна функция с двумя параметрами - позицией монеты и старым состоянием, возвращающая новое состояние. Так она и используется.

Comments

много добър

[(Anonymous)]

Трябва да проверя:)