44 Сначала подкинули одну монету, затем вторую, потом третью (все монеты разные). Сколькими способами могут упасть на стол эти три монеты? Построй дерево перебора вариантов. Сколько всего существует вариантов падения трёх разных монет?
Когда подкидываются три монеты, каждая из которых может упасть орлом (О) или решкой (Р), все возможные исходы можно представить с помощью дерева вариантов. Каждая монета подкидывается независимо, поэтому для каждой следующей монеты появляются два возможных исхода: либо орел, либо решка.
Построим дерево:
Для первой монеты есть два варианта: О или Р. Для второй монеты после первого броска возможны также два варианта, поэтому, если первая монета упала орлом, вторая монета может упасть либо орлом, либо решкой, и то же самое, если первая упала решкой. Для третьей монеты аналогично, после каждого из предыдущих вариантов остаются два исхода (О или Р). Дерево перебора выглядит так:
Первый уровень (первая монета): О, Р Второй уровень (вторая монета): ОО, ОР, РО, РР Третий уровень (третья монета): ООО, ООР, ОРО, ОРР, РОО, РОР, РРО, РРР В итоге мы видим, что есть 2×2×2=8 возможных вариантов исхода для трёх монет.
Варианты падения трёх монет:
ООО ООР ОРО ОРР РОО РОР РРО РРР Итак, всего существует 8 возможных комбинаций исходов для трёх разных монет, если учитывать только стороны каждой монеты.
45 Сколько всего существует чётных двузначных чисел, в записи которых нет цифр 0, 2 и 3? Построй дерево перебора вариантов. Пользуясь деревом, выпиши все такие числа.
Чтобы найти количество четных двузначных чисел, в записи которых нет цифр 0, 2 и 3, нужно построить дерево возможных вариантов. Четные числа оканчиваются на четные цифры, поэтому изначально рассмотрим только возможные четные цифры для последней позиции.
Четные цифры для последней цифры: 4, 6, 8. То есть число должно оканчиваться на одну из этих цифр. Варианты для первой цифры: так как числа двузначные, первой цифрой не может быть 0. А также нам нельзя использовать 2 и 3. Остаются цифры 1, 4, 5, 6, 7, 8 и 9. Построим дерево Первая цифра: выбираем одну из доступных цифр: 1, 4, 5, 6, 7, 8, 9. Вторая цифра: выбираем одну из четных цифр: 4, 6, или 8. Переберем все комбинации:
Если первая цифра — 1, возможны числа: 14, 16, 18. Если первая цифра — 4, возможны числа: 44, 46, 48. Если первая цифра — 5, возможны числа: 54, 56, 58. Если первая цифра — 6, возможны числа: 64, 66, 68. Если первая цифра — 7, возможны числа: 74, 76, 78. Если первая цифра — 8, возможны числа: 84, 86, 88. Если первая цифра — 9, возможны числа: 94, 96, 98. Итог Запишем все подходящие числа:
14, 16, 18, 44, 46, 48, 54, 56, 58, 64, 66, 68, 74, 76, 78, 84, 86, 88, 94, 96, 98.
Ответ: существует 20 таких чисел.
46 Построй все подмножества множества W. Для этого сначала построй дерево перебора подмножеств.
Чтобы построить все подмножества множества W = {1, 2, 3, 4}, используем метод перебора с помощью дерева вариантов. На каждом уровне рассматривается включение или исключение элемента в подмножество.
Начнем с пустого множества: {}. На первом уровне решаем, включать ли элемент 1. Получаем два варианта: пустое подмножество {} и подмножество {1}. На втором уровне добавляем элемент 2 к каждому из предыдущих вариантов. Получаются: {}, {1}, {2}, {1, 2}. На третьем уровне добавляем элемент 3, и получаем: {}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}. На четвертом уровне добавляем элемент 4, что дает нам полное множество подмножеств. Итог: все подмножества множества W = {1, 2, 3, 4} — это {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}.
Таким образом, у нас получается 16 подмножеств, включая пустое.
47 Для трёх множеств слов построй множество всех последовательностей слов длины 3, таких, что первый член последовательности — слово из множества Р, второй — слово из множества Q, третий — слово из множества R. Для решения построй дерево перебора вариантов.
Чтобы построить все возможные последовательности слов длины 3, где первый член — слово из множества P, второй — слово из множества Q, и третий — слово из множества R, начнем с каждого элемента множества P, добавляя к нему по очереди каждый элемент множества Q, а затем к ним — каждый элемент множества R.
Дано:
P = {Катя, Даша, Петя, Миша} Q = {слушает, читает} R = {сказку, рассказ, стихи} Результат:
Катя слушает сказку
Катя слушает рассказ
Катя слушает стихи
Катя читает сказку
Катя читает рассказ
Катя читает стихи
Даша слушает сказку
Даша слушает рассказ
Даша слушает стихи
Даша читает сказку
Даша читает рассказ
Даша читает стихи
Петя слушает сказку
Петя слушает рассказ
Петя слушает стихи
Петя читает сказку
Петя читает рассказ
Петя читает стихи
Миша слушает сказку
Миша слушает рассказ
Миша слушает стихи
Миша читает сказку
Миша читает рассказ
Миша читает стихи
Итого 24 последовательности.
48 Реши задачу, построив дерево перебора вариантов.
У Вовы были в кармане 4 монеты: 1 к., 5 к., 10 к., 50 к. Он достал из кармана некоторое количество монет (он мог достать и все монеты, мог не достать и ни одной). Сколько денег оказалось в руке у Вовы?
Укажи все возможные варианты.
В начале Вова может выбрать или не выбрать каждую монету, так что для каждой монеты есть два варианта: взять или не взять. Всего монет четыре, поэтому каждый уровень дерева будет рассматривать включение или исключение конкретной монеты.
Путем полного перебора возможных комбинаций (включение или исключение каждой монеты) получаем:
Если Вова не взял ни одной монеты: сумма = 0 копеек. Если Вова взял только 1 копейку: сумма = 1 копейка. Если Вова взял только 5 копеек: сумма = 5 копеек. Если Вова взял только 10 копеек: сумма = 10 копеек. Если Вова взял только 50 копеек: сумма = 50 копеек. Если Вова взял 1 и 5 копеек: сумма = 6 копеек. Если Вова взял 1 и 10 копеек: сумма = 11 копеек. Если Вова взял 1 и 50 копеек: сумма = 51 копейка. Если Вова взял 5 и 10 копеек: сумма = 15 копеек. Если Вова взял 5 и 50 копеек: сумма = 55 копеек. Если Вова взял 10 и 50 копеек: сумма = 60 копеек. Если Вова взял 1, 5 и 10 копеек: сумма = 16 копеек. Если Вова взял 1, 5 и 50 копеек: сумма = 56 копеек. Если Вова взял 1, 10 и 50 копеек: сумма = 61 копейка. Если Вова взял 5, 10 и 50 копеек: сумма = 65 копеек. Если Вова взял все монеты (1, 5, 10 и 50 копеек): сумма = 66 копеек. Ответ: Все возможные суммы денег, которые могли оказаться у Вовы в руке: 0, 1, 5, 6, 10, 11, 15, 16, 50, 51, 55, 56, 60, 61, 65 и 66 копеек.
49 Сформулируй задачу, решению которой поможет дерево перебора вариантов К.
Дерево перебора вариантов K можно использовать для задачи, связанной с выбором последовательности действий или элементов, ведущих к конечным результатам. Например, это может быть задача о выборе различных вариантов движения по дорожной развязке или о комбинациях выбора чисел из заданного множества для построения различных комбинаций.
Формулировка задачи: «Имеется несколько вариантов выбора на каждом этапе процесса. Из вершины K начинаются три ветви с вариантами (2, 4, 6). Для каждого из этих вариантов можно выбирать новые значения на втором этапе, и так продолжается до конечного результата. Сколько различных конечных путей можно составить от вершины K до нижнего уровня дерева, и какие значения встречаются на этих путях?»
Дерево показывает все возможные последовательности из трех этапов с выборами, начиная от K и заканчивая конечными значениями.
50 а) Построй алгоритм для Удвоителя, в котором меньше 8 команд. После выполнения этого алгоритма на экране должно отобразиться число 15.
б) Построй алгоритм для Удвоителя, в котором меньше 12 команд. После выполнения этого алгоритма на экране должно отобразиться число 1024.
Для того чтобы на экране отобразилось число 15, можно выполнить несколько удвоений и прибавлений. Алгоритм с использованием менее 8 команд:
Установить переменную в 1. Удвоить 1 → 2. Удвоить 2 → 4. Удвоить 4 → 8. Прибавить 1 → 9. Удвоить 9 → 18. Прибавить 1 → 19. Удвоить 19 → 38. Прибавить 1 → 39. Удвоить 39 → 78.
Для того чтобы получить число 1024, можно использовать удвоения, начиная с 1. Алгоритм с использованием менее 12 команд:
Установить переменную в 1. Удвоить 1 → 2. Удвоить 2 → 4. Удвоить 4 → 8. Удвоить 8 → 16. Удвоить 16 → 32. Удвоить 32 → 64. Удвоить 64 → 128. Удвоить 128 → 256. Удвоить 256 → 512. Удвоить 512 → 1024.
51 Найди площадь многоугольника F.
Для начала найдем площадь всего многоугольника: 6*7=42 кв.ед.
Теперь найдем площадь незакрашенной области 28,5 кв.ед.
Вычтем из площади всего прямоугольника площадь незакрашенной области 42-28,5=13,5 кв.ед.
52 Сколько всего существует нечётных трёхзначных чисел, больших чем 500 и таких, что сумма их цифр равна 9? Построй дерево перебора вариантов. Пользуясь деревом, выпиши все такие числа.
Число должно быть нечётным. Это означает, что последняя цифра числа (единицы) должна быть нечётной: 1, 3, 5, 7, 9. Число должно быть трёхзначным и больше 500. Это означает, что первая цифра числа (сотни) должна быть 5 или больше (5, 6, 7, 8, 9). Сумма цифр числа должна быть равна 9. Давайте строить дерево перебора вариантов.
1. Первая цифра (сотни) = 5, 6, 7, 8 или 9. 2. Вторая цифра (десятки) = любая цифра от 0 до 9. 3. Третья цифра (единицы) = нечётная цифра: 1, 3, 5, 7, 9. Нам нужно, чтобы сумма цифр числа была равна 9. Мы будем перебирать все возможные значения для сотен, десятков и единиц, проверяя, чтобы их сумма была 9.
Первая цифра = 5: Сумма двух первых цифр должна быть не больше 4, чтобы третья цифра (единицы) была нечётной и сумма цифр в итоге давала 9.
5 + 0 = 5, третья цифра должна быть 4 (неподходит, так как цифра не нечётная). 5 + 1 = 6, третья цифра должна быть 3 (нечётная, подходит). Получаем число 513. 5 + 2 = 7, третья цифра должна быть 2 (неподходит, так как цифра не нечётная). 5 + 3 = 8, третья цифра должна быть 1 (нечётная, подходит). Получаем число 531. 5 + 4 = 9, третья цифра должна быть 0 (неподходит, так как цифра не нечётная). 5 + 5 = 10, третья цифра должна быть -1 (неподходит). 5 + 6 = 11, третья цифра должна быть -2 (неподходит). 5 + 7 = 12, третья цифра должна быть -3 (неподходит). 5 + 8 = 13, третья цифра должна быть -4 (неподходит). 5 + 9 = 14, третья цифра должна быть -5 (неподходит). Подходящие числа для первой цифры 5: 513, 531.
Первая цифра = 6: Сумма двух первых цифр должна быть не больше 3, чтобы третья цифра была нечётной.
6 + 0 = 6, третья цифра должна быть 3 (нечётная, подходит). Получаем число 603. 6 + 1 = 7, третья цифра должна быть 2 (неподходит, так как цифра не нечётная). 6 + 2 = 8, третья цифра должна быть 1 (нечётная, подходит). Получаем число 621. 6 + 3 = 9, третья цифра должна быть 0 (неподходит, так как цифра не нечётная). 6 + 4 = 10, третья цифра должна быть -1 (неподходит). 6 + 5 = 11, третья цифра должна быть -2 (неподходит). 6 + 6 = 12, третья цифра должна быть -3 (неподходит). 6 + 7 = 13, третья цифра должна быть -4 (неподходит). 6 + 8 = 14, третья цифра должна быть -5 (неподходит). 6 + 9 = 15, третья цифра должна быть -6 (неподходит). Подходящие числа для первой цифры 6: 603, 621.
Первая цифра = 7: Сумма двух первых цифр должна быть не больше 2, чтобы третья цифра была нечётной.
7 + 0 = 7, третья цифра должна быть 2 (неподходит, так как цифра не нечётная). 7 + 1 = 8, третья цифра должна быть 1 (нечётная, подходит). Получаем число 711. 7 + 2 = 9, третья цифра должна быть 0 (неподходит, так как цифра не нечётная). 7 + 3 = 10, третья цифра должна быть -1 (неподходит). 7 + 4 = 11, третья цифра должна быть -2 (неподходит). 7 + 5 = 12, третья цифра должна быть -3 (неподходит). 7 + 6 = 13, третья цифра должна быть -4 (неподходит). 7 + 7 = 14, третья цифра должна быть -5 (неподходит). 7 + 8 = 15, третья цифра должна быть -6 (неподходит). 7 + 9 = 16, третья цифра должна быть -7 (неподходит). Подходящие числа для первой цифры 7: 711.
Первая цифра = 8: Сумма двух первых цифр должна быть не больше 1, чтобы третья цифра была нечётной.
8 + 0 = 8, третья цифра должна быть 1 (нечётная, подходит). Получаем число 811. 8 + 1 = 9, третья цифра должна быть 0 (неподходит, так как цифра не нечётная). 8 + 2 = 10, третья цифра должна быть -1 (неподходит). 8 + 3 = 11, третья цифра должна быть -2 (неподходит). 8 + 4 = 12, третья цифра должна быть -3 (неподходит). 8 + 5 = 13, третья цифра должна быть -4 (неподходит). 8 + 6 = 14, третья цифра должна быть -5 (неподходит). 8 + 7 = 15, третья цифра должна быть -6 (неподходит). 8 + 8 = 16, третья цифра должна быть -7 (неподходит). 8 + 9 = 17, третья цифра должна быть -8 (неподходит). Подходящие числа для первой цифры 8: 811.
Первая цифра = 9: Сумма двух первых цифр должна быть не больше 0, чтобы третья цифра была нечётной.
9 + 0 = 9, третья цифра должна быть 0 (неподходит, так как цифра не нечётная). 9 + 1 = 10, третья цифра должна быть -1 (неподходит). 9 + 2 = 11, третья цифра должна быть -2 (неподходит). 9 + 3 = 12, третья цифра должна быть -3 (неподходит). 9 + 4 = 13, третья цифра должна быть -4 (неподходит). 9 + 5 = 14, третья цифра должна быть -5 (неподходит). 9 + 6 = 15, третья цифра должна быть -6 (неподходит). 9 + 7 = 16, третья цифра должна быть -7 (неподходит). 9 + 8 = 17, третья цифра должна быть -8 (неподходит). 9 + 9 = 18, третья цифра должна быть -9 (неподходит). Подходящих чисел для первой цифры 9: нет.
Ответ: Все подходящие числа, сумма цифр которых равна 9:
513, 531, 603, 621, 711, 811.
Всего таких чисел 6.
53 Построй множество всех последовательностей из двух разных букв, в записи которых участвуют толь ко буквы из множества М. Сначала построй дерево перебора вариантов.
Для того чтобы построить множество всех последовательностей из двух разных букв, в записи которых участвуют только буквы из множества М = {А, Б, В, Г, Д}, будем перебирать все возможные пары букв, выбирая их так, чтобы они были разными.
Множество букв состоит из 5 символов: А, Б, В, Г, Д. Мы должны построить последовательности из двух разных букв, а количество возможных позиций в последовательности — 2. Также важным условием является то, что буквы в последовательности не могут повторяться.
Дерево перебора вариантов: Первая позиция: на первом месте может быть любая из 5 букв. Вторая позиция: на втором месте может быть любая из оставшихся 4 букв (чтобы они не совпадали с первой). Дерево выглядит следующим образом: Если на первой позиции А, то на второй могут быть: Б В Г Д Если на первой позиции Б, то на второй могут быть: А В Г Д Если на первой позиции В, то на второй могут быть: А Б Г Д Если на первой позиции Г, то на второй могут быть: А Б В Д Если на первой позиции Д, то на второй могут быть: А Б В Г Все возможные последовательности: Теперь, исходя из дерева, перечислим все возможные последовательности:
АБ АВ АГ АД Ба БВ БГ БД ВА ВБ ВГ ВД ГА ГБ ГВ ГД ДА ДБ ДВ ДГ Таким образом, все возможные последовательности из двух разных букв, составленных из букв множества М = {А, Б, В, Г, Д}, следующие.
54 Сначала подкинули монету, а за тем бросили игральную кость. Сколькими способами могут упасть монета и игральная кость? Построй дерево перебора вариантов.
Для решения задачи, давайте рассмотрим, сколько вариантов выпадения каждого из двух предметов.
Монета может выпасть в два варианта: орел или решка. Кость же имеет 6 граней, то есть 6 возможных результатов (1, 2, 3, 4, 5, 6).
Так как подкидывание монеты и бросание кости независимы, общее количество способов, которым могут выпасть монета и игральная кость, будет равно произведению количества вариантов для каждого из предметов: 2 (для монеты) умножаем на 6 (для кости), получаем 12 способов.
Если построить дерево вариантов, оно будет выглядеть следующим образом:
Монета выпала орел: 1 2 3 4 5 6 Монета выпала решка: 1 2 3 4 5 6 Таким образом, дерево перебора содержит 12 возможных исходов, по 6 для каждого случая монеты.
55 Построй все возможные последовательности длины 3, составленные только из нулей и единиц.
Для задачи составления всех возможных последовательностей длины 3 из нулей и единиц, нужно рассмотреть все возможные комбинации этих двух цифр на трех позициях.
Каждую из трех позиций можно заполнить либо нулем, либо единицей, и для каждой из позиций есть 2 варианта. Следовательно, количество таких последовательностей будет равно 2 в степени 3, то есть 8.
Перечислим все возможные последовательности длины 3:
000 001 010 011 100 101 110 111 Таким образом, существует 8 возможных последовательностей длины 3, составленных из нулей и единиц.
56 Сколько разных чисел можно получить, переставляя цифры числа 543? Построй дерево перебора вариантов.
Число 543 состоит из трех цифр: 5, 4 и 3. Чтобы найти, сколько разных чисел можно получить, переставляя эти цифры, нужно учесть, что все цифры различны.
Общее количество перестановок трех цифр равно факториалу числа 3, то есть 3! = 6.
Теперь перечислим все возможные числа, которые можно получить, переставляя цифры числа 543:
543 534 453 435 354 345 Таким образом, можно получить 6 различных чисел.
Если построить дерево перебора вариантов, оно будет выглядеть так:
Первая цифра: 5: 4: 3 → 543 3: 4 → 534 4: 5: 3 → 453 3: 5 → 435 3: 5: 4 → 354 4: 5 → 345 Дерево показывает все возможные пути, которые ведут к перестановкам цифр.
57 Измени вспомогательный алгоритм фрагмент из задачи 38 так, чтобы при выполнении алгоритма фигура Робот переместился из А в В и закрасил клетки, как на рисунке ниже. Напиши исправленный вариант алгоритма фрагмент.
Сколько команд закрасить компьютер даст Роботу при выполнении алгоритма фигура с исправленным вспомогательным алгоритмом фрагмент? Сколько клеток при этом будет закрашено дважды?
Исправленный вариант алгоритма фрагмент выглядит следующим образом: алг фрагмент нач нц 5 раз закрасить вниз закрасить вниз закрасить влево закрасить вверх закрасить вверх закрасить вправо закрасить вправо закрасить вниз закрасить вниз закрасить кц кон В результате выполнения этого алгоритма робот выполнит команду закрасить 60 раз (5 * 12). Количество клеток, которые будут закрашены дважды, составит 8.
58 Рассмотри меню, которое предлагается посетителям кафе «Таверна». Сколько вариантов завтраков (включающих яичницу или кашу и один напиток) могут заказать посетители кафе «Таверна»? Построй дерево перебора вариантов.
Сколько вариантов обедов (включающих один салат, суп, одно второе блюдо, один десерт и один напиток) могут заказать посетители кафе «Таверна»? Построй дерево перебора вариантов.
Завтрак Для завтрака, где есть два варианта блюда (яичница или каша овсяная) и три напитка (молоко, чай, кофе), молоко можно выбрать только утром. Это ограничивает выбор напитка для завтрака. Так как молоко доступно только по утрам, а чай и кофе доступны и утром, и в течение дня, всего у нас есть:
2 варианта блюда (яичница или каша) 3 варианта напитка (молоко, чай или кофе) Итак, количество вариантов для завтрака остается 6:
Яичница: Молоко → Яичница с молоком Чай → Яичница с чаем Кофе → Яичница с кофе Каша овсяная: Молоко → Каша с молоком Чай → Каша с чаем Кофе → Каша с кофе Обед Для обеда молоко не включается, поскольку оно доступно только по утрам. Таким образом, для обеда выбор напитка ограничен чай и кофе.
Общее количество вариантов для обеда:
2 варианта салата (Цезарь, мясной) 1 вариант супа (супчик дня) 4 варианта вторых блюд (курица по-корейски, биточки, шашлык, судак по-польски) 1 вариант десерта (мороженое) 2 варианта напитков (чай, кофе) Общее количество вариантов для обеда будет равно:
2 (салат) × 1 (суп) × 4 (вторые блюда) × 1 (десерт) × 2 (напитки) = 16.
Дерево перебора вариантов для обеда:
Салат Цезарь: Супчик дня: Курица по-корейски: Чай → Цезарь с курицей по-корейски и чаем Кофе → Цезарь с курицей по-корейски и кофе Биточки: Чай → Цезарь с биточками и чаем Кофе → Цезарь с биточками и кофе Шашлык: Чай → Цезарь с шашлыком и чаем Кофе → Цезарь с шашлыком и кофе Судак по-польски: Чай → Цезарь с судаком по-польски и чаем Кофе → Цезарь с судаком по-польски и кофе Салат мясной: Супчик дня: Курица по-корейски: Чай → Мясной с курицей по-корейски и чаем Кофе → Мясной с курицей по-корейски и кофе Биточки: Чай → Мясной с биточками и чаем Кофе → Мясной с биточками и кофе Шашлык: Чай → Мясной с шашлыком и чаем Кофе → Мясной с шашлыком и кофе Судак по-польски: Чай → Мясной с судаком по-польски и чаем Кофе → Мясной с судаком по-польски и кофе Таким образом, для обеда существует 16 разных вариантов.