В мир информатики # 100 (16–31 декабря).
Задачник

Ответы, решения, разъяснения

(“В мир информатики” № 91 / “Информатика” № 9/2007)

1. Статья “Машина для расшифровки… из бумаги”

Напомним, что в статье были предложены два задания для самостоятельной работы.

1. Словом НУЛТХСЁУГИЛВ зашифровано слово КРИПТОГРАФИЯ — наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения.

2. Во втором задании предлагалось расшифровать четверостишие Омара Хайяма.

Ответы прислал один :( читатель — Ивановский Леонид, г. Ярославль, школа № 33, учитель Ярцева О.В. Но этому есть объяснение — статья была опубликована в майском номере нашей газеты, когда у читателей началась подготовка к переводным и выпускным экзаменам, а у многих появилось “каникулярное” настроение :). Благодаря Леонида и учитывая, что задание было интересным, редакция решила еще раз повторить его. Итак, зашифрованное четверостишие:

РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ,

ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ:

ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ

В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.

Предлагаем читателям расшифровать его и прислать ответ в редакцию.

“Машина для расшифровки” показана на рисунке ниже и описана в указанном номере нашей газеты.

В заключение заметим, что Гордиенко Евгений, средняя школа села Гилевка Алтайского края, учитель Збарах В.Ф., разработал программу на языке Паскаль, позволяющую найти величину сдвига, с использованием которого осуществлялось шифрование методом Цезаря, а затем осуществляющую расшифровку заданного текста.

2. Статья “Две задачи”

1. Задача “Убывающий факториал”

Напомним, что предлагалось определить так называемые “убывающие факториалы” заданного числа — убывающий факториал порядка n числа a (обозначается (a)_n) равен произведению:

Начнем с решения средствами электронной таблицы Microsoft Excel:

Прежде всего можем записать значение в ячейке D2 — его лучше получить по формуле =B2 (как указывалось в статье, при n = 1: (a)n = a – 0 = a).

Далее, проанализировав приведенную формулу расчета убывающего факториала, можно установить, что (a)_n = (a)_n-1 * (a – (n – 1)). Значит, в ячейку D3 можно записать формулу

=D2 * ($B$2 –(C3 –1)),

которую затем распространить (скопировать) на остальные ячейки диапазона D3:D10.

При таком оформлении листа можно получать обратные факториалы и для других значений а:

Программа на школьном алгоритмическом языке, вычисляющая убывающий факториал для заданных значений a и n, может быть оформлена следующим образом:

алг Обратный_факториал

нач цел a, n, обр_факт, i

вывод нс, "Задайте значение а"

ввод a

вывод нс, "Задайте значение n"

ввод n

обр_факт := 1 |При n = 0 (см. статью)

нц для i от 1 до n

¦ обр_факт := обр_факт * (a - (i - 1))

кц

вывод нс, "Обратный факториал числа"

вывод "равен", обр_факт

кон

2. Задача “Определение числа сочетаний с использованием рекурсии”

В задаче речь шла об определении числа сочетаний из n элементов по m () с учетом того, что

Из приведенной зависимости следует, что для определения может быть использован прием, который в программировании называют “рекурсией” [1]. Рекурсивная (использующая саму себя как вспомогательную) функция для расчета имеет вид:

алг цел С(арг цел n, m)

нач

если m = 0

то

|Значение функции (см. статью)

знач := 1

иначе

если n = m

то

знач := 1

иначе

|Рекурсивный вызов функции С

знач := С(n - 1, m - 1) + С(n - 1, m)

все

все

кон

Примечание. При m = 0: = 1 — это так называемый “сингулярный (от французского singulier — единичный, особый) случай”.

Основная часть программы выглядит так:

алг Число_сочетаний

нач цел m, n, C

вывод нс, "Задайте значение n"

ввод n

вывод нс, "Задайте значение m"

ввод m

вывод нс, "Число сочетаний из "

вывод n, " по ", m, " равно ", C(n, m)

кон

Литература

1. Рекурсия. / “В мир информатики” № 5 (“Информатика” № 37/2003).

Решения рассмотренных задач прислали (уже в этом учебном году):

— Аствацатурян Эдуард, средняя школа поселка Новопетровский Московской обл., учитель Иванова М.Н.;

— Баженов Василий и Баженов Михаил, средняя школа села Горелово Тамбовской обл., учитель Шитова Л.А.;

— Деминцев Борис, средняя школа села Сердар, Республика Марий Эл, учитель Чернова Л.И.;

— Юргин Андрей, средняя школа села Кубайка Красноярского края, учитель Чудов Н.А.

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