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

1 Переборные задачи

2 Задача 1 У исполнителя Калькулятор две команды: 1. прибавь умножь на 2. Первая из них увеличивает число на экране на 1, вторая – увеличивает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команды? Решение Примерами программ могут быть 1122, 1212 или По сути – это двоичные числа из 4-х знаков. Особенно наглядно это видно, если изменить нумерацию команд: 0. прибавь умножь на 2. Тогда программы будут выглядеть так: 0011, 0101, 0110.

3 Задача 1 У исполнителя Калькулятор две команды: 1. прибавь умножь на 2. Первая из них увеличивает число на экране на 1, вторая – увеличивает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команды? Решение Самое большое 4-х-значное двоичное число – это Одна восьмёрка + одна четвёрка + одна двойка + одна единица 1*8 + 1*4 + 1*2 + 1*1 = Значит, так можно закодировать 16 чисел (программ): от 0 до 15. Остаётся проверить, не получаются ли в результате выполнения этих 16-ти программ одинаковые числа. «Тысячи»«Сотни»«Десятки»«Единицы»

4 Задача 1 У исполнителя Калькулятор две команды: 1. прибавь умножь на 2. В файле perebor-zadanie.xlsx заполните самостоятельно оставшиеся позиции. Должен получиться ответ – 15. Решение

5 Задача 2 На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

6 Задача 2 На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H? Решение В В есть одна дорога. В F есть одна дорога. В Е приходят 3 дороги: 1) 1-я из А; 2) 2-я из В, но в В есть только одна дорога, значит к дороге из А добавляется одна дорога из В; 3) 3-я из F, но в F есть только одна дорога, значит к дорогам из А и В добавляется одна дорога из F;

7 Задача 2 На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H? Решение В С есть две дороги: 1) 1-я из В, а в В можно попасть одной дорогой, значит и в С через В можно попасть одной дорогой; 2) 2-я из Е, но в Е ведут 3 дороги, значит в С через Е можно попасть тремя дорогами. Итого, в С можно попасть 1+3 = 4 четырьмя дорогами.

8 Задача 2 На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H? Решение Проделайте аналогичные размышления для пунктов G, D и, наконец Н. В файле perebor-zadanie.xlsx впишите вместо знака «?» нужные числа.

9 Задача 3 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F. Построим граф F А В С E D 3 Найдем все пути из А в F 1) АBEF = 11 2) ABCEF = 9 3) 4) 5) Остальные пути просчитайте сами и заполните в файле

10 Задача 4 Задача Рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Какой из игроков выиграет, если будет играть безошибочно? Решение Надо сделать перебор всех возможных ходов. Удобно представлять ходы в виде таблицы: Числа – количество спичек после хода игрока. Например, после первого хода первого игрока может остаться 4 или 3 спички. Ответ в задаче таков: при правильной игре обязательно выиграет 1-й игрок. Для этого ему надо на первом ходе взять 1 спичку, тогда вторым ходом он выигрывает независимо от того, как сходил 2-й игрок. 1 игрок 2 игрок 1 игрок

11 Задача 4 Задача Рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Какой из игроков выиграет, если будет играть безошибочно? Решение Надо сделать перебор всех возможных ходов. Удобно представлять ходы в виде таблицы: Числа – количество спичек после хода игрока. Например, после первого хода первого игрока может остаться 4 или 3 спички. Ответ в задаче таков: при правильной игре обязательно выиграет 1-й игрок. Для этого ему надо на первом ходе взять 1 спичку, тогда вторым ходом он выигрывает независимо от того, как сходил 2-й игрок. 1 игрок 2 игрок 1 игрок

12 Задача 5 Задача Рассмотрим похожую игру: сначала в кучке лежит 7 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1, 2 или 3 спички; выигрывает тот, кто оставит в кучке 1 спичку (по-другому говоря, вынудит соперника взять последнюю спичку). Какой из игроков выиграет, если будет играть безошибочно? Решение Проделайте самостоятельно в файле perebor-zadanie.xlsx