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



[profile] 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 часов. :)

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 19th, 2017 11:03 am
Powered by Dreamwidth Studios