Решение задач. Перебор вариантов, построение дерева.
методическая разработка по информатике и икт (11 класс) по теме
Предварительный просмотр:
Подписи к слайдам:
Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2, 2. умножь на 3. Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раз. Программа для Утроителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 25? Ответ обоснуйте.
Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Такая задача решается графом, начиная с конца. 25 не делится на 3= > мы получили 25 из 23 командой 1. 23 не делится на 3= > мы получили 23 из 21 командой 1. 21 мы могли получить из 19 командой 1 или из 7 командой 2. Рассуждая таким образом строим граф возможных вариантов, получаем 8 путей, 8 наборов команд, которыми можно из 1 получить 25. Ответ 8 21 25 23 19 7 17 15 5 3 1 1 5 13 11 9 3 7 3 1 1 5 3 1 1 1 1
Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Арифметик две команды, которым присвоены номера: 1. прибавь 1, 2. прибавь 3. Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3. Программа для Арифметика — это последовательность команд. Сколько существует программ, которые число 7 преобразуют в число 20?
Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Конечно эту задачу тоже можно решить графом, но это не рационально. От перестановки слагаемых местами сумма не поменяется, но программы содержащие команды 1112221 и 1212211 считаются разными. 20-7=13 – сумма увеличится на 13. Максимальное количество команд -13(13 раз прибавили 1) Минимальное количество команд 5(13:3=4 и 1 в остатке, т.е. потребуется 4 команды под номером 2 и одна команда под номером 1. Число 13 нечётное, но сумма 2-х команд – четная! = > нам потребуется нечетное количество команд, от 5 до 13: 5,7,9,11,13. Пусть n = m 1 + m 2 – общее количество команд, где m 1 - количество команд №1, m 2 - количество команд №2. Тогда справедлива формула:
Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © n m 1 m 2 P n (m 1 ,m 2 )= 5 1 4 5!/(1!*4!)= 5 – программ длины 5 команд. 7 4 3 7!/(4!*3!)=35 – программ длины 7 команд. 9 7 2 9!/(7!*2!)=36 – программ длины 9 команд. 11 10 1 11!/(10!*1!)=11 – программ длины 11 команд. 13 13 0 13!/(13!*0!)=1 – программа длины 13 команд. Представим всё в виде таблицы: Всего получим:5+35+36+11+1=88 команд(согласитесь, что граф получится слишком большой). *Формула называется « Число перестановок c повторениями» Ответ 88
Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Множик есть две команды: 1. умножь на 8, 2. подели на 2. Первая из них увеличивает число на экране в 8 раз, вторая – уменьшает его в 2 раза. Программа для Множика – это последовательность команд. Сколько различных чисел можно получить из числа 512 с помощью программы, которая содержит ровно 8 команд?
Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение: От перестановок множителей произведение не меняется, поэтому, подсчитав количество возможных программ, найдём количество разных чисел. Запишем все программы в виде набора команд, с точностью до перестановки: Всего 9 разных команд без учёта перестановок. Ответ 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 2 1 1 1 1 2 2 2 2 1 1 1 2 2 2 2 2 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Кузнечик две команды: 1.прибавь 7 2.вычти 5 Первая из них увеличивает число на экране на 7, вторая – уменьшает его на 5 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд? Ответ 8
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 4 Сколько есть программ, которые число 1 преобразуют в число 55? Указание. Решить графом. Ответ 32
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2 2. умножь на 2 Сколько есть программ, которые число 2 преобразуют в число 40? Указание. Решить графом . Многие ветки графа будут повторяться. Ответ 60
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя четыре команды, которым присвоены номера: 1. прибавь 1, 2. сделай чётное, 3. сделай нечётное, 4. умножь на 10. Первая из них увеличивает на 1 исходное число x , вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвёртая умножает его на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15? Указание: решать графом. Ответ 84
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Прибавитель две команды, которым присвоены номера: 1. прибавь 1, 2. увеличь старшую цифру числа на 1. Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Программа для Прибавителя — это последовательность команд. Сколько есть программ, которые число 10 преобразуют в число 33? Указание. Можно решить графом, можно сказать, что вторая команда, это всё равно что прибавить 10 (в нашем случае) и использовать формулу для числа перестановок с повторениями. Ответ 2 5
По теме: методические разработки, презентации и конспекты
Организация процесса учения учащихся при решении задач. Логико-психологические этапы решения задач
Этот материал будет интересен молодым специалистам...
Решение задач варианта егэ
полностью разобраны все задачи с в1 до в14...
Элементы математической статистики, комбинаторики и теории вероятности.Решение задач из вариантов ЕГЭ.
Элементы математической статистики, комбинаторики и теории вероятности.Решение задач из вариантов ЕГЭ. Презентация для учителей, а так же учеников 9-11 классов....
Практическая работа №2 "Решение генетических задач".10 класс (4 варианта).
В практической работе представлены задачи на дигибридное скрещивание, наследование генов, локализованных в половых хромосомах....
Вариант решения задачи 23 ЕГЭ по информатике. "Системы логических уравнений".
Рассмотрен вариант решения задачи 23 демоверсии ЕГЭ по информатике. Применяется метод отображения....
Решение задач на перебор вариантов
Перебор вариантов...
Презентация "Решение задач тренировочных вариантов"
Презентация "Решение задач тренировочных вариантов"...