Задачи С3 по информатике. Выигрышная стратегия

C 3 Два иг­ро­ка иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки кам­ней, в пер­вой из ко­то­рых 3, а во вто­рой — 6 кам­ней. У каж­до­го иг­ро­ка не­огра­ни­чен­но много кам­ней. Иг­ро­ки ходят по оче­ре­ди. Ход со­сто­ит в том, что игрок или удва­и­ва­ет число кам­ней в какой - то куче, или до­бав­ля­ет 2 камня в какую - то кучу. Вы­иг­ры­ва­ет игрок, после хода ко­то­ро­го общее число кам­ней в двух кучах ста­но­вит­ся не менее 24 кам­ней. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре обоих иг­ро­ков — игрок, де­ла­ю­щий пер­вый ход, или игрок, де­ла­ю­щий вто­рой ход? Каким дол­жен быть пер­вый ход вы­иг­ры­ва­ю­ще­го иг­ро­ка? Решение. Вы­иг­ры­ва­ет пер­вый игрок, своим пер­вым ходом он дол­жен до­ба­вить 2 камня в первую кучу. Для до­ка­за­тель­ства рас­смот­рим не­пол­ное де­ре­во игры, оформ­лен­ное в виде таб­ли­цы, где в каж­дой ячей­ке за­пи­са­ны пары чисел, раз­делённые за­пя­той. Эти числа со­от­вет­ству­ют ко­ли­че­ству кам­ней на каж­дом этапе игры, в пер­вой и вто­рой кучах со­от­вет­ствен­но.

Таб­ли­ца со­дер­жит все воз­мож­ные ва­ри­ан­ты ходов вто­ро­го иг­ро­ка. Из неё видно, что при любом от­ве­те вто­ро­го иг­ро­ка у пер­во­го име­ет­ся ход, при­во­дя­щий к по­бе­де.

C 3 Име­ют­ся две кучи кам­ней, в одной из ко­то­рых 1, а в дру­гой — 4 камня. Двум иг­ро­кам пред­ла­га­ет­ся игра по сле­ду­ю­щим пра­ви­лам. Каж­дый игрок обес­пе­чи­ва­ет­ся не­огра­ни­чен­ным за­па­сом кам­ней. Иг­ро­ки ходят по оче­ре­ди. Ход со­сто­ит в том, что игрок про­из­во­дит одно из воз­мож­ных дей­ствий: или утра­и­ва­ет число кам­ней в одной из куч, или уве­ли­чи­ва­ет на 3 ко­ли­че­ство кам­ней в какой - либо куче.

Вы­иг­ры­ва­ет тот игрок, после хода ко­то­ро­го, сум­мар­ное число кам­ней в двух кучах ста­но­вит­ся рав­ным 22 или более кам­ней. Кто вы­иг­ра­ет при без­оши­боч­ной игре обоих иг­ро­ков — игрок, де­ла­ю­щий пер­вый ход, или игрок, де­ла­ю­щий вто­рой ход? Как дол­жен хо­дить вы­иг­ры­ва­ю­щий игрок?

Решение.

Вы­иг­ры­ва­ет пер­вый игрок. У него есть два ва­ри­ан­та вы­иг­рыш­но­го пер­во­го хода: или до­ба­вить 3 камня в первую кучу, или утро­ить их ко­ли­че­ство.

Для до­ка­за­тель­ства рас­смот­рим не­пол­ное де­ре­во игры, оформ­лен­ное в виде таб­ли­цы, где в каж­дой ячей­ке за­пи­са­ны пары чисел, раз­делённые за­пя­той. Эти числа со­от­вет­ству­ют ко­ли­че­ству кам­ней на каж­дом этапе игры в пер­вой и вто­рой кучах со­от­вет­ствен­но.

Весьм атериал - смотрите документ.

Задания С3. Вы­иг­рыш­ная стратегия

C 3  Два иг­ро­ка иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки кам­ней, в пер­вой из ко­то­рых 3, а во вто­рой — 6 кам­ней. У каж­до­го иг­ро­ка не­огра­ни­чен­но много кам­ней. Иг­ро­ки ходят по оче­ре­ди. Ход со­сто­ит в том, что игрок или удва­и­ва­ет число кам­ней в какой-то куче, или до­бав­ля­ет 2 камня в какую-то кучу. Вы­иг­ры­ва­ет игрок, после хода ко­то­ро­го общее число кам­ней в двух кучах ста­но­вит­ся не менее 24 кам­ней. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре обоих иг­ро­ков — игрок, де­ла­ю­щий пер­вый ход, или игрок, де­ла­ю­щий вто­рой ход? Каким дол­жен быть пер­вый ход вы­иг­ры­ва­ю­ще­го иг­ро­ка? Решение.

C 3  Име­ют­ся две кучи кам­ней, в одной из ко­то­рых 1, а в дру­гой — 4 камня. Двум иг­ро­кам пред­ла­га­ет­ся игра по сле­ду­ю­щим пра­ви­лам. Каж­дый игрок обес­пе­чи­ва­ет­ся не­огра­ни­чен­ным за­па­сом кам­ней. Иг­ро­ки ходят по оче­ре­ди. Ход со­сто­ит в том, что игрок про­из­во­дит одно из воз­мож­ных дей­ствий: или утра­и­ва­ет число кам­ней в одной из куч, или уве­ли­чи­ва­ет на 3 ко­ли­че­ство кам­ней в какой-либо куче.

Вы­иг­ры­ва­ет тот игрок, после хода ко­то­ро­го, сум­мар­ное число кам­ней в двух кучах ста­но­вит­ся рав­ным 22 или более кам­ней. Кто вы­иг­ра­ет при без­оши­боч­ной игре обоих иг­ро­ков — игрок, де­ла­ю­щий пер­вый ход, или игрок, де­ла­ю­щий вто­рой ход? Как дол­жен хо­дить вы­иг­ры­ва­ю­щий игрок?

Решение.

Вы­иг­ры­ва­ет пер­вый игрок. У него есть два ва­ри­ан­та вы­иг­рыш­но­го пер­во­го хода: или до­ба­вить 3 камня в первую кучу, или утро­ить их ко­ли­че­ство.

Для до­ка­за­тель­ства рас­смот­рим не­пол­ное де­ре­во игры, оформ­лен­ное в виде таб­ли­цы, где в каж­дой ячей­ке за­пи­са­ны пары чисел, раз­делённые за­пя­той. Эти числа со­от­вет­ству­ют ко­ли­че­ству кам­ней на каж­дом этапе игры в пер­вой и вто­рой кучах со­от­вет­ствен­но

C 3. У ис­пол­ни­те­ля Каль­ку­ля­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1. при­бавь 2,

2. умножь на 5.

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 2, вто­рая — уве­ли­чи­ва­ет его в 5 раз.

Про­грам­ма для Каль­ку­ля­то­ра — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко есть про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 50?

Решение.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 5, не пре­вос­хо­дя­щее n. За­ме­тим, что нечётные числа мы никак по­лу­чить не можем. Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может превос­хо­дить (50 - 2) / 2 = 24.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 10, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем двоек.

2. Пусть n де­лит­ся на 5.

Тогда R(n) = R(n / 5) + R(n - 2)= R(n / 5) + R(n - 10) (если n 10).

При n = 10 R(n)) = 2 (два спо­со­ба: при­бав­ле­ни­ем четырёх двоек или од­но­крат­ным умно­же­ни­ем на 5).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных де­ся­ти и не пре­вос­хо­дя­щих 50: сна­ча­ла вы­чис­ля­ем R(2), затем R(10), R(20) и т. д.

Имеем:

R(2) = 1 = R(4) = R(6) = R(8),

R(10) = 2 = R(12) — R(18),

R(20) = R(4) + R(10) =1 + 2 = 3 = R(22) = R(28),

R(30) = R(6) + R(20) =1 + 3 = 4 = R(32) = R(38),

R(40) = R(8) + R(30) =1 + 4 = 5 = R(42) = R(48),

R(50) = R(10) + R(40) = 2 + 5 = 7.

Ответ: 7.

C 3  У ис­пол­ни­те­ля Каль­ку­ля­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1. при­бавь 2,

2. умножь на 3.

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 2, вто­рая — уве­ли­чи­ва­ет его в 3 раз.

Про­грам­ма для Утро­и­те­ля — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко есть про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число 25?

Решение.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n. За­ме­тим, что чет­ные числа мы никак по­лу­чить не можем.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить (25 - 1) / 2 = 12.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 3, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем двоек.

2. Пусть n де­лит­ся на 3.

Тогда R(n) = R(n / 3) + R(n - 2)= R(n / 3) + R(n - 6) (если n 6).

При n = 3 R(n)) = 2 (два спо­со­ба: при­бав­ле­ни­ем двоqкb или од­но­крат­ным умно­же­ни­ем на 3).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 25: сна­ча­ла вы­чис­ля­ем R(1), затем R(3), R(9) и т. д.

Имеем:

R(1)=1

R(3) = 2 = R(5) = R(7),

R(9) = R(3)+R(3)=2+2=4= R(11)=R(13),

R(15) = R(5) + R(9) =2 + 2 = 4 = R(17) = R(19),

R(21) = R(7) + R(15) =2 + 6 = 8= R(23) = R(25).

Ответ: 8.