Самостоятельная работа по теме:"Графы и деревья", 11 класс

Самостоятельная работа «Графы и деревья»

Вариант 1

1. Сколько четырёхзначных чисел можно записать с помощью цифр 0, 1, 2 и 3 при условии, что в записи числа не должно быть одинаковых цифр? Выпишите все такие числа. Для решения задачи постройте и проанализируйте дерево.

2. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, D. На втором – любая согласная, если первая буква гласная, и любая гласная, если первая согласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом и втором месте. Сколько цепочек можно создать по этому правилу? Для решения задачи постройте и проанализируйте дерево.

3. У исполнителя Вычислитель есть две команды, которым присвоены номера:

1 – прибавь 2,

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

Первая из них увеличивает текущее число на 2, вторая – умножает его на 3. Например, программа 112 преобразует исходное число 1 в число 15: 1+2=3, 3+2=5, 5×3=15.

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

1. У исполнителя Вычислитель есть 2 команды, которым присвоены номера:

1 – прибавить 4,

2 – вычесть 3.

Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из четырёх команд?

1. У исполнителя Вычислитель есть 2 команды, которым присвоены номера:

1 – прибавить 1,

2 – умножить на 2.

Сколько существует различных программ, позволяющих преобразовать число 1 в число 10?

Для решения задачи постройте и проанализируйте дерево.

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

Самостоятельная работа «Графы и деревья»

Вариант 2

1. Сколько трёхзначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4 при условии, что в записи числа должны быть две одинаковые цифры? Выпишите все такие числа. Для решения задачи постройте и проанализируйте дерево.

2. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

Для решения задачи постройте и проанализируйте дерево.

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

1 – прибавь 1,

2 – умножь на 4.

Первая из них увеличивает текущее число на 1, вторая – умножает его на 4. Например, программа 122 преобразует исходное число 1 в число 32: 1+1=2, 2×4=8, 8×4=32.

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

1. У исполнителя Вычислитель есть 2 команды, которым присвоены номера:

1 – прибавить 4,

2 – вычесть 3.

Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из пяти команд?

1. Исполнитель Калькулятор преобразует целое число, записанное на экране. У исполнителя 2 команды, каждой команде присвоен номер:

1 – прибавить 1,

2 – умножить на 2.

Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза.Сколько существует программ, которые число 3 преобразуют в число 20 и в которых предпоследняя команда 1?

Для решения задачи постройте и проанализируйте дерево.

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

Самостоятельная работа «Графы и деревья»

Вариант 3

1. Сколько чётных трёхзначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4 при условии, что в записи числа не должно быть одинаковых цифр? Выпишите все такие числа. Для решения задачи постройте и проанализируйте дерево.

2. Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

а) на первом месте стоит одна из букв: А, Е, И,

б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,

в) последней буквой не может быть А.

Сколько цепочек можно создать по этому правилу?

Для решения задачи постройте и проанализируйте дерево.

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

1 – прибавь 1,

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

Первая из них увеличивает текущее число на 1, вторая – умножает его на 3. Например, программа 221111 преобразует исходное число 1 в число 32: 5×3=15, 15×3=45, 45+1=46, 46+1=47, 47+1=48, 48+1=49.

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

1. У исполнителя Вычислитель есть 2 команды, которым присвоены номера:

1 – прибавить 3,

2 – вычесть 4.

Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из пяти команд?

1. Исполнитель Калькулятор две команды, которым присвоены номера:

1 – прибавить 1,

2 – увеличь число десятков на 1.

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, то она не изменяется. Сколько существует программ, которые число 11 преобразуют в число 27?

Для решения задачи постройте и проанализируйте дерево.

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

Самостоятельная работа «Графы и деревья»

Вариант 4

1. Сколько нечётных трёхзначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4 при условии, что в записи числа не должно быть одинаковых цифр? Выпишите все такие числа. Для решения задачи постройте и проанализируйте дерево.

2. Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

а) на первом месте стоит одна из букв: А, Е, И,

б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,

в) последней буквой не может быть А.

Сколько цепочек можно создать по этому правилу?

Для решения задачи постройте и проанализируйте дерево.

1. У исполнителя Утроитель есть две команды, которым присвоены номера:

1 – прибавь 1,

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

Первая из них увеличивает текущее число на 1, а вторая утраивает его. Например, программа 12211 преобразует исходное число 1 в число 20: 1+1=2, 2×3=6, 6×3=18, 18+1=19, 19+1=20.

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

1. У исполнителя Вычислитель есть 2 команды, которым присвоены номера:

1 – прибавить 3,

2 – вычесть 4.

Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из пяти команд?

1. Исполнитель Калькулятор две команды, которым присвоены номера:

1 – прибавить 1,

2 – увеличь число десятков на 1.

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, то она не изменяется. Сколько существует программ, которые число 11 преобразуют в число 27?

Для решения задачи постройте и проанализируйте дерево.

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

Ответы:

Вариант 1

1. 18 чисел

3. 6 способов

6. Игрок, делающий первый ход (-1)

Вариант 2

1. 32 числа

2. 19

3. 15 программ

4. 6 разных чисел

5. 17 программ

6. Игрок, делающий первый ход (-1)

Вариант 3

1. 28 чисел

2. 12

3. 15 программ

4. 6 разных чисел

5. 8 программ

6. Игрок, делающий первый ход (-1)