Slider

Задача №22. Перебор вариантов.

Автор материалов - Лада Борисовна Есакова.

Поиск количества программ по результату

Задачу такого типа можно решить, построив подробное дерево всех возможных вариантов наборов команд и подсчитав те, которые приведут к нужному результату. Однако, это очень длинный и объемный способ. Его использование может привести к вычислительным ошибкам, а при большой длине программы построение дерева вообще практически невозможно.

Рассмотрим более эффективный метод подсчета количества программ.

Пример 1.

У ис­пол­ни­те­ля Уве­ли­чи­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1. при­бавь 2,

2. умножь на 3.

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 2, вто­рая — умно­жа­ет его на 3.

Про­грам­ма для Уве­ли­чи­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число 31?

Ответ обос­нуй­те.

 

Решение:

Заполним таблицу со следующими столбцами:

«Число» - перечень всех чисел от 1 до 31;

«Числа-источники» - числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» - количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Заметим, что никаким набором указанных команд невозможно получить четное число из 1, значит, четные числа можем в таблице не рассматривать вообще.

Число

Числа-источники

Кол-во способов получения

1 1 1
3 1 2
5 3 2
7 5 2
9 3 ; 7 2+2=4
11 9 4
13 11 4
15 5 ; 13 2+4=6
17 15 6
19 17 6
21 7 ; 19 2+6=8
23 21 8
25 23 8
27 9 ; 25 4+8=12
29 27 12
31 29 12

 

Число 1 нам дано, т.е. его можно получить единственным способом: ничего не делая.

Число 3 можно получить из 1 двумя способами: командой 1. и командой 2. И т.д.

Заметим, что два источника могут быть только у чисел, кратным трем. Это наблюдение поможет нам быстро заполнить таблицу, т.к. количество способов увеличивается, когда рассматриваем число, кратное трем.

Например, число 9 можно получить из числа 3 и числа 7. Сложив количество способов получения чисел 3 и 7 (2+2=4), получим количество способов получения числа 9.

Полная таблица приведена для наглядности, можно было заполнить только строки с числами, кратными 3, т.к. только они меняют количество способов получения числа.

Для числа 31 получаем количество способов 12. Это и есть искомое количество программ.

 

Ответ: 12

 

Пример 2.

У ис­пол­ни­те­ля Ариф­ме­тик две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

1. при­бавь 1,

2. при­бавь 3.

Пер­вая из них уве­ли­чи­ва­ет на 1 число на экра­не, вто­рая уве­ли­чи­ва­ет это число на 3.

Про­грам­ма для Ариф­ме­ти­ка — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 15?

 

Решение:

Заполним таблицу со следующими строками:

«Число» - перечень всех чисел от 2 до 15;

«Числа-источники» - числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» - количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Число

Числа-источники

Кол-во способов получения

2 2 1
3 2 1
4 3 1
5 2 ; 4 1+1=2
6 3 ; 5 1+2=3
7 4 ; 6 1+3=4
8 5 ; 7 2+4=6
9 6 ; 8 3+6=9
10 7 ; 9 4+9=13
11 8 ; 10 6+13=19
12 9 ; 11 9+19=28
13 10 ; 12 13+28=41
14 11 ; 13 19+41=60
15 12 ; 14 28+60=88

Для числа 15 получаем количество способов 88. Это и есть искомое количество программ.

 

Ответ: 88

 

Пример 3.

Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя Май15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение:

Заполним таблицу со следующими строками:

«Число» - перечень всех чисел от 2 до 29;

«Числа-источники» - числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» - количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Число

Числа-источники

Кол-во способов получения

2 2 1
3 2 1
4 2 ; 3 1+1=2
5 4 2
6 3 ; 5 1+2=3
7 6 3
8 4 ; 7 2+3=5
9 8 5
10 5 ; 9 2+5=7
11 10 7
12 6 ; 11 3+7=10
13 12 10
14 7 ; 13 3+10=13
15 14 13
16 15 13
17 16 13
18 17 13
19 18 13
20 19 13
21 20 13
22 21 13
23 22 13
24 23 13
25    
26    
27    
28 14 13
29 28 13

До строки с числом 15 считаем все способы получения чисел. Начиная с числа 16 и до числа 24 (включительно) числа-источники 8-12 и способ получения числа применением команды «Умножить на 2» не подходят, т.к. траектория вычисления не содержит число 14. Для этих чисел учитываем одно число-источник (предыдущее) и один способ получения – «Прибавить 1».

Числа 25 вообще не должно быть в траектории, а значит, числа 26 и 27 получить невозможно.

Для числа 28 существует одно число-источник (14).

Для числа 29 получаем количество способов 13. Это и есть искомое количество программ.

Ответ: 13

 

Интенсивная подготовка

Бесплатные пробные ЕГЭ

Расписание курсов

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России)
                       +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

БЕСПЛАТНЫЙ РЕПЕТИЦИОННЫЙ ЕГЭ ОНЛАЙН

Типы подготовки:
Сказать спасибо
РЕКОМЕНДУЕМ:
ege-tv

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Смотреть

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Позвоните мне

Все поля обязательны для заполнения

Отправить

Премиум

Вся часть 2 на ЕГЭ по математике, от задачи 13 до задачи 19. То, о чем не рассказывают даже ваши репетиторы. Все приемы решения задач части 2. Оформление задач на экзамене. Десятки реальных задач ЕГЭ, от простых до самых сложных.

Видеокурс «Премиум» состоит из 7 курсов  для освоения части 2 ЕГЭ по математике (задачи 13-19). Длительность каждого курса - от 3,5 до 4,5 часов.

  1. Уравнения (задача 13)
  2. Стереометрия (задача 14)
  3. Неравенства (задача 15)
  4. Геометрия (задача 16)
  5. Финансовая математика (задача 17)
  6. Параметры (задача 18)
  7. Нестандартная задача на числа и их свойства (задача 19).

Здесь то, чего нет в учебниках. Чего вам не расскажут в школе. Приемы, методы и секреты решения задач части 2.

Каждая тема разобрана с нуля. Десятки специально подобранных задач, каждая из которых помогает понять «подводные камни» и хитрости решения.  Автор видеокурса Премиум - репетитор-профессионал Анна Малкова.

Получи пятерку

Видеокурс «Получи пятерку» включает все темы, необходимые для успешной сдачи ЕГЭ по математике на 60-65 баллов. Полностью все задачи 1-13 Профильного ЕГЭ по математике. Подходит также для сдачи Базового ЕГЭ по математике. Если вы хотите сдать ЕГЭ на 90-100 баллов, вам надо решать часть 1 за 30 минут и без ошибок!

Курс подготовки к ЕГЭ для 10-11 класса, а также для преподавателей. Все необходимое, чтобы решить часть 1 ЕГЭ по математике (первые 12 задач) и задачу 13 (тригонометрия). А это более 70 баллов на ЕГЭ, и без них не обойтись ни стобалльнику, ни гуманитарию.

Вся необходимая теория. Быстрые способы решения, ловушки и секреты ЕГЭ. Разобраны все актуальные задания части 1 из Банка заданий ФИПИ. Курс полностью соответствует требованиям ЕГЭ-2018.

Курс содержит 5 больших тем, по 2,5 часа каждая. Каждая тема дается с нуля, просто и понятно.

Сотни заданий ЕГЭ. Текстовые задачи и теория вероятностей. Простые и легко запоминаемые алгоритмы решения задач. Геометрия. Теория, справочный материал, разбор всех типов заданий ЕГЭ. Стереометрия. Хитрые приемы решения, полезные шпаргалки, развитие пространственного воображения. Тригонометрия с нуля - до задачи 13. Понимание вместо зубрежки. Наглядное объяснение сложных понятий. Алгебра. Корни, степени и логарифмы, функция и производная. База для решения сложных задач 2 части ЕГЭ.

Сразу после оплаты вы получите ссылки на скачивание видеокурсов и уникальные ключи к ним.

Задачи комплекта «Математические тренинги - 2019» непростые. В каждой – интересные хитрости, «подводные камни», полезные секреты.

Варианты составлены так, чтобы охватить все возможные сложные задачи, как первой, так и второй части ЕГЭ по математике.

Как пользоваться?

  1. Не надо сразу просматривать задачи (и решения) всех вариантов. Такое читерство вам только помешает. Берите по одному! Задачи решайте по однойи старайтесь довести до ответа.
  2. Если почти ничего не получилось – начинать надо не с решения вариантов, а с изучения математики. Вам помогут книга для подготовки к ЕГЭи Годовой Онлайн-курс.
  3. Если вы правильно решили из первого варианта Маттренингов 5-7 задач – значит, знаний не хватает. Смотри пункт 1: Книгаи Годовой Онлайн-курс!
  4. Обязательно разберите правильные решения. Посмотрите видеоразбор – в нем тоже много полезного.
  5. Можно решать самостоятельно или вместе с друзьями. Или всем классом. А потом смотреть видеоразбор варианта.

Стоимость комплекта «Математические тренинги – 2019» - всего 1100 рублей. За 5 вариантов с решениями и видеоразбором каждого.