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

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

Вариант 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? Для решения задачи постройте и проанализируйте дерево.

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

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

2 – вычесть 3.

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

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

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

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

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

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

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

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

Вариант 2

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

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

3.        На схеме изображены дороги между четырьмя населёнными пунктами А, Б, В, Г и указаны протяженности дорог.

Известно, что кратчайшее расстояние между наиболее удалёнными друг от друга пунктами составляет 7. Определите, при каком х это возможно. Для решения задачи заполните таблицу:

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

1 – прибавь 2,

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

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

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

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

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

2 – вычесть 3.

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

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

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

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

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

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

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