|
| Упражнение #4. |
|
Докажите правильность нашего предположения,
что M=2N-1, воспользовавшись
методом математической индукции. |
Завершая тяжелую работу "переносчиков дисков",
обратим еще раз внимание на постановку задачи: обойтись в ней без
стеков невозможно - разрушится вся конструкция условия; уменьшить
число стеков до двух нельзя, поскольку задача становится
неразрешимой; можно, конечно, увеличить их число, но это
"неинтересно", да и никак не опровергает тезис о полезности
многостековой обработки!
А теперь вновь увеличим число стеков - уже до 4-х.
И предложим вам карточную игру, правила которой явно демонстрируют
понимание, - хотя бы, интуитивное, - ее изобретателем (к сожалению,
безымянным) стековых механизмов.
Эта игра, а точнее, пасьянс на двоих, нам известна
под странным названием "Пьяница", которое объяснить затрудняемся.
Правила таковы:
-
перемешанная колода из N карт
(естественно, N кратно 4)
делится в процессе раздачи пополам между двумя игроками (A и B). После этого каждый из них
далее располагает двумя стопками карт: A1 и B1, содержащими по N div 2 карт,
уложенных картинками вниз, а также A2 и B2, пока пустыми;
-
при каждом очередном ходе игроки открывают на
игровом поле по одной верхней карте из своей первой стопки (pop (стек_)) и
-
тот игрок, карта которого "старше" (масть не
имеет значения, старшинство установлено по убыванию, согласно
последовательности "туз - король - дама - валет - десятка и
т.д." {"Ace - King - Queen - knave Jack - 10 etc."}
), забирает обе выложенные карты и кладет их, картинками
вниз, в свою вторую стопку - A2 или B2(push (стек_2)); будем считать, что сначала
кладется "убитая" карта, а сверху - своя;
-
если карты равнозначны, то оба снимают еще по
одной карте из своей первой стопки, укладывая их, картинкой вниз,
на выложенную ранее карту; затем открывают так же еще по одной
карте, но уже картинкой вверх - повторяется сравнение, и старшая
карта выигрывает; опять же, будем укладывать во вторую стопку
выигравшего сначала "битые" карты, потом - свои, не забывая
перевернуть их все картинками вверх;
-
если при очередном ходе игрока (предположим, A) стопка A1 закончилась (стек
пуст), то ее функции переходят ко второй стопке (A2®A1), и далее стопка A2 начинает формироваться заново;
-
игра заканчивается победой одного из игроков,
если у второго не осталось карт (оба его стека пусты), либо
ничьей, когда все N карт выложены на игровом поле
и пустыми оказываются сразу 4 стека (наш опыт
показывает, что эта ситуация крайне редка).
Если правила ясны, то вы, несомненно, получите
удовольствие, выполнив
| Упражнение #5. |
| a) |
Сыграйте несколько партий в описанную игру.
Обратите внимание, что отсутствие партнера, учитывая правила,
не является непреодолимым препятствием. |
| b) |
Установите, возможен ли вариант бесконечного
продолжения игры при неукоснительном соблюдении указанных
правил (естественно признавать в таком случае результат
ничейным). |
Назад
|
