Несколько конечных состояний
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


"Несколько конечных состояний"




"Несколько конечных состояний"

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

Текст задачи. У некоторого исполнителя есть две команды, которым присвоены номера:
1. вычти 4,
2. вычисли минимальное целое, не меньшее значения квадратного корня.

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

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

Сколько есть программ, которые позволяют преобразовать число 48 в число, не превосходящее 5 и вычисленное при этом в первый раз?

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


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

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

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

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

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

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

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

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

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

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

Теперь во второй столбец можно вписать и число 40, а в третий — его "возможные следствия":

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

Аналогично заполним ещё несколько строк таблицы:

Количество программОчередное числоВозможные следствия
 4844, 7
 4440, 7
 4036, 7
 3632, 6
 3228, 6
 2824, 6
 2420, 5
 2016, 5
 1612, 4
 128, 4
 84, 3
 73, 3

Мы добрались, наконец, до вторых следственных значений из начинающих таблицу "очередных чисел". Закончим её заполнение:

Количество программОчередное числоВозможные следствия
 4844, 7
 4440, 7
 4036, 7
 3632, 6
 3228, 6
 2824, 6
 2420, 5
 2016, 5
 1612, 4
 128, 4
 84, 3
 73, 3
 62, 3
 5 
 4 
 3 
 2 

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

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

Количество программОчередное числоВозможные следствия
14844, 7
 4440, 7
 4036, 7
 3632, 6
 3228, 6
 2824, 6
 2420, 5
 2016, 5
 1612, 4
 128, 4
 84, 3
 73, 3
 62, 3
 5 
 4 
 3 
 2 

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

Количество программОчередное числоВозможные следствия
14844, 7
14440, 7
 4036, 7
 3632, 6
 3228, 6
 2824, 6
 2420, 5
 2016, 5
 1612, 4
 128, 4
 84, 3
 73, 3
 62, 3
 5 
 4 
 3 
 2 

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

Количество программОчередное числоВозможные следствия
14844, 7
14440, 7
14036, 7
13632, 6
13228, 6
12824, 6
12420, 5
12016, 5
11612, 4
1128, 4
184, 3
 73, 3
 62, 3
 5 
 4 
 3 
 2 

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

Количество программОчередное числоВозможные следствия
14844, 7
14440, 7
14036, 7
13632, 6
13228, 6
12824, 6
12420, 5
12016, 5
11612, 4
1128, 4
184, 3
373, 3
 62, 3
 5 
 4 
 3 
 2 

По аналогии можно посчитать "количество программ" для оставшихся "очередных чисел":

Количество программОчередное числоВозможные следствия
14844, 7
14440, 7
14036, 7
13632, 6
13228, 6
12824, 6
12420, 5
12016, 5
11612, 4
1128, 4
184, 3
373, 3
362, 3
25 
34 
103 
32 

Суммарное количество программ, которыми можно получить все взятые вместе конечные числа — 18. Таким образом…
числа 2, 3, 4 или 5 из числа 48 последовательными уменьшением на четыре или извлечением квадратного корня с последующим округлением результата до целого значения с избытком можно получить 18 разными способами; столько же программ существует для описанного в условии задачи исполнителя.



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


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

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

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



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