Кратко по теме
Сначала разберите алгоритм и пример на презентации; письменно выполните задания ниже. УМК ФГОС: данные → действие → проверка результата. Тема знакомит с деревом как способом наглядного представления всевозможных вариантов выбора. Мы научимся строить дерево перебора, чтобы ничего не упустить и не посчитать лишний раз, а также использовать его для решения комбинаторных задач.
Опора
- Количество листьев дерева равно числу всех возможных вариантов перебора.
- Если на каждом уровне дерева количество ветвей одинаково, то общее число листьев можно вычислить по формуле: N = k^n, где k — число вариантов на каждом шаге, n — число шагов.
- Дерево перебора можно строить для задач на составление слов, чисел, маршрутов, расписаний и т.д.
- При построении дерева важно соблюдать порядок: сначала перебираем все варианты для первого шага, затем для каждого — для второго и так далее.
- Дерево перебора является частным случаем графа, поэтому для него справедливы основные понятия теории графов.
- Дерево — это граф без циклов, в котором от корня к листьям идут ветви.
Задания
- 1Таблица: понятие / определение / пример — 4 строки по «Дерево. Перебор вариантов с помощью дерева».
бланк · таблица
Заполните таблицу по столбцам
понятие определение - 2Игра «Найди пару»: «данные ↔ обработка», «алгоритм ↔ шаги», «ошибка ↔ проверка».
бланк · соедини карточки
Соедините пары линиями или запишите соответствия (А–1, Б–2…)
данныеалгоритмошибкаобработкашагипроверкаСоответствия: А— Б— В—