ЕГЭ 16. Рекрсия

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

Рассмотрим      функцию F(n) заданную следующими соотношениями:

F(n) = 1 при n ≤ 1;

F(n) = n · F(n – 1)  при чётных n > 1;

F(n) = n + F(n – 2)  при нечётных n > 1;

Определите значение F(84).

 

1 способ

Рис. 1

Используя прогрессию с шагом 2, заполним столбец  А  четными числами от -2 до 84.

Аналогично, заполним столбец   В – не четными числами от -1 до 83.

Рис. 2

Рис.3

Для   n<=1   поставим значения  F(n)=1, а для   F(2)  и  F(3) введем формулы согласно правилам работы с электронными таблицами, и скопируем их на весь диапазон.

Рис.4

В режиме отображения значений видим ответ: F(84)= 148176.

Рис.5

ВНИМАНИЕ!

На время карантина все задания будут выставляться здесь!
Смотрите вкладку своего класса и отправляете задания строго до указанного срока!

В теме письма указывать ФИ, класс.

Программы для машины Тьюринга

Задача 1. Уменьшить двоичное число на 1.

Задача 2. Увеличить на единицу число, записанное в десятичной системе счисления.

Задача 3. Уменьшить на единицу число, записанное в десятичной системе счисления.

Задача 4. Сложить два числа в двоичной системе, разделенные на ленте знаком «+».

Задача 5. Сложить два числа в десятичной системе, разделенные на ленте знаком «+».

Источник:  http://kpolyakov.spb.ru/

Машина Тьюринга: http://kpolyakov.spb.ru/prog/turing.htm

Подготовка к к/р

№1  

Два игрока, Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.   

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.   

КУ РАК АРА КУКУ ЛОООМ ОКОРОК КАРАТ МЕМО КЕТЕКЕ НАНАЦА ПРОРОК

МОЛОКО РАПИРА АНКАРА АРАРАТ  

Задание 2. Укажите все слова из представленных, начиная с которых Ваня не может гарантированно выиграть своим первым ходом, но может выиграть либо своим первым или вторым ходом, в зависимости от хода Пети. Для всех выбранных слов укажите его выигрышную стратегию.   

Задание 3. Дана фраза: ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

№2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

а) добавить в любую кучу один камень;
б) увеличить количество камней в любой куче в два раза.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 63. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 63 камня или больше. В начальный момент в первой куче было 5 камней, а во второй – S камней, 1 ≤ S ≤ 57.

Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.

б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Задание 2. Укажите такое значение S, при котором у Пети есть выигрышная стратегия,

причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.

.

Д/з от 11.10.19   для 11А класса 

§7 + задачи

1)     Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

2)       Два игрока играют в следующую игру. Перед ними лежат две кучки фишек, в первой из которых 3, а во второй – 5 фишек. У каждого игрока неограниченно много фишек. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число фишек в 2 раза, или добавляет в какую-то кучку 2 фишки. Выигрывает тот игрок, после хода которого общее число фишек в двух кучках становится не менее 21. Кто выиграет – игрок, делающий ход первым, или игрок, делающий второй ход? Ответ обоснуйте. 

Урок 11. Команды ветвления (продолжение).

Урок 11

Урок 10: Команды ветвления.

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

Урок 10