Лишняя информация
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


"Лишняя информация"


Perfect Money

"Лишняя информация"

Вашему вниманию предлагается СТАНДАРТНЫЙ (но сокращённый) аналог задачи с развёрнутым ответом КИМ ЕГЭ. Предполагается, что учащийся должен уметь применить элементарные знания в области математики для исключения "лишних" возможностей, предоставленных в условии задачи. Использование всех данных из показанного условия возможно (хотя нежелательно), само по себе не приводит к снижению экспертной оценки, но может значительно увеличить время выполнения решения.

Текст задачи. У некоторого исполнителя есть три команды, которым присвоены номера:
1. умножь на 2,
2. умножь на 3,
3. умножь на 5.

Первая из них увеличивает число на экране в два раза, вторая — в три, третья — в пять раз.

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

Сколько есть программ, которые число 3 преобразуют в число 45?

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


Решение. Пользуясь указаниями, сделанными в Теоретическом введении и, конкретно, его Примере 8, построим таблицу, в которой отразим все возможные способы получения промежуточных и окончательного результатов. В этой таблице должны присутствовать следующие столбцы: "Количество программ", в котором будут показаны числа, описывающие количество способов получения каждого очередного промежуточного или окончательного результата, "Очередное число", где каждое из чисел является собственно начальным значением, промежуточным или окончательным результатом, и "Возможные следствия", содержащий все те числа, которые можно получить из соответствующего значения, записанного в предыдущем столбце, не превосходящие при этом конечное число. Получается, что заголовки таблицы выглядят так:

Количество программОчередное числоВозможные следствия

Самый первый столбец этой таблицы будем заполнять в последнюю очередь.

В первую строку второго столбца запишем исходное число:

Количество программОчередное числоВозможные следствия
 3 

Из этого числа можно вывести три других: его умножением на два, три и пять соответственно получаем 6, 9 и 15. Запишем эти числа в третий столбец:

Количество программОчередное числоВозможные следствия
 36, 9, 15

Важная ремарка. При решении данной задачи в третьем столбце таблицы всегда будут присутствовать не более чем три числа, являющиеся результатом осуществления над очередным числом заданных по условию операций: умножения на два, три и пять. При этом ни одно число третьего столбца не должно превосходить конечное число, указанное в условии задачи (ведь все три команды исполнителя позволяют увеличить очередное число, а не уменьшить его). Соответственно, максимальным числом и второго столбца может быть только конечное.

Теперь занесём во второй столбец таблицы число 6 (ведь оно следующее по порядку после 3) и покажем все "возможные следствия" из него. Будем также отмечать белым цветом те числа третьего столбца, которые на данный момент присутствуют во втором столбце (при решении задачи во время экзамена эти числа можно просто обвести или даже вычеркнуть, тем более в черновике):

Количество программОчередное числоВозможные следствия
 36, 9, 15
 612, 18, 30

Ниже числа 6 в столбце "Очередное число" логично записать 9, взятое из третьего столбца:

Количество программОчередное числоВозможные следствия
 36, 9, 15
 612, 18, 30
 918, 27, 45

А далее — 12, 15, 18…

Количество программОчередное числоВозможные следствия
 36, 9, 15
 612, 18, 30
 918, 27, 45
 1224, 36
 1530, 45
 1836

Как видно, из чисел 12 и 15 можно получить лишь по два других числа, поскольку третьи их "следствия" явно превосходят конечное 45. Из 18 вообще получается лишь одно число, не превосходящее конечный результат.

Продолжим заполнение таблицы. Последовательно внесём в её второй столбец числа 24, 27, 30, 36, 45 (именно в таком порядке).

Количество программОчередное числоВозможные следствия
 36, 9, 15
 612, 18, 30
 918, 27, 45
 1224, 36
 1530, 45
 1836
 24 
 27 
 30 
 36 
 45 

Замечаем: для только что внесённых в таблицу чисел невозможно определить ни одного следствия, ведь любое такое следствие превосходит требуемый к получению результат! Как показано в Примере 7 Теоретического введения, все эти числа, кроме, разумеется, конечного значения, можно исключить из второго и третьего столбцов таблицы так:

Количество программОчередное числоВозможные следствия
 36, 9, 15
 612, 18
 918, 45
 12 
 1545
 18 
 45 

Исключение чисел придётся продолжить, ведь из некоторых (12 и 18) теперь тоже отсутствуют следствия:

Количество программОчередное числоВозможные следствия
 36, 9, 15
 6 
 945
 1545
 45 

Осталось удалить из таблицы всё, что связано с "очередным числом" (и "возможным следствием") 6:

Количество программОчередное числоВозможные следствия
 39, 15
 945
 1545
 45 

Теперь стало возможным гораздо быстрее осуществить расчёт количества программ, с помощью которых можно получить 45, ведь таблица значительно уменьшилась.

    • Следует отметить, что первой командой системы команд исполнителя ("умножить на 2") можно было пренебречь изначально и не описывать никакие "возможные следствия", вызванные ею. Дело в том, что все команды исполнителя реализуют только умножение, но нельзя из нечётного числа получить нечётное, если в цепочке последовательных произведений существует хотя бы одно умножение на чётное число! Таким образом, в условии задачи предоставлена информация об одной команде, воспользоваться которой не представляется возможным. Эта информация явно является лишней.

Само начальное число можно получить единственной программой, — пустой (по Утверждению 1 о подсчёте числа маршрутов, см. Теоретическое введение). Поэтому в первом столбце таблицы рядом с первым "очередным числом" поставим 1:

Количество программОчередное числоВозможные следствия
139, 15
 945
 1545
 45 

Следующее "очередное число" (9) встречается во всех строках третьего столбца таблицы всего один раз, притом в той строке, в которой ячейка первого столбца содержит 1 (ниже соответствующие числа показаны белым цветом). Следовательно, число 9 можно получить только одним способом (одной программой):

Количество программОчередное числоВозможные следствия
139, 15
1945
 1545
 45 

Число 15, как и предыдущее, можно найти в третьем столбце только один раз, к тому же в строке, в которой первая ячейка содержит 1:

Количество программОчередное числоВозможные следствия
139, 15
1945
11545
 45 

А вот 45 встречается в двух разных строках третьего столбца; при каждом упоминании этого числа крайняя левая ячейка соответствующих строк таблицы содержит единицу, значит, конечное число может быть получено двумя разными способами:

Количество программОчередное числоВозможные следствия
139, 15
1945
11545
245 

Оказалось, что конечное число 45 можно получить двумя различными программами. Таким образом…
число 45 из числа 3 последовательным умножением на (два), три или пять любого из промежуточных результатов можно получить двумя разными способами; столько же различных программ существует для описанного в условии задачи исполнителя.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика