59 Рассмотри граф, представляющий схему дорог от дома, где живёт Коля, до школы. Нарисуй дерево перебора возможных маршрутов от дома Коли до школы. В качестве элементов такого дерева используй имена вершин графа. Через каждую точку можно проходить не больше одного раза, по дорогам со стрелками можно двигаться только в направлении стрелок. Какой путь оказался самым коротким?
Самый короткий путь Д - А - Е - Ж - Ш длиной 8 км.
60 Построй все подмножества множества V.
Для множества V, содержащего элементы: {Зеленый круг, Красный круг, Желтый круг, Синий круг}, мы можем построить все подмножества.
Число подмножеств множества из n элементов равно 2^n . В данном случае n=4, поэтому всего будет 2^4 =16 подмножеств.
Список всех подмножеств множества V:
{} (пустое множество) {Зеленый круг} {Красный круг} {Желтый круг} {Синий круг} {Зеленый круг, Красный круг} {Зеленый круг, Желтый круг} {Зеленый круг, Синий круг} {Красный круг, Желтый круг} {Красный круг, Синий круг} {Желтый круг, Синий круг} {Зеленый круг, Красный круг, Желтый круг} {Зеленый круг, Красный круг, Синий круг} {Зеленый круг, Желтый круг, Синий круг} {Красный круг, Желтый круг, Синий круг} {Зеленый круг, Красный круг, Желтый круг, Синий круг} Таким образом, это полный список всех подмножеств множества V.
61 Процесс вычисления значения арифметического выражения тоже можно изобразить при помощи дерева. В таком дереве каждый родитель является результатом арифметической операции, применённой ко всем его детям. При этом родитель изображается в виде знака этой операции. Для каждого дерева на-пиши арифметическое выражение, которое соответствует этому дереву.
А=2*5
В=(45/9)*(8+5)
С=8+(71-33)
D=(((7*89)+(6+17))+(15-8)
E=((21/3)*(4+5))*((26-7)+(8*9))
62 Реши задачу.
Крыса бежит по лабиринту, который устроен так, что сначала она должна выбрать один из двух проходов, затем один из трёх проходов, а за каждым из них её ожидают четыре прохода. Войдя в какой-то проход, крыса не может вернуться че рез него обратно. Сколькими различными путями крыса может пройти лабиринт от начала до конца?
Для решения задачи нужно найти общее количество путей, которые может выбрать крыса, исходя из структуры лабиринта.
На первом этапе у крысы 2 прохода. На втором этапе у крысы 3 прохода для каждого из предыдущих. На третьем этапе у крысы 4 прохода для каждого из проходов второго этапа. Чтобы найти общее количество путей, достаточно перемножить количество вариантов на каждом этапе:
2×3×4=24 Таким образом, крыса может пройти лабиринт 24 различными путями.
63 Инициалы — это первые буквы имени и отчества. Например, инициалы Татьяны Михайловны — Т. М., инициалы Николая Николаевича — Н. Н.
Сосчитай, сколько в русском языке может быть таких двухбуквенных инициалов.
Ясно, что в инициалах не встретятся буквы Ъ, Ь. Имена, начинающиеся на остальные буквы, даже если их нет в списке русских имён, могут встретиться в именах у других народов, например: Йорган, Ёшка, Щедрик. Поэтому остальные буквы следует учитывать.
Дерево перебора в этой задаче будет большим. Не строя дерева, опиши его по образцу:
1. В этом дереве ... уровня.
2. В этом дереве у каждого элемента первого уровня ровно ... детей.
3. В этом дереве всего ... листьев.
Теперь, пользуясь своим описанием, ответь на вопрос задачи.
В этом дереве 2 уровня. Первый уровень соответствует выбору первой буквы (инициала имени), а второй уровень — выбору второй буквы (инициала отчества).
В этом дереве у каждого элемента первого уровня ровно 31 ребёнок, потому что в русском алфавите 33 буквы, но исключены буквы Ъ и Ь, поэтому остаётся 31 возможная буква.
В этом дереве всего 31 × 31 = 961 лист. Это общее количество возможных двухбуквенных комбинаций.
64 Построй все такие последовательности бусин, для которых все следующие утверждения истинны:
Длина этой последовательности меньше 4.
Каждая бусина этой последовательности содержится в множестве Р.
В этой последовательности есть две одинаковые бусины.
Красный квадрат, красный квадрат Красный круг, красный круг Красный квадрат, красный квадрат, красный круг Красный квадрат, красный круг, красный квадрат Красный круг, красный квадрат, красный квадрат Красный круг, красный круг, красный квадрат Красный круг, красный квадрат, красный круг Красный квадрат, красный круг, красный круг Красный квадрат, красный квадрат, красный квадрат Красный круг, красный круг, красный круг
65 Реши задачу.
В очереди стоят Юра, Миша, Вова, Саша и Олег. Юра стоит раньше Миши, но после Олега. Вова и Олег не стоят рядом. Саша не стоит рядом ни с Олегом, ни с Юрой, ни с Вовой. В каком порядке стоят ребята? Объясни, почему твой ответ — единственное возможное решение.
У нас есть пять человек: Юра, Миша, Вова, Саша и Олег. Условия:
Юра стоит раньше Миши, но после Олега. Вова и Олег не стоят рядом. Саша не стоит рядом ни с Олегом, ни с Юрой, ни с Вовой. Теперь давайте построим цепочки, как это предложено:
Юра стоит после Олега и раньше Миши. Следовательно, Олег - Юра - Миша.
Саша не может стоять рядом с Олегом, Юрой или Вовой. Это значит, что Саша может стоять только рядом с Мишей. Таким образом, Саша может быть либо на первом месте (рядом с Мишей на втором), либо на пятом месте (рядом с Мишей на четвёртом). Однако, учитывая, что Миша должен стоять после Юры, он занимает четвёртое место, а Саша — пятое место.
Вова не может стоять рядом с Олегом. Следовательно, Вова занимает третье место.
Теперь правильный порядок:
Олег стоит первым. Юра стоит вторым. Вова стоит третьим. Миша стоит четвёртым. Саша стоит пятым. Итак, верный порядок: Олег, Юра, Вова, Миша, Саша.
Проверка условий:
Юра стоит раньше Миши, но после Олега — соблюдено. Вова и Олег не стоят рядом — соблюдено. Саша не стоит рядом ни с Олегом, ни с Юрой, ни с Вовой — соблюдено. Ответ правильный: Олег, Юра, Вова, Миша, Саша.