Условие: Номер 21

Задача 20. Игровой автомат состоит из нескольких изогнутых трубок, по форме похожих на перевернутую вверх ногами букву "Y" . Сверху у трубы находится входное отверстие, а два выходных отверстия - снизу. Труба может находиться в одном из двух возможных состояний: Шарики кладутся вовнутрь один за другим через входное отверстие. В состоянии 1 (Рис. 3), шарик покидает трубу через незаблокированный правый выход, при этом Состояние 1 автоматически изменяется на Состояние 0 ( Рис.4, правый вход заблокирован, левый -- нет ). В состоянии 0 все происходит наоборот. Пусть игральный автомат состоит из 8 "Y"-образных трубок, их взаимное расположение показано на Рис.5. Вы можете забрасывать шарики через Вход A, Вход B, или Вход C. Пусть, например, первый шарик опускается через Вход A. Он покидает трубу G1 через левый выход, изменяя ее состояние с 0 на 1, поступает в G6 и покидает автомат через левый выход G6 ( изменяя состояние G6 c 0 на 1). Эту процедуру мы запишем следующим образом: A Затем мы забросим шарик через Вход A (он находится в Состоянии 1). Шаpик покидает G1 чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G4, покидает G4 чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G7, покидает автомат чеpез левый выход (изменяя G7 из состояния 0 в состояние 1 ).Все вышеизложенные действия мы запишем в виде: AA Если мы опустим третий шарик через Вход B, четвертый - через Вход C, то все действия запишутся следующим образом: AABC Необходимо: 1. Ввести с клавиатуры последовательность из 8 двоичных цифр (бит), показывающих соответственно начальное состояние G1-G8: бит 7 6 5 4 3 2 1 0 Вход G8 G7 G6 G5 G4 G3 G2 G1 Например, последовательность 11001010 означает, что G8, G7, G4 и G2 находятся в Состоянии 1 ( левый вход заблокирован ), тогда как G6, G5, G3 и G1 находятся в Состоянии 0 (правый вход заблокирован). 2. Ввести с клавиатуры вторую последовательность из 8 бит, показывающих конечные состояния G'1-G'8. 3. Напечатать последовательность ходов A, B, или C, указывающую, каким образом можно получить конечную позицию, забрасывая шарики через Входы A, B и C.

  Решение задачи: Номер 21

Решение задачи 20. Во всех узлах (трубках) схемы мы должны получить состояние Gi'. Первоначально установим G1, G2 и G3 в G1', G2' и G3', выбрасывая, по необходимости, шарики через входы A, B и С соответственно. Для того, чтобы G1,G2 и G3 оставались в состоянии G1', G2' и G3' необходимо, чтобы через каждый из входов забрасывалось лишь четное число шариков. Если проследить за шариками, заброшенными в игровой автомат, то мы можем заметить, что результат хода, например, ABC аналогичен результату хода BCA, т.е. от порядка заброски шариков ничего не зависит! Рассмотрим узлы,состояние которых может меняться при забрасывании шариков через вход A, т.к. при выбранной методике забрасывания только четного числа шариков через входы всегда G1=G1', то состояний G6 G4 G7 может быть лишь 23=8, от 000 до 111. Если мы будем забрасывать через A пары шариков, то при забросе серии максимум из 8 пар шариков какое-то состояние G6 G4 G7 должно обязательно повториться на протяжении серии, а далее состояния будут циклически повторяться, и случай с забрасыванием более 8 пар шариков сводится к случаю с количеством пар, не превосходящим 8. Аналогично, для забрасывания шариков через B мы получаем серию из не более чем 25=32 пар шариков, на протяжении которой будут установлены все возможные состояния G4 G5 G6 G7 G8, а для входа C серия, как и для A, будет иметь длину не более 8 пар. Перебирая все возможные комбинации A2x B2y C2z забрасывания шариков (тут A2x обозначает серию из 2X забрасываний шариков через вход A, 0<= x,y <=8, 0<=z<=32 ) получаем либо комбинацию-решение задачи, либо определяем отсутствие решения.

Назад