Промежуточное условие
ИнфоКонсалтинг
Образовательный сервис


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

24.08.2017 Поздравляем учителей, преподавателей, учащихся и их родителей с началом нового учебного года! Пусть он окажется успешным и даст много полезных и нужных знаний.

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

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

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

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

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

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

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

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

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

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


"Промежуточное условие"


Payeer

"Промежуточное условие"

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

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

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

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

Сколько есть программ, которые число 3 преобразуют в число 84 так, чтобы в процессе выполнения любой из них на экране появлялось число 24 в качестве промежуточного результата?

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


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

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

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

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

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

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

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

В то же время выведенные только что числа являются промежуточными результатами для последующих вычислений, потому они должны быть занесены по-отдельности во второй столбец, — в порядке возрастания:

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

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

Однако заметим, что любая последовательность осуществления указанных в условии действий должна приводить к вычислению определённого промежуточного результата (24). Поэтому разделим всю работу по построению таблицы на два этапа. На первом этапе будем считать конечным число 24 (а не 84) и применять правила, сформулированные в предыдущем абзаце, относительно конечного числа 24. Второй же этап предполагает продолжение построения таблицы до тех пор, пока в её столбце "Очередное число" не появится конечное число, заданное по условию (84).

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

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

Внесём в столбец "Очередное число" и следующее по возрастанию 15 (из последнего столбца), а также укажем "возможные следствия" из него:

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

Как видно, единственным "возможным следствием" числа 15 является 24, которое получается увеличением его на 9. Действительно, если умножить 15 на два, то получится число, превосходящее 24, а а на первом этапе построения таблицы мы договорились считать конечным именно требуемый к получению промежуточный результат!

Внесём в таблицу два оставшихся значения третьего столбца, обнаружив, что "возможных следствий" они не имеют:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224, 21
 1524
 21 
 24 

Число 24 — конечное по требованию первого этапа построения таблицы, поэтому естественно, что его следствия в третьем столбце пока не появились. А то обстоятельство, что следствия отсутствуют у предыдущего "очередного числа", указывает на необходимость его удаления из всех столбцов таблицы:

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

Теперь из числа 12 есть только одно "возможное следствие".

Тем временем, первый этап построения таблицы завершён и теперь можно строить её, пока "очередным числом" не получим конечное по условию 84. Начиная второй этап построения таблицы, запишем все "возможные следствия" числа 24:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33

"Сделаем" число 33 "очередным" и покажем все "возможные следствия" из него:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42

Следующие "очередные числа" — 42 и 48:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284, 51
 4857

Как видно, из 48 можно получить лишь одно другое число, поскольку ещё одно его следствие (результат умножения на два) явно превосходит конечное 84. Для каждого следующего "очередного числа", за исключением, разумеется, конечного, также можно будет определить лишь одно следствие.

Заполним таблицу до конца, рассуждая по аналогии, завершив тем самым второй этап её построения:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284, 51
 4857
 5160
 5766
 6069
 6675
 6978
 7584
 78 
 84 

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

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284, 51
 4857
 5160
 5766
 6069
 6675
 69 
 7584
 84 

Теперь ни одного следствия нет и из числа 69. Удаляем его тоже:

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284, 51
 4857
 5160
 5766
 60 
 6675
 7584
 84 

И 60…

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284, 51
 4857
 51 
 5766
 6675
 7584
 84 

И 51 (тогда из "очередного числа" 42 будет лишь одно "возможное следствие"):

Количество программОчередное числоВозможные следствия
 36, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

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

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

Количество программОчередное числоВозможные следствия
136, 12
 612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

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

Количество программОчередное числоВозможные следствия
136, 12
1612, 15
 1224
 1524
 2448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

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

Количество программОчередное числоВозможные следствия
136, 12
1612, 15
21224
 1524
 2448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

Число 15 упоминается в третьем столбце единожды, причём в строке, где "количество программ" равно единице:

Количество программОчередное числоВозможные следствия
136, 12
1612, 15
21224
11524
 2448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

А 24 — два раза, причём в строках, в которых "количество программ" равно 2 и 1. Значит, число 24 можно получить тремя несовпадающими программами:

Количество программОчередное числоВозможные следствия
136, 12
1612, 15
21224
11524
32448, 33
 3366, 42
 4284
 4857
 5766
 6675
 7584
 84 

Заполним первый столбец таблицы до конца аналогичным способом:

Количество программОчередное числоВозможные следствия
136, 12
1612, 15
21224
11524
32448, 33
33366, 42
34284
34857
35766
66675
67584
984 

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



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


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

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

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



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