Условия всех задач из категории C3

Проверяемые элементы содержания: умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию
 
 
 
 

Историческая справка и теоретические сведения

Алгоритм – последовательность действий, приводящая к решению поставленной задачи.

Фундаментальные свойства алгоритма:

  • дискретность – последовательность шагов выполнения;

  • детерминированность – алгоритм должен быть определенным;

  • понятность – алгоритм должен быть понятен исполнителю (как правило, исполнителем выступает компилятор или интерпретатор);

  • завершаемость – алгоритм должен завершиться за разумное время;

  • массовость – алгоритм должен корректно работать при различных входных данных;

  • результативность – алгоритм должен финализироваться конкретным результатом.

 

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

Дедуктивный метод – метод мышления, при котором частное выводится из общих положений, используя логические переходы.

Пример дедуктивного умозаключения:

  1. все языки программирования сложны в изучении;

  2. Turbo Pascal – современный язык программирования

Следовательно, язык программирования Turbo Pascal сложен в изучении.

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

Пример индуктивного умозаключения:

  1. Петров Иван научился программировать на Turbo Pascal;

  2. Иванова Татьяна научилась программировать на Turbo Pascal;

Следовательно, любого человека можно научить программировать на Turbo Pascal.

 

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

 

Методические указания

Для успешного решения задач из данной категории вы должны:

  1. внимательно прочитать условие задачи и, понять, какие операции допустимы для игроков;

  2. рассмотреть доказательство через построение дерева игры;

  3. сделать корректные умозаключения.

 

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

*примечание: мое субъективное мнение - очень немного существует людей, обладающих "развитой" смекалкой и нестандартным мышлением. Иногда, данные навыки развиваются при решении олимпиадных задач и задач повышенного уровня сложности (как видите, именно на олимпиадах даются задачи на смекалку и нестандартное мышление, неспроста это!).

 
 
 
 

Задача №1

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

 

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

 
 
 
 
 
 

Задача №2

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

Выигрывает тот игрок, после хода которого суммарное число камней в двух кучах становится равным 22 или  более камней.

 

Вопрос:
кто выиграет при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

 
 
 
 
 
 

Задача №3

Дано:
два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй - 3 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает или в 2, или в 3 раза число камней в какой-то куче.

Выигрывает игрок, после хода которого в одной их куч становится не менее 20 камней.

 

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

 
 
 
 
 
 

Задача №4

Дано:
два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 6, а во второй – 5 камней. У каждого игрока неограниченное количество камней.
Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает в 2, или в три раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 48.

 

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

 
 
 
 
 
 
© 2011-2024 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?