Решение задачи C3 (2012 г.)
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


Решение задачи C3 на примере официальной демо-версии КИМ ЕГЭ 2012 г.


Payeer

Решение задачи C3 на примере официальной демо-версии КИМ ЕГЭ 2012 г.

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Во втором столбце числа повторяться не могут. Кроме того, записывать числа во второй столбец нужно всё-таки по порядку, иначе можно легко сбиться. Потому продолжение выглядит пока так:

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

И для числа 4 запишем "возможные следствия":

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

Следующие два последовательных числа — 5 и 6. Сразу рассчитаем для них значения третьего столбца:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18

Занесём во второй столбец число 7:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21

А теперь можно записать во второй столбец сразу два числа, 8 и 9:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27

Сейчас из таблицы видно, что очередным числом можно легко определить одно, — 10. Остановимся на его "возможных следствиях" подробнее.

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011

Мы видим, что единственным следствием, получаемым из числа 10, является 11. Действительно, второй возможный результат, число 30, получить, конечно, можно, но оно превосходит конечное число, определённое в задаче, а, значит, записывать его в таблицу не надо: ни во второй (потом), ни в третий (сейчас) её столбцы.

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

В данный момент во втором столбце таблицы "очередными числами" являются 11 и 12:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213

Продолжим заполнение таблицы. Внесём в её второй столбец число 13:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314

А теперь ещё два, — 14 и 15:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516

Рассуждая аналогично, достроим таблицу до конца. Она получит следующий вид:

Количество программОчередное числоВозможные следствия
 12, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

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

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

Количество программОчередное числоВозможные следствия
112, 3
 23, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

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

Количество программОчередное числоВозможные следствия
112, 3
123, 6
 34, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

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

Количество программОчередное числоВозможные следствия
112, 3
123, 6
234, 9
 45, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

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

Количество программОчередное числоВозможные следствия
112, 3
123, 6
234, 9
245, 12
 56, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

Число 5, кстати, тоже — с помощью двух разных программ:

Количество программОчередное числоВозможные следствия
112, 3
123, 6
234, 9
245, 12
256, 15
 67, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

А вот 6 является следствием числа 2, для получения которого возможно составить лишь одну программу, и числа 5, получаемого двумя разными способами. Итого имеются три различные программы, дающие возможность получить число 6:

Количество программОчередное числоВозможные следствия
112, 3
123, 6
234, 9
245, 12
256, 15
367, 18
 78, 21
 89, 24
 910, 27
 1011
 1112
 1213
 1314
 1415
 1516
 1617
 1718
 1819
 1920
 2021
 2122
 2223
 2324
 2425
 2526
 2627
 2728
 2829
 29 

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

Количество программОчередное числоВозможные следствия
112, 3
123, 6
234, 9
245, 12
256, 15
367, 18
378, 21
389, 24
5910, 27
51011
51112
71213
71314
71415
91516
91617
91718
121819
121920
122021
152122
152223
152324
182425
182526
182627
232728
232829
2329 

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



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


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

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

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



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