Re: Задачке 45+ лет.
От: Erop Россия  
Дата: 26.02.20 17:42
Оценка: 8 (2)
Здравствуйте, NovaMind, Вы писали:


NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

NM>Image: Libra2.jpg

Нашлось у меня два-три часика свободного времени у компа сына с питоном на ходу.
Так что попробуем решить грубой силой, а не всякими там рассуждениями на две недели
Ну, поехали.

Разберёмся с порядком перебора.
Нам надо уметь перебирать уникальные наборы монет вида "три монеты из множества против двух монет из того же множества). при этом их стоит перебирать в порядке возрастания суммарного числа элементов множеств, так как чем больше монет в деле, тем, больше шансов, что в этой группе больше наборов.

  "для начала решим более простую задачу: напишем генератор таких пар подмножеств."
Начнём с того, что построим список пар размеров подмножеств.
Можем заметить, что может можно написать и поумнее, но мне лень, тем более, что время работы этого генератора, очевидно, очень маленькое.

def _get_subsets_sizes( max_size, max_diff, max_sum ) :
    """
    Генерируем последовательность размеров пар подмножеств, таких, 
    что бы каждое следующее можно было получить из какого-то предыдущего
    И что бы сначала перебирать группы множеств с меньшей вариативностью. 
    """
    res = set() # будем строить множество, что бы не париться с повторами, хотя мы и строим каждую пару один раз
    for left_size in range(1, max_size+1) : # леове множество всегда не пустое и максимум max_size
        for right_size in range( max(0, left_size-max_diff), min(max_size, left_size+max_diff ) + 1 ) :
            to_add = left_size, right_size
            assert to_add not in res, f"Повторно сгенерировали пару {to_add}" #это для эстетов
            # Мы уже итерируем такие значения right_size, что 0 <= right_size <= max_size
            # И -max_diff <= right_size - max_size <= max_diff
            if sum(to_add) <= max_sum : # Но есть ещё условие на максимальную сумму размеров
                res.add( to_add ) 
    # множество построено, осталось отсортировать.
    return sorted( res, key=lambda x:(sum(x), max(x), x))


  "проверим, что получилось" 
print( f"{( 4, 0, 12 )}:", _get_subsets_sizes( 4, 0, 12 ) )
print( f"{( 4, 2, 12 )}:", _get_subsets_sizes( 4, 2, 12 ) )
print( f"{( 4, 4, 12 )}:", _get_subsets_sizes( 4, 4, 12 ) )
Печатает:
(4, 0, 12): [(1, 1), (2, 2), (3, 3), (4, 4)]
(4, 2, 12): [(1, 0), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 4), (4, 2), (3, 4), (4, 3), (4, 4)]
(4, 4, 12): [(1, 0), (1, 1), (2, 0), (1, 2), (2, 1), (3, 0), (2, 2), (1, 3), (3, 1), (4, 0), (2, 3), (3, 2), (1, 4), (4, 1), (3, 3), (2, 4), (4, 2), (3, 4), (4, 3), (4, 4)]


Напишем ещё несколько запчастей.
Для того, что бы облегчить себе отсечения множеств, отличающихся только порядком элементов, потребуем, что бы наши элементы были
1) все разными
2) все упорядочены по <
Генерировать будем так.
Будем строить по одному наборы подмножеств одного размера.
При этом запоминать будем не пары подмножеств, а тройки, так как нас интересуют ещё и те элементы, которые ещё можно добавлять.
Кроме того, давайте договоримся, не ограничивая общности, что
1) Пустым может быть только правое множество
2) Самый маленький элемент всегда находится в левом множестве
4) Сами множества будем строить упорядоченными, что бы не получать дубликаты, отличающиеся только порядком элементов. То есть в терминах python'а это будут списки
5) Левое и правое подмножества не могут пересекаться.
6) В целях экономии памяти, третье подмножество (подмножество кандидатов) будем вычислять не каждый раз, а пореже, осуществляя доп. фильтрацию при расширении подмножества

Итак, начнём с функции, которая из набора упорядочиваемых уникальных элементов строит набор троек упорядоченных подмножеств, таких, что в левом один элемент, правое пустое, и в остатке есть только элементы, превышающие элемент левого подмножества

Потом пишем функцию, которая берёт на вход список троек и всеми допустимыми способами расширяет левое (первое) подмножество, элементами третьего
И аналогичную функцию для расширения правого (второго) подмножества.
Функция для правого чуть сложнее, так как из (1) следует, что левое пустым быть не может, а правое может
(2) нам обеспечит изначальное построение соответствующих остатков (третьих множеств)
(5), а так же сокращение перебора в самых массовых подмножествах с относительно коротким остатком, нам обеспечит фильтрация остатка для каждой исходной тройки

def _build_start_1_0_trios( items ) :
    """
    Строим самое первое подмножество подмножеств, в котором в левом по одному, а правое пустое
    За одно вычисляем в каждом случае упорядоченный rest, все элементы в котором больше, 
    чем элемент в левом подмножестве
    """
    items = tuple( sorted( set(items) ) ) #делаем уникальный упорядоченный набор элемнтов
    return [(items[i:i+1], tuple(), items[i+1:]) for i in range(len(items))]

def _gen_add_item_to_left( trios ) :   
    """
    перечисляет результаты возможного расширения левых подмножества, за счёт остатков из той же тройки
    """
    for l, r, rest in trios : #для всех троек
        used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
        rest = [c for c in rest if c not in used]
        for c in rest :
            if c > l[-1] : #l пустым быть не может. Строим только упорядоченные подмножества
                yield l+(c,), r, rest

def _gen_add_item_to_right( trios ) :
    """
    перечисляет результаты возможного расширения правых подмножества, за счёт остатков из той же тройки
    """
    for l, r, rest in trios : #для всех троек
        if r : # правое подможество, в отличии от левого, может быть пустым!
            used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
            rest = [c for c in rest if c not in used]
            for c in rest :
                if c > r[-1] : # Строим только упорядоченные подмножества
                    yield l, r+(c,), rest
        else : # случай пустого правого подмножества -- некоторые отсечения нельзя выполнить.
            used = set( l ) # строим остаток, в котором нет элемнтов из l и r (но оно всё равно пустое)
            rest = [c for c in rest if c not in used]
            for c in rest :
                yield l, (c,), rest


  "проверим, что получилось" 
print( _build_start_1_0_trios( "мама мыла раму милым мылом".split(" ") ) )

print( list( _gen_add_item_to_left([
                                    ( (1,), tuple(), [2,4]),
                                    ( (1, 3), (2,), [2,4,5]),
                                    ( (1, 3), (2, 4), [2,4,5,7]),
                                   ]) ) )

print( list( _gen_add_item_to_right([
                                    ( (1,), tuple(), [2,4]),
                                    ( (1, 3), (2,), [2,4,5]),
                                    ( (1, 3), (2, 4), [2,4,5,7]),
                                   ]) ) )
Печатает:
[(('мама',), (), ('милым', 'мыла', 'мылом', 'раму')), (('милым',), (), ('мыла', 'мылом', 'раму')), (('мыла',), (), ('мылом', 'раму')), (('мылом',), (), ('раму',)), (('раму',), (), ())]
[((1, 2), (), [2, 4]), ((1, 4), (), [2, 4]), ((1, 3, 4), (2,), [4, 5]), ((1, 3, 5), (2,), [4, 5]), ((1, 3, 5), (2, 4), [5, 7]), ((1, 3, 7), (2, 4), [5, 7])]
[((1,), (2,), [2, 4]), ((1,), (4,), [2, 4]), ((1, 3), (2, 4), [4, 5]), ((1, 3), (2, 5), [4, 5]), ((1, 3), (2, 4, 5), [5, 7]), ((1, 3), (2, 4, 7), [5, 7])]


Ну и теперь можем писать сам генератор подмножеств.
Предлагается генерировать подмножества группами, в каждой из которых их размеры одинаковые.
При этом мы так написали _get_subsets_sizes, что обычно можем генерировать новую группу на основе уже сгенерированных, пополняя левое или правое подмножество.
(мы всегда можем это сделать, так как все наборы с меньшей суммой размеров подмножеств мы генерируем до того, как наборы с большей)
К сожалению, из этого правила есть исключение: это случай, когда max_diff == 0, так как в этом случае мы не можем увеличить сумму на 1. И нам придётся в этом случае "преодолевать пропасть в два прыжка" 

def gen_sorted_pairs( items, max_diff, max_size ) :
    """
    Генерирует множество пар упорядоченных подмножеств items
    """
    if max_size < 1 : # нечего генерировать
        return
    trios_1_0 = _build_start_1_0_trios(items)
    if max_diff < 1 : # особый случай, когда надо "преодолевать пропасть в два прыжка"
        cur_trios = list( _gen_add_item_to_right(trios_1_0) ) #построили тройки для множеств 1х1
        for t in cur_trios :
            yield (set(t[0]), set(t[1]))
        for i in range(2, max_size+1) :
            # Прыжок №1. Сортируем, что бы удобнее было ориентироваться
            tmp = _gen_add_item_to_left( sorted( cur_trios ) ) # в генерируемых множествах
            # Прыжок №2. Выдаём множества по одному, что бы у перебора была возможность отсечься
            cur_trios = [] # Но, если, нам потребуется и более поздняя группа, сохраняем выданное только что множество
            for t in _gen_add_item_to_right( tmp ):
                cur_trios.append( t )
                yield (set(t[0]), set(t[1]))
    else : # max_diff >= 1 -- можем позволить себе строить подмножества увеличивая их по одному!
        cache = { (1,0):trios_1_0 } # в этом словаре будем хранить наборы множеств, которые планируем расширять
        for size in _get_subsets_sizes(max_size, max_diff, len(items)) :
            left_size, right_size = size
            tmp = []
            if size in cache :
                for t in cache[size] :
                    yield (set(t[0]), set(t[1]))
            elif (left_size, right_size-1) in cache :
                for t in _gen_add_item_to_right( cache[(left_size, right_size-1)] ) :
                    yield (set(t[0]), set(t[1]))
                    tmp.append(t)
                tmp.sort()
                cache[size] = tmp
            elif (left_size-1, right_size) in cache :
                for t in _gen_add_item_to_left( cache[(left_size-1, right_size)] ) :
                    yield (set(t[0]), set(t[1]))
                    tmp.append(t)
                tmp.sort()
                cache[size] = tmp
            else :
                assert False


  "проверим, что получилось" 
print( len( list(gen_sorted_pairs([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 0, 4)) ) ) # первое взвешивание
print( len( list(gen_sorted_pairs([1, 2, 3, 4, 5, 6, 7, 8], 4, 4)) ) ) # второе взвешивание
list( gen_sorted_pairs("папа мама я спортивная семья".split(" "), 5, 5 ) )
Печатает:
28116
2703
[({'мама'}, set()),
 ({'папа'}, set()),
 ({'семья'}, set()),
 ({'спортивная'}, set()),
 ({'я'}, set()),
 ({'мама'}, {'папа'}),
 ({'мама'}, {'семья'}),
 ({'мама'}, {'спортивная'}),
 ({'мама'}, {'я'}),
 ({'папа'}, {'семья'}),
 ({'папа'}, {'спортивная'}),
 ({'папа'}, {'я'}),
 ({'семья'}, {'спортивная'}),
 ({'семья'}, {'я'}),
 ({'спортивная'}, {'я'}),
 ({'мама', 'папа'}, set()),
 ({'мама', 'семья'}, set()),
 ({'мама', 'спортивная'}, set()),
 ({'мама', 'я'}, set()),
 ({'папа', 'семья'}, set()),
 ({'папа', 'спортивная'}, set()),
 ({'папа', 'я'}, set()),
 ({'семья', 'спортивная'}, set()),
 ({'семья', 'я'}, set()),
 ({'спортивная', 'я'}, set()),
 ({'мама'}, {'папа', 'семья'}),
 ({'мама'}, {'папа', 'спортивная'}),
 ({'мама'}, {'папа', 'я'}),
 ({'мама'}, {'семья', 'спортивная'}),
 ({'мама'}, {'семья', 'я'}),
 ({'мама'}, {'спортивная', 'я'}),
 ({'папа'}, {'семья', 'спортивная'}),
 ({'папа'}, {'семья', 'я'}),
 ({'папа'}, {'спортивная', 'я'}),
 ({'семья'}, {'спортивная', 'я'}),
 ({'мама', 'папа'}, {'семья'}),
 ({'мама', 'папа'}, {'спортивная'}),
 ({'мама', 'папа'}, {'я'}),
 ({'мама', 'семья'}, {'папа'}),
 ({'мама', 'семья'}, {'спортивная'}),
 ({'мама', 'семья'}, {'я'}),
 ({'мама', 'спортивная'}, {'папа'}),
 ({'мама', 'спортивная'}, {'семья'}),
 ({'мама', 'спортивная'}, {'я'}),
 ({'мама', 'я'}, {'папа'}),
 ({'мама', 'я'}, {'семья'}),
 ({'мама', 'я'}, {'спортивная'}),
 ({'папа', 'семья'}, {'спортивная'}),
 ({'папа', 'семья'}, {'я'}),
 ({'папа', 'спортивная'}, {'семья'}),
 ({'папа', 'спортивная'}, {'я'}),
 ({'папа', 'я'}, {'семья'}),
 ({'папа', 'я'}, {'спортивная'}),
 ({'семья', 'спортивная'}, {'я'}),
 ({'семья', 'я'}, {'спортивная'}),
 ({'мама', 'папа', 'семья'}, set()),
 ({'мама', 'папа', 'спортивная'}, set()),
 ({'мама', 'папа', 'я'}, set()),
 ({'мама', 'семья', 'спортивная'}, set()),
 ({'мама', 'семья', 'я'}, set()),
 ({'мама', 'спортивная', 'я'}, set()),
 ({'папа', 'семья', 'спортивная'}, set()),
 ({'папа', 'семья', 'я'}, set()),
 ({'папа', 'спортивная', 'я'}, set()),
 ({'семья', 'спортивная', 'я'}, set()),
 ({'мама', 'папа'}, {'семья', 'спортивная'}),
 ({'мама', 'папа'}, {'семья', 'я'}),
 ({'мама', 'папа'}, {'спортивная', 'я'}),
 ({'мама', 'семья'}, {'папа', 'спортивная'}),
 ({'мама', 'семья'}, {'папа', 'я'}),
 ({'мама', 'семья'}, {'спортивная', 'я'}),
 ({'мама', 'спортивная'}, {'папа', 'семья'}),
 ({'мама', 'спортивная'}, {'папа', 'я'}),
 ({'мама', 'спортивная'}, {'семья', 'я'}),
 ({'мама', 'я'}, {'папа', 'семья'}),
 ({'мама', 'я'}, {'папа', 'спортивная'}),
 ({'мама', 'я'}, {'семья', 'спортивная'}),
 ({'папа', 'семья'}, {'спортивная', 'я'}),
 ({'папа', 'спортивная'}, {'семья', 'я'}),
 ({'папа', 'я'}, {'семья', 'спортивная'}),
 ({'мама'}, {'папа', 'семья', 'спортивная'}),
 ({'мама'}, {'папа', 'семья', 'я'}),
 ({'мама'}, {'папа', 'спортивная', 'я'}),
 ({'мама'}, {'семья', 'спортивная', 'я'}),
 ({'папа'}, {'семья', 'спортивная', 'я'}),
 ({'мама', 'папа', 'семья'}, {'спортивная'}),
 ({'мама', 'папа', 'семья'}, {'я'}),
 ({'мама', 'папа', 'спортивная'}, {'семья'}),
 ({'мама', 'папа', 'спортивная'}, {'я'}),
 ({'мама', 'папа', 'я'}, {'семья'}),
 ({'мама', 'папа', 'я'}, {'спортивная'}),
 ({'мама', 'семья', 'спортивная'}, {'папа'}),
 ({'мама', 'семья', 'спортивная'}, {'я'}),
 ({'мама', 'семья', 'я'}, {'папа'}),
 ({'мама', 'семья', 'я'}, {'спортивная'}),
 ({'мама', 'спортивная', 'я'}, {'папа'}),
 ({'мама', 'спортивная', 'я'}, {'семья'}),
 ({'папа', 'семья', 'спортивная'}, {'я'}),
 ({'папа', 'семья', 'я'}, {'спортивная'}),
 ({'папа', 'спортивная', 'я'}, {'семья'}),
 ({'мама', 'папа', 'семья', 'спортивная'}, set()),
 ({'мама', 'папа', 'семья', 'я'}, set()),
 ({'мама', 'папа', 'спортивная', 'я'}, set()),
 ({'мама', 'семья', 'спортивная', 'я'}, set()),
 ({'папа', 'семья', 'спортивная', 'я'}, set()),
 ({'мама', 'папа'}, {'семья', 'спортивная', 'я'}),
 ({'мама', 'семья'}, {'папа', 'спортивная', 'я'}),
 ({'мама', 'спортивная'}, {'папа', 'семья', 'я'}),
 ({'мама', 'я'}, {'папа', 'семья', 'спортивная'}),
 ({'мама', 'папа', 'семья'}, {'спортивная', 'я'}),
 ({'мама', 'папа', 'спортивная'}, {'семья', 'я'}),
 ({'мама', 'папа', 'я'}, {'семья', 'спортивная'}),
 ({'мама', 'семья', 'спортивная'}, {'папа', 'я'}),
 ({'мама', 'семья', 'я'}, {'папа', 'спортивная'}),
 ({'мама', 'спортивная', 'я'}, {'папа', 'семья'}),
 ({'мама'}, {'папа', 'семья', 'спортивная', 'я'}),
 ({'мама', 'папа', 'семья', 'спортивная'}, {'я'}),
 ({'мама', 'папа', 'семья', 'я'}, {'спортивная'}),
 ({'мама', 'папа', 'спортивная', 'я'}, {'семья'}),
 ({'мама', 'семья', 'спортивная', 'я'}, {'папа'}),
 ({'мама', 'папа', 'семья', 'спортивная', 'я'}, set())]


Итого, нам осталось написать только сам перебор взвешиваний.
Самую муторнуя часть -- генератор варинтов расположения монет на чашках весов, мы уже написали!


Нам надо перебирать разные стратегии взвешивания, и искать такую, в результате которой у нас в каждом листе дерева будет один исход (такая-то монета фальшивая и мы знаем тяжелее она или легче)

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

Итого, любое взвешивание -- это два набора монет (левая и правая чашка), про которые мы пока не знаем, фальшивые ли они. При этом число монет в наборах, может отличаться не больше, чем на количество уже установленных нефальшивых.

Как раз генератор таких множеств мы и написали выше

Теперь надо формализовать саму задачу про взвешивания.

Для удобства занумеруем монеты числами от 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


  "проверим, что получилось" 
_scale_all_states( {1, 2, 3, 4}, {5, 6, 7, 8}, ALL_STATES )
Печатает:
{'count': None,
 'vs': ({1, 2, 3, 4}, {5, 6, 7, 8}),
 '<': [5, 6, 7, 8, -1, -4, -3, -2],
 '=': [9, 10, 11, 12, 13, -13, -12, -11, -9, -10],
 '>': [1, 2, 3, 4, -8, -7, -6, -5]}


Ну, что же, осталось только научиться заменять подмножества состояний на следующее взвешивание, добавить перебор множеств в порядке, который мы научились генерировать выше, отсечения и подсчёт максимального числа взвешиваний на каждом из путей.
Мы почти решили задачку!

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


  "проверим, что получилось" 
get_scale_strategy( ALL_STATES, 3 )
Печатает (174ms):
{'count': 3,
 'vs': ({1, 2, 3, 7}, {4, 5, 6, 8}),
 '<': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({1}, {2}), '<': [-1], '=': [4], '>': [-2]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [6], '=': [8], '>': [5]},
  '>': {'count': 1, 'vs': ({3}, set()), '<': [-3], '=': [-7], '>': []}},
 '=': {'count': 2,
  'vs': ({9}, {10, 11}),
  '<': {'count': 1, 'vs': ({10}, {11}), '<': [11], '=': [-9], '>': [10]},
  '=': {'count': 1, 'vs': ({12}, set()), '<': [-12], '=': [], '>': [12]},
  '>': {'count': 1, 'vs': ({10}, {11}), '<': [-10], '=': [9], '>': [-11]}},
 '>': {'count': 2,
  'vs': ({1, 2}, {3, 4, 7}),
  '<': {'count': 1, 'vs': ({3}, set()), '<': [], '=': [7], '>': [3]},
  '=': {'count': 1, 'vs': ({5}, {6}), '<': [-5], '=': [-8], '>': [-6]},
  '>': {'count': 1, 'vs': ({1}, {2}), '<': [2], '=': [-4], '>': [1]}}}

а
COINS_COUNT = 13
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

get_strategy( ALL_STATES, 3 )

за 2 секунды находит, что решения нет


Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?

  "полная версия кода" 
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

def _get_subsets_sizes( max_size, max_diff, max_sum ) :
    """
    Генерируем последовательность размеров пар подмножеств, таких, 
    что бы каждое следующее можно было получить из какого-то предыдущего
    И что бы сначала перебирать группы множеств с меньшей вариативностью. 
    """
    res = set() # будем строить множество, что бы не париться с повторами, хотя мы и строим каждую пару один раз
    for left_size in range(1, max_size+1) : # леове множество всегда не пустое и максимум max_size
        for right_size in range( max(0, left_size-max_diff), min(max_size, left_size+max_diff ) + 1 ) :
            to_add = left_size, right_size
            assert to_add not in res, f"Повторно сгенерировали пару {to_add}" #это для эстетов
            # Мы уже итерируем такие значения right_size, что 0 <= right_size <= max_size
            # И -max_diff <= right_size - max_size <= max_diff
            if sum(to_add) <= max_sum : # Но есть ещё условие на максимальную сумму размеров
                res.add( to_add ) 
    # множество построено, осталось отсортировать.
    return sorted( res, key=lambda x:(sum(x), max(x), x))

def _build_start_1_0_trios( items ) :
    """
    Строим самое первое подмножество подмножеств, в котором в левом по одному, а правое пустое
    За одно вычисляем в каждом случае упорядоченный rest, все элементы в котором больше, 
    чем элемент в левом подмножестве
    """
    items = tuple( sorted( set(items) ) ) #делаем уникальный упорядоченный набор элемнтов
    return [(items[i:i+1], tuple(), items[i+1:]) for i in range(len(items))]

def _gen_add_item_to_left( trios ) :   
    """
    перечисляет результаты возможного расширения левых подмножества, за счёт остатков из той же тройки
    """
    for l, r, rest in trios : #для всех троек
        used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
        rest = [c for c in rest if c not in used]
        for c in rest :
            if c > l[-1] : #l пустым быть не может. Строим только упорядоченные подмножества
                yield l+(c,), r, rest

def _gen_add_item_to_right( trios ) :
    """
    перечисляет результаты возможного расширения правых подмножества, за счёт остатков из той же тройки
    """
    for l, r, rest in trios : #для всех троек
        if r : # правое подможество, в отличии от левого, может быть пустым!
            used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
            rest = [c for c in rest if c not in used]
            for c in rest :
                if c > r[-1] : # Строим только упорядоченные подмножества
                    yield l, r+(c,), rest
        else : # случай пустого правого подмножества -- некоторые отсечения нельзя выполнить.
            used = set( l ) # строим остаток, в котором нет элемнтов из l и r (но оно всё равно пустое)
            rest = [c for c in rest if c not in used]
            for c in rest :
                yield l, (c,), rest

def gen_sorted_pairs( items, max_diff, max_size ) :
    """
    Генерирует множество пар упорядоченных подмножеств items
    """
    if max_size < 1 : # нечего генерировать
        return
    trios_1_0 = _build_start_1_0_trios(items)
    if max_diff < 1 : # особый случай, когда надо "преодолевать пропасть в два прыжка"
        cur_trios = list( _gen_add_item_to_right(trios_1_0) ) #построили тройки для множеств 1х1
        for t in cur_trios :
            yield (set(t[0]), set(t[1]))
        for i in range(2, max_size+1) :
            # Прыжок №1. Сортируем, что бы удобнее было ориентироваться
            tmp = _gen_add_item_to_left( sorted( cur_trios ) ) # в генерируемых множествах
            # Прыжок №2. Выдаём множества по одному, что бы у перебора была возможность отсечься
            cur_trios = [] # Но, если, нам потребуется и более поздняя группа, сохраняем выданное только что множество
            for t in _gen_add_item_to_right( tmp ):
                cur_trios.append( t )
                yield (set(t[0]), set(t[1]))
    else : # max_diff >= 1 -- можем позволить себе строить подмножества увеличивая их по одному!
        cache = { (1,0):trios_1_0 } # в этом словаре будем хранить наборы множеств, которые планируем расширять
        for size in _get_subsets_sizes(max_size, max_diff, len(items)) :
            left_size, right_size = size
            tmp = []
            if size in cache :
                for t in cache[size] :
                    yield (set(t[0]), set(t[1]))
            elif (left_size, right_size-1) in cache :
                for t in _gen_add_item_to_right( cache[(left_size, right_size-1)] ) :
                    yield (set(t[0]), set(t[1]))
                    tmp.append(t)
                tmp.sort()
                cache[size] = tmp
            elif (left_size-1, right_size) in cache :
                for t in _gen_add_item_to_left( cache[(left_size-1, right_size)] ) :
                    yield (set(t[0]), set(t[1]))
                    tmp.append(t)
                tmp.sort()
                cache[size] = tmp
            else :
                assert False

def _scale_all_states( left, right, states ) :
    """
    разбить множество состояний на случаи < = >
    """
    res = { "count":None, "vs": (left, right), '<':[], '=':[], '>':[] }
    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

get_scale_strategy( ALL_STATES, 3 )
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Отредактировано 26.02.2020 18:36 Erop . Предыдущая версия . Еще …
Отредактировано 26.02.2020 18:30 Erop . Предыдущая версия .
Отредактировано 26.02.2020 18:22 Erop . Предыдущая версия .
Отредактировано 26.02.2020 18:20 Erop . Предыдущая версия .
Отредактировано 26.02.2020 18:20 Erop . Предыдущая версия .
Re[2]: Задачке 45+ лет.
От: Erop Россия  
Дата: 27.02.20 09:29
Оценка:
E>Здравствуйте, NovaMind, Вы писали:

NM>>Есть 12 монет.
NM>>Одна отличается по весу.
NM>>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

NM>>Image: Libra2.jpg


E>
  "полная версия кода" 
E>COINS_COUNT = 12
E>SCALE_RESULTS = "<=>" # возможные результаты взвешивания

E>ALL_COINS = set(range(1,COINS_COUNT+1))    
E>ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
E>MAX_SPLIT_SIZE = COINS_COUNT

E>def _get_subsets_sizes( max_size, max_diff, max_sum ) :
E>    """
E>    Генерируем последовательность размеров пар подмножеств, таких, 
E>    что бы каждое следующее можно было получить из какого-то предыдущего
E>    И что бы сначала перебирать группы множеств с меньшей вариативностью. 
E>    """
E>    res = set() # будем строить множество, что бы не париться с повторами, хотя мы и строим каждую пару один раз
E>    for left_size in range(1, max_size+1) : # леове множество всегда не пустое и максимум max_size
E>        for right_size in range( max(0, left_size-max_diff), min(max_size, left_size+max_diff ) + 1 ) :
E>            to_add = left_size, right_size
E>            assert to_add not in res, f"Повторно сгенерировали пару {to_add}" #это для эстетов
E>            # Мы уже итерируем такие значения right_size, что 0 <= right_size <= max_size
E>            # И -max_diff <= right_size - max_size <= max_diff
E>            if sum(to_add) <= max_sum : # Но есть ещё условие на максимальную сумму размеров
E>                res.add( to_add ) 
E>    # множество построено, осталось отсортировать.
E>    return sorted( res, key=lambda x:(sum(x), max(x), x))

E>def _build_start_1_0_trios( items ) :
E>    """
E>    Строим самое первое подмножество подмножеств, в котором в левом по одному, а правое пустое
E>    За одно вычисляем в каждом случае упорядоченный rest, все элементы в котором больше, 
E>    чем элемент в левом подмножестве
E>    """
E>    items = tuple( sorted( set(items) ) ) #делаем уникальный упорядоченный набор элемнтов
E>    return [(items[i:i+1], tuple(), items[i+1:]) for i in range(len(items))]

E>def _gen_add_item_to_left( trios ) :   
E>    """
E>    перечисляет результаты возможного расширения левых подмножества, за счёт остатков из той же тройки
E>    """
E>    for l, r, rest in trios : #для всех троек
E>        used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
E>        rest = [c for c in rest if c not in used]
E>        for c in rest :
E>            if c > l[-1] : #l пустым быть не может. Строим только упорядоченные подмножества
E>                yield l+(c,), r, rest

E>def _gen_add_item_to_right( trios ) :
E>    """
E>    перечисляет результаты возможного расширения правых подмножества, за счёт остатков из той же тройки
E>    """
E>    for l, r, rest in trios : #для всех троек
E>        if r : # правое подможество, в отличии от левого, может быть пустым!
E>            used = set( l ) | set( r ) # строим остаток, в котором нет элемнтов из l и r
E>            rest = [c for c in rest if c not in used]
E>            for c in rest :
E>                if c > r[-1] : # Строим только упорядоченные подмножества
E>                    yield l, r+(c,), rest
E>        else : # случай пустого правого подмножества -- некоторые отсечения нельзя выполнить.
E>            used = set( l ) # строим остаток, в котором нет элемнтов из l и r (но оно всё равно пустое)
E>            rest = [c for c in rest if c not in used]
E>            for c in rest :
E>                yield l, (c,), rest

E>def gen_sorted_pairs( items, max_diff, max_size ) :
E>    """
E>    Генерирует множество пар упорядоченных подмножеств items
E>    """
E>    if max_size < 1 : # нечего генерировать
E>        return
E>    trios_1_0 = _build_start_1_0_trios(items)
E>    if max_diff < 1 : # особый случай, когда надо "преодолевать пропасть в два прыжка"
E>        cur_trios = list( _gen_add_item_to_right(trios_1_0) ) #построили тройки для множеств 1х1
E>        for t in cur_trios :
E>            yield (set(t[0]), set(t[1]))
E>        for i in range(2, max_size+1) :
E>            # Прыжок №1. Сортируем, что бы удобнее было ориентироваться
E>            tmp = _gen_add_item_to_left( sorted( cur_trios ) ) # в генерируемых множествах
E>            # Прыжок №2. Выдаём множества по одному, что бы у перебора была возможность отсечься
E>            cur_trios = [] # Но, если, нам потребуется и более поздняя группа, сохраняем выданное только что множество
E>            for t in _gen_add_item_to_right( tmp ):
E>                cur_trios.append( t )
E>                yield (set(t[0]), set(t[1]))
E>    else : # max_diff >= 1 -- можем позволить себе строить подмножества увеличивая их по одному!
E>        cache = { (1,0):trios_1_0 } # в этом словаре будем хранить наборы множеств, которые планируем расширять
E>        for size in _get_subsets_sizes(max_size, max_diff, len(items)) :
E>            left_size, right_size = size
E>            tmp = []
E>            if size in cache :
E>                for t in cache[size] :
E>                    yield (set(t[0]), set(t[1]))
E>            elif (left_size, right_size-1) in cache :
E>                for t in _gen_add_item_to_right( cache[(left_size, right_size-1)] ) :
E>                    yield (set(t[0]), set(t[1]))
E>                    tmp.append(t)
E>                tmp.sort()
E>                cache[size] = tmp
E>            elif (left_size-1, right_size) in cache :
E>                for t in _gen_add_item_to_left( cache[(left_size-1, right_size)] ) :
E>                    yield (set(t[0]), set(t[1]))
E>                    tmp.append(t)
E>                tmp.sort()
E>                cache[size] = tmp
E>            else :
E>                assert False

E>def _scale_all_states( left, right, states ) :
E>    """
E>    разбить множество состояний на случаи < = >
E>    """
E>    res = { "count":None, "vs": (left, right), '<':[], '=':[], '>':[] }
E>    for s in states :
E>        if -s in left or s in right :
E>            res['<'].append( s )
E>        elif s in left or -s in right :
E>            res['>'].append( s )
E>        else :
E>            res['='].append( s )
E>    return res
    
E>def get_scale_strategy( states, max_count, coins_count=None, max_split_size=MAX_SPLIT_SIZE ) :
E>    """
E>    Возвращает стратегию взвешинвания на двухчашесных весах, или None, если стратегии нет
E>    позволяющую найти отличающуюся по весу единственную фальшивую монету в наборе
E>    states -- множество возвожных исходов
E>    max_count - максимальное число взвешиваний
E>    coins_count -- общее число монет. Еслидостоверно нефальшивых сначала нет, то определяется по states
E>    """
E>    if len(states) <= 1 : # нечего решать, возвращаем некий формальный результат
E>        return {"count":0, "vs":(set(),set()), "<":[], "=":list(states), ">":[]} 
    
E>    if len(states) > 3**max_count :
E>        return None #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
    
E>    unknown = {abs(c) for c in states} # множество монет, про которые пока не ясно, фальшивые ли они
E>    coins_count = coins_count or len( unknown )
E>    for l, r in gen_sorted_pairs(unknown, coins_count - len(unknown), max_split_size) :
E>        scale_res = _scale_all_states( l, r, states )
E>        #if max_count == 3 and len(l) == 4 and len(r) == 4:
E>        #    print( l, r, scale_res )
E>        max_state_len = max( len(scale_res[k]) for k in SCALE_RESULTS )
E>        if max_state_len > 3**(max_count-1) :
E>            continue #отсекаем, так как это множество состояний за оставшееся число взвешиваний не разделяется
E>        if max_state_len <= 1 : # Мы нашли решение за одно взвешивание!!!
E>            scale_res["count"] = 1
E>            return scale_res
E>        #if max( len(scale_res[k]) for k in SCALE_RESULTS ) == 0:
E>        #    continue #Это только эвристика, но правдоподобная!
E>        if max_count <= 1 :
E>            continue # больше ничего сделать нельзя
        
E>        # Итак, с отсечениями покончено, давайте запускать поиск стратегии рекурсивно!
E>        scale_count = 0
E>        for k in SCALE_RESULTS :
E>            substrategy = get_scale_strategy( scale_res[k], max_count-1, coins_count, max_split_size )
E>            if substrategy is None : # разделить не удалось!
E>                scale_res = None
E>                break
E>            scale_res[k] = substrategy
E>            scale_count = max(substrategy["count"], scale_count)
E>        if scale_res : # Нашли решение для всех трёх результатов взвешивания!
E>            scale_res["count"] = scale_count + 1
E>            return scale_res 
E>    return None

E>get_scale_strategy( ALL_STATES, 3 )
E>


E>Теперь можно пробовать решать разные двухчашечные задачи про уникальные монеты.
E>Например, проверить, а можно ли так же найти фальшивую среди 40 монет за 4 взвешивания?
На самом деле решения с 40 монетами за 4 взвешивания, очевидно, не существует. Ясно, что если после первого взвешивания будет равенство, то оставшиеся монеты будут играть в похожую игру — один ход, но + запас заведомо честных монет. Очевидно, что для 14 монет (28) исходов 3 взвешиваниями (27 исходов) она не решается, а для того, что бы получить меньшее число, надо первым ходом взвешивать 14х14. А это, опять по 28 исходов в случае неравенство.

Но легко проверить, например, что с первым ходом 8х8 это ещё решается, что даёт нам 16+12 = 28 фишек.
Кстати, если сделать запрос про второе взвешивание в духе
COINS_COUNT = 13
ALL_COINS = set(range(1,COINS_COUNT+1))    
ALL_STATES = ALL_COINS | {-s for s in ALL_COINS}
get_scale_strategy( ALL_STATES, 3, COINS_COUNT+16, 5 )

может быть окажется, что можно с 16+13 решить 13 -- это же всего 26 состояний, 27 исходов хватит. Вот 14 уже точно никак разрешить не получится.
То есть не выясненным остаётся только вопрос про 13 монет.
К сожалению комп сына сейчас далеко, так что придётся снова без бурт-форса прикинуть. Если первое взвешивание в задаче про 13 + дополнительные заведомо верные монеты будет 4х4, то в случае равенства останется 10 состояний на 9 возможных исходов.
И при неравенстве при взвешивании 5х5 останется 10 состояний. Ergo -- 12 -- точная верхняя оценка для числа монет, про которые ничего не известно, кроме, быть может, дополнительного запаса верных...

То есть единственный потенциал увеличения -- это 16 первых превратить в 18 и т. п.
Но и тут хочется, например, если есть 18 монет, участвовавших в первом неравновесном взвешивании, разбить их на три группы так, что бы 6 осталось на месте, 6 переехали на другую чашку и 6 вообще во втором не участвовали. Тогда за третье взвешивание нам надо будет выбрать из 6 монет-состояний, что не кажется нереальным.
Так что хочется сказать, что на последнее взвешивание можно прийти максимум с 3 состояниями, на предпоследнее с 9, на третье с конца -- 26, то есть
13 * 2 + 12 = 38 монет

1. 13 х 13. Если равенство, получаем 12 монет и 3 взвешивания. Мы это умеем!
Значит надо рассмотреть случай неравенства. Пусть левая чашка (монеты 1-13) тяжелее правой (монеты 14-26) .

2. взвешиваем: 1-5, 14-17 vs 9-13, 18-21 (а 6-8 и 22-26 откладываем в сторону )
При этом монеты бьются на три группы:
> Те, кто остался на той же чашке: 1-5 и 18-21 (9 шт)
< Те, кто переехал на другую чашку: 9-13 и 14-17 (9 шт)
= Те, кого отложили в сторону: 6-8 и 22-26 (8 шт)
В случае равенства получаем повтор ситуации: делим на группы 3, 2, 3 и дальше всё очевидно
Пусть, во втором взвешивании получили результат "правая тяжелее"
значит монета в группе тех, кто переехал (9-17)
Делим её на 3 группы относительно первого взвешивания (можно и относительно второго)
9, 10, 15 vs 14, 11, 12 (13, 16, 17)
> 9, 10, 14
< 11, 12, 15
= 13, 16, 17
и т. д.

Итого, за 4 взвешивания можно разобраться с 26 + 12 = 38 монетой.
С 40 не получится даже с запасом....
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 09.03.20 05:48
Оценка:
Здравствуйте, Erop, Вы писали:

E>Так?
E>1. 1+2+3+4 == 5+6+7+8 => фальшивая среди 9, 10, 11 ,12
E>2. 9 +10 == 1+2 => фальшивая среди 11 и 12
Зачем 1 и 2 взвешивать, если известно, что они уже не фальшивые? Взвешиваются те, что неизвестны. Известная примешивается из стопки, которая ещё не полностью проверена. Стопка 1,2,3,4 и 5,6,7,8 уже проверены на шаге 1.
Поэтому: 9 <=> 10
Если равно, то как раз и примешиваем 11: 9 <=> 11
Если нет, то примешиваем уже не фальшиваю из остатка, т.к. знаем, что фальшивых монет всегда одна:
К примеру: 9 < 10 -> 9 <=> 11, если весы 9 x 11 изменили баланс с < на >, соответственно, была фальшивой 9, т.к. 11 точно не фальшивая, если изменили с < на =, то фальшивая — 10.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[3]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 09.03.20 06:02
Оценка:
Здравствуйте, Erop, Вы писали:

E>По моему тоже, но ты первый, кто тут смог сформулировать решение.
Моё решение тебе чем не подошло?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[4]: Задачке 45+ лет.
От: Erop Россия  
Дата: 10.03.20 07:32
Оценка:
Здравствуйте, Vain, Вы писали:

V>Здравствуйте, Erop, Вы писали:

E>>Так?
E>>1. 1+2+3+4 == 5+6+7+8 => фальшивая среди 9, 10, 11 ,12
E>>2. 9 +10 == 1+2 => фальшивая среди 11 и 12
V>Зачем 1 и 2 взвешивать, если известно, что они уже не фальшивые?
Чтобы проверить те, про которые уже известно, если они и фальшивые, то тяжелее, но не известно фальшивые ли они.
Например, если у нас есть 8 монет из которых одна фальшивая и известно, что она тяжелее, то как за два взвешивания найти фальшивую?

V>Если равно, то как раз и примешиваем 11: 9 <=> 11
Это же не даёт экономии шагов? И так и так 2 шага получится?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: Задачке 45+ лет.
От: Erop Россия  
Дата: 10.03.20 07:34
Оценка:
Здравствуйте, Vain, Вы писали:

V>Моё решение тебе чем не подошло?

Я уже не помню какое чьё, но мне так кажется, что твоё было то, которое для самого неудачного случая, позволяло установить фальшивую монету, но не позволяло узнать тяжелее она или легче...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[5]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 10.03.20 16:23
Оценка:
Здравствуйте, Erop, Вы писали:

E>>>Так?
E>>>1. 1+2+3+4 == 5+6+7+8 => фальшивая среди 9, 10, 11 ,12
E>>>2. 9 +10 == 1+2 => фальшивая среди 11 и 12
V>>Зачем 1 и 2 взвешивать, если известно, что они уже не фальшивые?
E>Чтобы проверить те, про которые уже известно, если они и фальшивые, то тяжелее, но не известно фальшивые ли они.
У тебя первым взвешиванием на весах равно, значит нету там фальшивой монеты.

E>Например, если у нас есть 8 монет из которых одна фальшивая и известно, что она тяжелее, то как за два взвешивания найти фальшивую?
Задача про 12 монет и 3 взвешивание, и решение для этой задачи.

V>>Если равно, то как раз и примешиваем 11: 9 <=> 11
E>Это же не даёт экономии шагов? И так и так 2 шага получится?
Вот тут исправил: http://rsdn.org/forum/education/7677064
Автор: Vain
Дата: 10.03.20
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Отредактировано 10.03.2020 17:02 Vain . Предыдущая версия .
Re[5]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 10.03.20 16:59
Оценка:
Здравствуйте, Erop, Вы писали:

V>>Моё решение тебе чем не подошло?
E>Я уже не помню какое чьё, но мне так кажется, что твоё было то, которое для самого неудачного случая, позволяло установить фальшивую монету, но не позволяло узнать тяжелее она или легче...
А, не проверил последний вариант, тогда тот же подход:
o  o  o  o
z1 z2 z3 z4

(A)
o  o  x  o  o
z1 z2    z3 x1

(B)
o  o  x  o  o
z1 z3    z4 x1

монета | (A) | (B) 
-------+-----+-----
z1 > < | > < | > <
z2 > < | > < |  = 
z3 > < | > < | < >
z4 > < |  =  | < >

По изменении разности на весах можно понять которая меньше/больше.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Отредактировано 10.03.2020 17:04 Vain . Предыдущая версия .
Re[6]: Задачке 45+ лет.
От: Erop Россия  
Дата: 11.03.20 06:49
Оценка:
Здравствуйте, Vain, Вы писали:

V>У тебя первым взвешиванием на весах равно, значит нету там фальшивой монеты.
Так до него мы же не знаем, что нету

E>>Например, если у нас есть 8 монет из которых одна фальшивая и известно, что она тяжелее, то как за два взвешивания найти фальшивую?
V>Задача про 12 монет и 3 взвешивание, и решение для этой задачи.
Это я половину мысли пропустил. Я хотел написать, что ситуация в этой задаче отличается от нашей. И в нашем случае взвешивать неизвестную против заведомо правильной может иметь смысл...

V>>>Если равно, то как раз и примешиваем 11: 9 <=> 11
E>>Это же не даёт экономии шагов? И так и так 2 шага получится?
V>Вот тут исправил: http://rsdn.org/forum/education/7677064
Автор: Vain
Дата: 10.03.20


Ну, если я верно понял, что имеется в виду, то да, так получится. Но ты там тоже сравниваешь с заведомо нефальшивыми монетами...
И у тебя табличка немного непонятная.

Я верно понял, что z1, z2, z3, z4 -- это 4 оставшиеся монеты после равенства в первом взвешивании, в x1 -- заведомо нефальшивая?

Мне, например, понятнее такая запись:

 (A) | (B) | монета 
-----+-----+--------
  <  |  <  | z1, <
  <  |  =  | z2, <
  <  |  >  | z3, >
  =  |  <  | z4, >
  =  |  =  | НЕВОЗМОЖНО
  =  |  >  | z4, <
  >  |  <  | z3, <
  >  |  =  | z2, >
  >  |  >  | z1, >


Но суть такая, что ответ и ты и я дали позже коллеги
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[7]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 11.03.20 09:46
Оценка:
Здравствуйте, Erop, Вы писали:

V>>У тебя первым взвешиванием на весах равно, значит нету там фальшивой монеты.
E>Так до него мы же не знаем, что нету

E>>>Например, если у нас есть 8 монет из которых одна фальшивая и известно, что она тяжелее, то как за два взвешивания найти фальшивую?
V>>Задача про 12 монет и 3 взвешивание, и решение для этой задачи.
E>Это я половину мысли пропустил. Я хотел написать, что ситуация в этой задаче отличается от нашей. И в нашем случае взвешивать неизвестную против заведомо правильной может иметь смысл...
У меня так и делается, ты невнимательно читал?

V>>>>Если равно, то как раз и примешиваем 11: 9 <=> 11
E>>>Это же не даёт экономии шагов? И так и так 2 шага получится?
V>>Вот тут исправил: http://rsdn.org/forum/education/7677064
Автор: Vain
Дата: 10.03.20

E>Ну, если я верно понял, что имеется в виду, то да, так получится. Но ты там тоже сравниваешь с заведомо нефальшивыми монетами...
Похоже на какой-то глюк (уже не в первый раз такое), делаешь изменения и они не отображаются. Только вот сейчас обновилось. Была правка тут: http://rsdn.org/forum/education/7642196
Автор: Vain
Дата: 24.01.20


E>И у тебя табличка немного непонятная.
У меня в каждой колонке по два значения

E>Но суть такая, что ответ и ты и я дали позже коллеги
Где?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Отредактировано 11.03.2020 9:50 Vain . Предыдущая версия .
Re[8]: Задачке 45+ лет.
От: Erop Россия  
Дата: 11.03.20 10:50
Оценка:
Здравствуйте, Vain, Вы писали:

V>У меня так и делается, ты невнимательно читал?
Мне кажется, что решений без таких взвешиваний вообще нет. Но ты писал (возможно и не ты, кстати ), что не имеет смысла взвешивать предположительно фальшивую против точно истинной. Мне этот тезис не понравился.

E>>Но суть такая, что ответ и ты и я дали позже коллеги
V>Где?
Ну ты вот там, где исправил. Я там, где написал, что не понимаю, о чём НИИ там неделю думал и т. д...


Это всё неинтересно. Интересно написать решалку задач такого типа для большего числа взвешиваний.
Например, про сколько монет можно определить какая фальшивая и тяжелее она или легче за 10 взвешиваний?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[9]: Задачке 45+ лет.
От: Vain Россия google.ru
Дата: 11.03.20 12:03
Оценка:
Здравствуйте, Erop, Вы писали:

V>>У меня так и делается, ты невнимательно читал?
E>Мне кажется, что решений без таких взвешиваний вообще нет. Но ты писал (возможно и не ты, кстати ), что не имеет смысла взвешивать предположительно фальшивую против точно истинной. Мне этот тезис не понравился.
Где?

E>>>Но суть такая, что ответ и ты и я дали позже коллеги
V>>Где?
E>Ну ты вот там, где исправил. Я там, где написал, что не понимаю, о чём НИИ там неделю думал и т. д...
Ещё выше написан принцип, по которому решается задача.

E>Это всё неинтересно. Интересно написать решалку задач такого типа для большего числа взвешиваний.
E>Например, про сколько монет можно определить какая фальшивая и тяжелее она или легче за 10 взвешиваний?
Ну если тебе нефиг делать, то можешь приступать.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[10]: Задачке 45+ лет.
От: Khimik  
Дата: 11.03.20 14:40
Оценка: +1
E>>Это всё неинтересно. Интересно написать решалку задач такого типа для большего числа взвешиваний.
E>>Например, про сколько монет можно определить какая фальшивая и тяжелее она или легче за 10 взвешиваний?
V>Ну если тебе нефиг делать, то можешь приступать.

За одно взвешивание получаем примерно полтора бита информации: либо левые весы тяжелее, либо правые, либо равенство — т.е. один из трёх вариантов.

3^10=59049

Это число надо поделить на два, поскольку есть дополнительный бит информации который надо определить — тяжелее или легче фальшивая монета:

59049/2=29524,5

Получается что ответ 29524 монеты. Правда тут наверняка реальное число меньше, поскольку не всегда можно равномерно разделить варианты. Из этого подхода получается что можно решить исходную задачу не только с 12, но и с 13 монетами, сомневаюсь что это возможно реально.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[11]: Задачке 45+ лет.
От: NovaMind  
Дата: 22.03.20 08:14
Оценка:
Здравствуйте, Khimik, Вы писали:


E>>>Это всё неинтересно. Интересно написать решалку задач такого типа для большего числа взвешиваний.
E>>>Например, про сколько монет можно определить какая фальшивая и тяжелее она или легче за 10 взвешиваний?
V>>Ну если тебе нефиг делать, то можешь приступать.

K>За одно взвешивание получаем примерно полтора бита информации: либо левые весы тяжелее, либо правые, либо равенство — т.е. один из трёх вариантов.

K>3^10=59049

K>Это число надо поделить на два, поскольку есть дополнительный бит информации который надо определить — тяжелее или легче фальшивая монета:

K>59049/2=29524,5

K>Получается что ответ 29524 монеты. Правда тут наверняка реальное число меньше, поскольку не всегда можно равномерно разделить варианты. Из этого подхода получается что можно решить исходную задачу не только с 12, но и с 13 монетами, сомневаюсь что это возможно реально.

С 13-ю монетами можно решить.

Откладываем одну... (13-ю)
Решаем для 12-ти...

Если всё равно — "неправильная" 13-я.

Только не известно — легче или тяжелее....
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.