Сообщение Re: Задачке 45+ лет. от 26.02.2020 17:42
Изменено 26.02.2020 18:36 Erop
Re: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:
NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
NM>Image: Libra2.jpg
Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.
Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.
Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)
При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.
Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.
Как раз генератор таких множеств мы и написали выше
Теперь надо формализовать саму задачу про взвешивания.
Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)
Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.
Итак.
Опишем нашу задачу на языке python 3.
Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.
Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.
Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!
Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?
NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
NM>Image: Libra2.jpg
Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.
Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.
| "для начала решим более простую задачу: напишем генератор таких пар подмножеств." | |||||||||||||||||||
| Начнём с того, что построим список пар размеров подмножеств. Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.
Напишем ещё несколько запчастей. Для того, что бы облегчить себе отсечения множеств, отличающихся только порядком элементов, потребуем, что бы наши элементы были 1) все разными 2) все упорядочены по < Генерировать будем так. Будем строить по одному наборы подмножеств одного размера. При этом запоминать будем не пары подмножеств, а тройки, так как нас интересуют ещё и те элементы, которые ещё можно добавлять. Кроме того, давайте договоримся, не ограничивая общности, что 1) Пустым может быть только правое множество 2) Самый маленький элемент всегда находится в левом множестве 4) Сами множества будем строить упорядоченными, что бы не получать дубликаты, отличающиеся только порядком элементов. То есть в терминах python'а это будут списки 5) Левое и правое подмножества не могут пересекаться. 6) В целях экономии памяти, третье подмножество (подмножество кандидатов) будем вычислять не каждый раз, а пореже, осуществляя доп. фильтрацию при расширении подмножества Итак, начнём с функции, которая из набора упорядочиваемых уникальных элементов строит набор троек упорядоченных подмножеств, таких, что в левом один элемент, правое пустое, и в остатке есть только элементы, превышающие элемент левого подмножества Потом пишем функцию, которая берёт на вход список троек и всеми допустимыми способами расширяет левое (первое) подмножество, элементами третьего И аналогичную функцию для расширения правого (второго) подмножества. Функция для правого чуть сложнее, так как из (1) следует, что левое пустым быть не может, а правое может (2) нам обеспечит изначальное построение соответствующих остатков (третьих множеств) (5), а так же сокращение перебора в самых массовых подмножествах с относительно коротким остатком, нам обеспечит фильтрация остатка для каждой исходной тройки
Ну и теперь можем писать сам генератор подмножеств. Предлагается генерировать подмножества группами, в каждой из которых их размеры одинаковые. При этом мы так написали _get_subsets_sizes, что обычно можем генерировать новую группу на основе уже сгенерированных, пополняя левое или правое подмножество. (мы всегда можем это сделать, так как все наборы с меньшей суммой размеров подмножеств мы генерируем до того, как наборы с большей) К сожалению, из этого правила есть исключение: это случай, когда max_diff == 0, так как в этом случае мы не можем увеличить сумму на 1. И нам придётся в этом случае "преодолевать пропасть в два прыжка"
Итого, нам осталось написать только сам перебор взвешиваний. Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали! | |||||||||||||||||||
Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)
При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.
Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.
Как раз генератор таких множеств мы и написали выше
Теперь надо формализовать саму задачу про взвешивания.
Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)
Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.
Итак.
Опишем нашу задачу на языке python 3.
COINS_COUNT = 12 # число монет
SCALE_RESULTS = "<=>" # возможные результаты взвешивания
ALL_COINS = set(range(1,COINS_COUNT+1)) # просто множество всех имеющихся у нас монет
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS} # а это множество возможных исходов.
MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1 # Это эвристика, на самом деле её, наверное можно доказать, но можно попробовать запустить с COINS_COUNT.Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.
Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.
Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
def _scale_all_states( left, right, states ) :
"""
разбить множество состояний на случаи < = >
"""
res = { "count":None, '<':[], '=':[], '>':[] }
for s in states :
if -s in left or s in right :
res['<'].append( s )
elif s in left or -s in right :
res['>'].append( s )
else :
res['='].append( s )
return res| "проверим, что получилось" | |
| |
Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!
def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
"""
Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
states -- множество возвожных исходов
max_count - максимальное число взвешиваний
coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
"""
if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]}
if len(states) > 3**max_count :
return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
coins_count = coins_count or len( unknown )
for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
scale_res = _scale_all_states( l, r, states )
#if max_count == 3 and len(l) == 4 and len(r) == 4:
# print( l, r, scale_res )
max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
if max_state_len > 3**(max_count-1) :
continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
scale_res["count"] = 1
return scale_res
#if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
# continue #Это только эвристика, но правдоподобная!
if max_count <= 1 :
continue # больше ничего сделать нельзя
# Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
scale_count = 0
for k in SCALE_RESULTS :
substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
if substrategy is None : # разделить не удалось!
scale_res = None
break
scale_res[k] = substrategy
scale_count = max(substrategy["count"], scale_count)
if scale_res : # Нашли решение для всех трёх результатов взвешивания!
scale_res["count"] = scale_count + 1
return scale_res
return None| "проверим, что получилось" | |
а за 2 секунды находит, что решения нет | |
Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?
| "полная версия кода" | |
| |
Re: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:
NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
NM>Image: Libra2.jpg
Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.
Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.
Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)
При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.
Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.
Как раз генератор таких множеств мы и написали выше
Теперь надо формализовать саму задачу про взвешивания.
Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)
Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.
Итак.
Опишем нашу задачу на языке python 3.
Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.
Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.
Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!
Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?
NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
NM>Image: Libra2.jpg
Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.
Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.
| "для начала решим более простую задачу: напишем генератор таких пар подмножеств." | |||||||||||||||||||
| Начнём с того, что построим список пар размеров подмножеств. Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.
Напишем ещё несколько запчастей. Для того, что бы облегчить себе отсечения множеств, отличающихся только порядком элементов, потребуем, что бы наши элементы были 1) все разными 2) все упорядочены по < Генерировать будем так. Будем строить по одному наборы подмножеств одного размера. При этом запоминать будем не пары подмножеств, а тройки, так как нас интересуют ещё и те элементы, которые ещё можно добавлять. Кроме того, давайте договоримся, не ограничивая общности, что 1) Пустым может быть только правое множество 2) Самый маленький элемент всегда находится в левом множестве 4) Сами множества будем строить упорядоченными, что бы не получать дубликаты, отличающиеся только порядком элементов. То есть в терминах python'а это будут списки 5) Левое и правое подмножества не могут пересекаться. 6) В целях экономии памяти, третье подмножество (подмножество кандидатов) будем вычислять не каждый раз, а пореже, осуществляя доп. фильтрацию при расширении подмножества Итак, начнём с функции, которая из набора упорядочиваемых уникальных элементов строит набор троек упорядоченных подмножеств, таких, что в левом один элемент, правое пустое, и в остатке есть только элементы, превышающие элемент левого подмножества Потом пишем функцию, которая берёт на вход список троек и всеми допустимыми способами расширяет левое (первое) подмножество, элементами третьего И аналогичную функцию для расширения правого (второго) подмножества. Функция для правого чуть сложнее, так как из (1) следует, что левое пустым быть не может, а правое может (2) нам обеспечит изначальное построение соответствующих остатков (третьих множеств) (5), а так же сокращение перебора в самых массовых подмножествах с относительно коротким остатком, нам обеспечит фильтрация остатка для каждой исходной тройки
Ну и теперь можем писать сам генератор подмножеств. Предлагается генерировать подмножества группами, в каждой из которых их размеры одинаковые. При этом мы так написали _get_subsets_sizes, что обычно можем генерировать новую группу на основе уже сгенерированных, пополняя левое или правое подмножество. (мы всегда можем это сделать, так как все наборы с меньшей суммой размеров подмножеств мы генерируем до того, как наборы с большей) К сожалению, из этого правила есть исключение: это случай, когда max_diff == 0, так как в этом случае мы не можем увеличить сумму на 1. И нам придётся в этом случае "преодолевать пропасть в два прыжка"
Итого, нам осталось написать только сам перебор взвешиваний. Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали! | |||||||||||||||||||
Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)
При этом понятно, что на каждом этапе у нас есть какой-то набор монет, про который мы уже знаем, что они не фальшивые, и какой-то набор, про которые ещё не ясно.
Соответственно, ясно, что любое осмысленное взвешивание -- это взвешивание какого-то количества монет, про которые мы пока не знаем, фальшивы ли они против какого-то количества монет из того же множества. При этом число монет на чашах, перед взвешиванием, надо уровнять монетами, которые уже точно нефальшивые.
Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.
Как раз генератор таких множеств мы и написали выше
Теперь надо формализовать саму задачу про взвешивания.
Для удобства занумеруем монеты числами от 1 до числа монет, а возможные результаты поиска фальшивой монеты (какая монета фальшивая и легче она ли тяжелее) за отрицательные номера монет (значит эта фальшивая монета легче) и положительные (значит эта монета тяжелее)
Зачем это надо? Что бы не перебирать, по возможности, эквивалентные стратегии. Например не перебирать разные способы разложить уже установленные нефальшивые монеты.
Итак.
Опишем нашу задачу на языке python 3.
COINS_COUNT = 12 # число монет
SCALE_RESULTS = "<=>" # возможные результаты взвешивания
ALL_COINS = set(range(1,COINS_COUNT+1)) # просто множество всех имеющихся у нас монет
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS} # а это множество возможных исходов.
MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1 # Это эвристика, на самом деле её, наверное можно доказать, но можно попробовать запустить с COINS_COUNT.Обсудим эвристику MAX_SPLIT_SIZE = COINS_COUNT // 3 + 1
На мой взгляд, её можно доказать (если решение существует с полным перебором, то существует и с таким ограничением), но строго доказывать мне лень.
Я пробовал запускать нерешаемые версии задачи (что бы перебирать всё до конца) с этой эвристикой и без неё. Без неё примерно в два раза дольше, так что если очень надо, можно просто отказаться.
Ещё есть эвристика, что если взвешивание не последнее (есть неразличимые состояния), а какой-то результат взвешивания получить нельзя, то эту ветку можно отсечь.
Я пробовал запускать нерешаемую задачу с ней и без неё -- эффект не более 10%. Так что её, для простоты, можно просто не использовать.
В окончательном варианте функции я её закомментировал.
Ну и осталась всего одна вспомогательная задача:
"Взвесить" какой-то набор возможных исходов (то есть применить его к какому-то множеству состояний
def _scale_all_states( left, right, states ) :
"""
разбить множество состояний на случаи < = >
"""
res = { "count":None, '<':[], '=':[], '>':[] }
for s in states :
if -s in left or s in right :
res['<'].append( s )
elif s in left or -s in right :
res['>'].append( s )
else :
res['='].append( s )
return res| "проверим, что получилось" | |
| |
Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!
def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
"""
Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
states -- множество возвожных исходов
max_count - максимальное число взвешиваний
coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
"""
if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]}
if len(states) > 3**max_count :
return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
coins_count = coins_count or len( unknown )
for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
scale_res = _scale_all_states( l, r, states )
#if max_count == 3 and len(l) == 4 and len(r) == 4:
# print( l, r, scale_res )
max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
if max_state_len > 3**(max_count-1) :
continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
scale_res["count"] = 1
return scale_res
#if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
# continue #Это только эвристика, но правдоподобная!
if max_count <= 1 :
continue # больше ничего сделать нельзя
# Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
scale_count = 0
for k in SCALE_RESULTS :
substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
if substrategy is None : # разделить не удалось!
scale_res = None
break
scale_res[k] = substrategy
scale_count = max(substrategy["count"], scale_count)
if scale_res : # Нашли решение для всех трёх результатов взвешивания!
scale_res["count"] = scale_count + 1
return scale_res
return None| "проверим, что получилось" | |
а за 2 секунды находит, что решения нет | |
Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?
| "полная версия кода" | |
| |