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

Кирсанов Илья Андреевич

В22

Скачать:

ВложениеРазмер
Файл v13.razbor_zadach_ege.pptx121.1 КБ

Предварительный просмотр:


Подписи к слайдам:

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


По теме: методические разработки, презентации и конспекты

Решение задач варианта егэ

полностью разобраны все задачи с в1 до в14...

Элементы математической статистики, комбинаторики и теории вероятности. Решение задач из вариантов ЕГЭ.

Элементы математической статистики, комбинаторики и теории вероятности.Решение задач из вариантов ЕГЭ. Презентация для учителей, а так же учеников 9-11 классов....

Практическая работа №2 "Решение генетических задач".10 класс (4 варианта).

В практической работе представлены задачи на дигибридное скрещивание, наследование генов, локализованных в половых хромосомах....

Вариант решения задачи 23 ЕГЭ по информатике. "Системы логических уравнений".

Рассмотрен вариант решения задачи 23 демоверсии ЕГЭ по информатике. Применяется метод отображения....

Презентация "Решение задач тренировочных вариантов"

Презентация "Решение задач тренировочных вариантов"...