Совпадающие следствия
ИнфоКонсалтинг
Образовательный сервис


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

02.10.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. умножь на 2,
3. возведи в квадрат.

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

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

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

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


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

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

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

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

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

Из этого числа можно вывести три других, однако совпадающих: прибавлением двойки получаем 4, умножением на два — 4, и возведением в квадрат — тоже 4! Несмотря на то, что все три числа равны друг другу, записать их в третий столбец нужно три раза, через запятую: это принципиально важно! Об особенностях заполнения столбца таблицы с аналогичным названием см. Теоретическое введение.

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

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

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

И для него определим все "возможные следствия":

Количество программОчередное числоВозможные следствия
 24, 4, 4
 46, 8, 16

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

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

Количество программОчередное числоВозможные следствия
 24, 4, 4
 46, 8, 16

Запишем во второй столбец ещё два "очередных числа" и "возможные следствия" из них:

Количество программОчередное числоВозможные следствия
 24, 4, 4
 46, 8, 16
 68, 12
 810, 16

Мы видим, что квадраты чисел 6 и 8 превосходят конечное число, поэтому записывать их в соответствующие строки третьего столбца не нужно.

А вот ещё два "очередных числа" теперь хорошо видны, определим значения и третьего столбца таблицы для них:

Количество программОчередное числоВозможные следствия
 24, 4, 4
 46, 8, 16
 68, 12
 810, 16
 1012
 1214

Начиная с числа 10, для любого "очередного числа" (кроме конечного) теперь можно определить не больше одного "возможного следствия", ведь уже и удвоенные значения оказываются велики относительно конечного числа.

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

Количество программОчередное числоВозможные следствия
 24, 4, 4
 46, 8, 16
 68, 12
 810, 16
 1012
 1214
 1416
 16 

Понятно, что из числа 16 нет никаких "возможных следствий".

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

Количество программОчередное числоВозможные следствия
124, 4, 4
 46, 8, 16
 68, 12
 810, 16
 1012
 1214
 1416
 16 

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

Количество программОчередное числоВозможные следствия
124, 4, 4
346, 8, 16
 68, 12
 810, 16
 1012
 1214
 1416
 16 

А вот с числом 6 ситуация проще: оно повторяется во всех строках третьего столбца таблицы единожды, притом в той строке, где первая ячейка содержит 3. Это означает, что число 6 тоже получается тремя разными способами:

Количество программОчередное числоВозможные следствия
124, 4, 4
346, 8, 16
368, 12
 810, 16
 1012
 1214
 1416
 16 

Число 8 повторяется во всех строках третьего столбца два раза, притом оба раза в тех строках, в которых ячейки первого столбца содержат число 3. Соответственно, число 8 можно получить из числа 4 тремя способами и из числа 6 тоже тремя способами, итого — шестью способами. Что и записываем в первый столбец рядом с числом 8:

Количество программОчередное числоВозможные следствия
124, 4, 4
346, 8, 16
368, 12
6810, 16
 1012
 1214
 1416
 16 

Следующее число 10 получается только из числа 8, которое, в свою очередь, получается, как мы только что рассчитали, с помощью шести разных программ. Значит, число 10 тоже получается с помощью шести разных программ:

Количество программОчередное числоВозможные следствия
124, 4, 4
346, 8, 16
368, 12
6810, 16
61012
 1214
 1416
 16 

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

Количество программОчередное числоВозможные следствия
124, 4, 4
346, 8, 16
368, 12
6810, 16
61012
91214
91416
1816 

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



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


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

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

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



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