goliafffff выложил задачку на взвешивание монеток.Вот условие: "Среди 12 монет найти фальшивую за 3 взвешивания на весах-чашках. Легче или тяжелее монетка - не известно."
Мне кажется, грех тратить уйму времени на задачки, которые легко решаются перебором, так что я особо не ломал голову над ней. Но несколько человек просили посмотреть моё решение, потому публикую под катом.
Решение в общих чертах:
Жадный алгоритм даёт рашение за 3 взвешивания, причём ещё и определяет, какого именно типа фальшивая монетка (легче или тяжелее). Сортируем все потенциальные варианты (24), сортируем все возможные разбиения для взвешивания, выбираем лексикографически первое разбиение, которое в наибольшей степени уменьшит число потенциальных вариантов в худшем случае по всем трём исходам взвешивания (=, <, >), и т.п. рекурсивно.
Код, CoinWeighting.py
import itertools N = 12 def gen_all(): normal = [0]*N for i in range(N): lighter_i = list(normal) lighter_i[i] = -1 yield lighter_i heavier_i = list(normal) heavier_i[i] = +1 yield heavier_i def get_all_splits(): maxK = N//2 first = [set(x) for x in itertools.chain.from_iterable(itertools.combinations(range(N), K) for K in range(1, 1+maxK))] pairs = [] for f in first: K = len(f) minI = min(f)+1 select_second = [i for i in range(N) if (not i in f) and (i > minI)] pairs.extend((f, set(x)) for x in itertools.combinations(select_second, K)) return pairs def get_satisfies(variants, weightings): satisfactory = [] for v in variants: good = True for (first, second, outcome) in weightings: first_weight = sum(v[i] for i in first) second_weight = sum(v[i] for i in second) if ((outcome == 0) and (first_weight != second_weight) or (outcome > 0) and (first_weight <= second_weight) or (outcome < 0) and (first_weight >= second_weight)): good = False break if good: satisfactory.append(v) return satisfactory def num_satisfies(variants, weightings): return len(get_satisfies(variants, weightings)) def get_potential(variants, weightings, first, second): return max([ num_satisfies(variants, weightings + [(first, second, 0)]), num_satisfies(variants, weightings + [(first, second, -1)]), num_satisfies(variants, weightings + [(first, second, +1)]), ]) def get_best_split(variants, weightings): splits = get_all_splits() best_first = None best_second = None best_potential = len(variants)+1 for first, second in splits: cur_potential = get_potential(variants, weightings, first, second) if cur_potential < best_potential: best_potential = cur_potential best_first = first best_second = second return (best_first, best_second, best_potential) def get_index_value(variant): try: pos = variant.index(1) except: pos = variant.index(-1) return pos, variant[pos] def explore(indent, variants, weightings): #print 'len(variants) = ', len(variants) #if len(variants)<=4: print variants print '# %sNum possible variants: %d' % (' '*indent, len(variants)) if len(variants) == 0: print '# %sThis cannot happen' % (' '*indent) elif len(variants) == 1: index, value = get_index_value(variants[0]) print '# %s Answer: %d at position #%d' % (' '*indent, value, index) else: (best_first, best_second, best_potential) = get_best_split(variants, weightings) print '# %s%s' % (' '*indent, str((sorted(best_first), sorted(best_second), best_potential))) print '# %s=' % (' '*indent) new_weightings = weightings + [(best_first, best_second, 0)] explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings) print '# %s<' % (' '*indent) new_weightings = weightings + [(best_first, best_second, -1)] explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings) print '# %s>' % (' '*indent) new_weightings = weightings + [(best_first, best_second, 1)] explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings) explore(0, list(gen_all()), [])
Результат, CoinWeighting.txt
# Num possible variants: 24 # ([0, 1, 2, 3], [4, 5, 6, 7], 8) # = # Num possible variants: 8 # ([0, 8], [9, 10], 3) # = # Num possible variants: 2 # ([0], [11], 1) # = # Num possible variants: 0 # This cannot happen # < # Num possible variants: 1 # Answer: 1 at position #11 # > # Num possible variants: 1 # Answer: -1 at position #11 # < # Num possible variants: 3 # ([0, 1], [8, 9], 1) # = # Num possible variants: 1 # Answer: 1 at position #10 # < # Num possible variants: 1 # Answer: 1 at position #9 # > # Num possible variants: 1 # Answer: -1 at position #8 # > # Num possible variants: 3 # ([0, 1], [8, 9], 1) # = # Num possible variants: 1 # Answer: -1 at position #10 # < # Num possible variants: 1 # Answer: 1 at position #8 # > # Num possible variants: 1 # Answer: -1 at position #9 # < # Num possible variants: 8 # ([0, 1, 4], [2, 3, 5], 3) # = # Num possible variants: 2 # ([0], [6], 1) # = # Num possible variants: 1 # Answer: 1 at position #7 # < # Num possible variants: 1 # Answer: 1 at position #6 # > # Num possible variants: 0 # This cannot happen # < # Num possible variants: 3 # ([0, 5], [2, 3], 1) # = # Num possible variants: 1 # Answer: -1 at position #1 # < # Num possible variants: 1 # Answer: -1 at position #0 # > # Num possible variants: 1 # Answer: 1 at position #5 # > # Num possible variants: 3 # ([0, 1], [2, 4], 1) # = # Num possible variants: 1 # Answer: -1 at position #3 # < # Num possible variants: 1 # Answer: 1 at position #4 # > # Num possible variants: 1 # Answer: -1 at position #2 # > # Num possible variants: 8 # ([0, 1, 4], [2, 3, 5], 3) # = # Num possible variants: 2 # ([0], [6], 1) # = # Num possible variants: 1 # Answer: -1 at position #7 # < # Num possible variants: 0 # This cannot happen # > # Num possible variants: 1 # Answer: -1 at position #6 # < # Num possible variants: 3 # ([0, 1], [2, 4], 1) # = # Num possible variants: 1 # Answer: 1 at position #3 # < # Num possible variants: 1 # Answer: 1 at position #2 # > # Num possible variants: 1 # Answer: -1 at position #4 # > # Num possible variants: 3 # ([0, 5], [2, 3], 1) # = # Num possible variants: 1 # Answer: 1 at position #1 # < # Num possible variants: 1 # Answer: -1 at position #5 # > # Num possible variants: 1 # Answer: 1 at position #0
(Syntax highligher used: http://tohtml.com/python/)
Комментарии к решению
Третье число во взвешивании означает "хорошесть", выражающуюся в максимальном количество вариантов, оставшихся после отсечения, по всем трём исходам. Нужно использовать шрифт фиксированной ширины (напр courier new)
Несколько идей:
1. Наверняка существует уйма решений, подобных или изоморфных этому, просто с какой-то симметричной нумерацией. (Нумерация монеток помогает автоматическому перебору, но, вполне возможно, не является оптимальным подоходом, чтобы решать задачу в уме).
2. Можно "откладывать" монетки. Напр., разобъём на 3 кучки по 4, взвесим первые две, если левая меньше правой, то третью кучу уже сразу можно "отложить" как эталонные монеты, гарантированно не фальшивые, и они могут *пригодиться* в будущем.
В решении, сгенерированном моей программкой, конкретно эти монетки не пригождаются, но пригождаются отложенные после второго взвешивания на третьем, именно в качестве эталона:
напр., если [0, 1, 2, 3] < [4, 5, 6, 7], следующее взвешивание будет [0, 1, 4] (две монетки слева и одну справа) и [2, 3, 5] (другие две слева и ещё одну справа). Если эти две группы оказались равны, это сразу гарантирует, что все монеты между собой не фальшивы, т.е. не фальшивы [0, 1, 2, 3, 4, 5] (ну и также отложенные ранее [8, 9, 10, 11]). Остались только [6, 7]. Но! Программа не предлагает их взвешивать между собой (хотя так тоже можно было), она предлагает взвесить [6] с эталоном [0]. Это сразу даёт ответы на все вопросы, т.к. если [6] == [0], [7] автоматически будет не только фальшивой монеткой, а ещё и, известно что, более тяжёлой (из-за первого взвешивания).
Основной принип, по которому я строил алгоритм, это выбирать "наилучшие" взвешивания, где "хорошесть" определяется тем, настолько много вариантов отсекаются. Скажем, вначале вариантов у нас 24 (фальшивая монетка может быть на любой позиции, от 0 до 11, причём она может быть тяжелее или легче других - т.е. по 2 варианта на позицию).
Если мы взвесим [0, 1, 2, 3] и [4, 5, 6, 7], у нас есть три исхода:
1) когда равны, фальшивая монетка в [8, 9, 10, 11], но не известно, она легче или тяжелее, т.е. осталось 8 вариантов.
2) когда слева легче, есть два под-варианта: либо фальшивая монетка слева (одна из 4), и известно, что она легче, либо фальшивая монетка справа (тоже одна из 4), но известно, что она тяжелее. Суммарное количество варианто будет тоже 8 (4+4).
3) аналогично, когда слева тяжелее.
Итого, у нас во всех случаях остаётся по 8 вариантов, т.е. даже в самом худшем случае число вариантов сократится с 24 до 8. Уменьшение вариантов в 3 раза это наилучший исход для взвешивания, мы используем максимум информации (т.к. взвешивание имеет 3 исхода, т.е. даёт ровно точь в точь необходимую информацию, чтобы уменьшить число вариантов втрое).
Если же мы взвесим первым взвешиванием, например, [0] и [1], то когда они неравны, останется по 2 варианта, а когда они равны, останется 20 (10*2). Получается, худший случай это уменьшение с 24 до 20, что есть довольно таки расточительно. Кстати, как только после первого взвешивания получилось больше 9 вариантов, уже можно доказать, что двумя взвешиваниями не обойтись*, чтобы завершить (два взвешивания дают 9 вариантов исхода, 3*3, и это информация, которой хватит, чтобы выбрать 1 из 9. В случае более, чем 9 вариантов, будут по крайней мере два, которых информация, полученная после двух взвешиваний, не сможет отличить - понадобится третье взвешивание).
Аналогичные размышления: после двух взвешиваний должно оставаться не более 3 вариантов, иначе одного взвешивания не хватит, чтобы завершить. Это размышление может помочь отбросить неэффективные взвешивания на этапе перебора.
Понятно, что мой алгоритм не идеален, т.к. я на каждом шаге выбираю строго "локальный максимум" (отсюда и название "жадный алгоритм"), а не перебираю разные возможности, но в данном случае, так уж повезло, что жадный алгоритм дал оптимальное решение. Так частенько бывает. "Вручную" надо всегда пробовать сначала жадным алгоритмом, а потом уже пробовать перебирать "умнее", если жадным не получается.
Дополнение к (*):
Это правда, только если мы исходим из того, что изначальных вариантов 24, т.е. нам важно, фальшивая монетка легче или тяжелее.
На самом деле нам не важно, и *может быть* найдётся ещё более хорошее решение, в котором на листьях дерева перебора остаются группы по 2 варианта, в которых позиция фальшивой монетки идентифицирована одинаково, просто не известно, легче она или тяжелее (оба варианта есть).
С другой стороны, если бы мы ограничились 12 вариантами и не различали бы, что легче и что тяжелее, мы не могли бы так резво отбрасывать варианты, и не смогли бы сконструировать решение, исходя из вот этой идеи с отсечением вариантов.
С этой точки зрения, приём, который применён, это спецификация: добавить в задачу больше требований, чтобы исходую задачу проще было решить. В данном случае добавлено требование понять, фальшивая монетка легче или тяжелее.