Решение задач. Пе­ре­бор вариантов, по­стро­е­ние дерева.
методическая разработка по информатике и икт (11 класс) по теме

Слайд 1

ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Анализ программ с циклами и подпрограммами . В13 Разбор задач ЕГЭ

Слайд 2

Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2, 2. умножь на 3. Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раз. Программа для Утроителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 25? Ответ обоснуйте.

Слайд 3

Задача 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

Слайд 4

Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Арифметик две команды, которым присвоены номера: 1. прибавь 1, 2. прибавь 3. Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3. Программа для Арифметика — это последовательность команд. Сколько существует программ, которые число 7 преобразуют в число 20?

Слайд 5

Задача 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. Тогда справедлива формула:

Слайд 6

Задача 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

Слайд 7

Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Множик есть две команды: 1. умножь на 8, 2. подели на 2. Первая из них увеличивает число на экране в 8 раз, вторая – уменьшает его в 2 раза. Программа для Множика – это последовательность команд. Сколько различных чисел можно получить из числа 512 с помощью программы, которая содержит ровно 8 команд?

Слайд 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

Слайд 9

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Кузнечик две команды: 1.прибавь 7 2.вычти 5 Первая из них увеличивает число на экране на 7, вторая – уменьшает его на 5 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд? Ответ 8

Слайд 10

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 4 Сколько есть программ, которые число 1 преобразуют в число 55? Указание. Решить графом. Ответ 32

Слайд 11

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2 2. умножь на 2 Сколько есть программ, которые число 2 преобразуют в число 40? Указание. Решить графом . Многие ветки графа будут повторяться. Ответ 60

Слайд 12

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя четыре команды, которым присвоены номера: 1. прибавь 1, 2. сделай чётное, 3. сделай нечётное, 4. умножь на 10. Первая из них увеличивает на 1 исходное число x , вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвёртая умножает его на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15? Указание: решать графом. Ответ 84

Слайд 13

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © У исполнителя Прибавитель две команды, которым присвоены номера: 1. прибавь 1, 2. увеличь старшую цифру числа на 1. Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Программа для Прибавителя — это последовательность команд. Сколько есть программ, которые число 10 преобразуют в число 33? Указание. Можно решить графом, можно сказать, что вторая команда, это всё равно что прибавить 10 (в нашем случае) и использовать формулу для числа перестановок с повторениями. Ответ 2 5