textarchive.ru

Главная > Документ


Примеры рекурсивной обработки массива

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

Таким образом, любая задача по обработке массива может быть решена с помощью рекурсии. Мы возьмем в качестве примера ту же самую задачу сортировки массива, которая рассматривалась выше для итерационного метода. Попутно окажется, что нам потребуется написать нахождение максимума, что также можно сделать рекурсивно5. Следовательно, в итоге у нас будет сразу два примера рекурсивных алгоритмов.

Рассмотрим возможную реализацию программы.

PROGRAM sort_rekurs(INPUT, OUTPUT);

CONST n = 10;

m: ARRAY [1..n] OF INTEGER =

(10,9,8,7,6,5,4,3,2,1);

FUNCTION ind_max(k: INTEGER): INTEGER;

VAR w: INTEGER;

BEGIN IF k > 1 THEN BEGIN w := ind_max(k - 1);

IF m[k] < m[w] THEN ind_max := w

ELSE ind_max := k

END

ELSE ind_max := 1

END;

PROCEDURE sort2(p: INTEGER);

VAR im,c: INTEGER;

BEGIN im := ind_max(p);

c := m[im]; m[im] := m[p]; m[p] := c;

FOR c := 1 TO n DO WRITE(m[c],' '); WRITELN;

IF p > 2 THEN sort2(p - 1)

END;

BEGIN sort2(n)

END.

Описание начнем с рассмотрения рекурсивной функции ind_max для нахождения индекса максимального элемента. Ее рекурсивная логика может быть сформулирована следующим образом. Решение задачи для массива из n элементов весьма трудоемко, поэтому его постепенно сводим к более простому: для n – 1, n – 2
и т.д. элементов (см. вызов ind_max(k-1), который и является рекурсивным вызовом функцией самой себя). Так поступаем до тех пор, пока ответ не станет тривиальным: в массиве из одного элемента индекс максимума равен индексу этого единственного элемента (в нашем случае 1). Далее производится “обратный ход” — зная текущее значение ind_max, соответствующее ему значение максимума сравниваем с текущим элементом массива, после чего индекс наибольшего из сравниваемых элементов запоминаем. Таким образом, отрабатывается последовательная цепочка рекурсивных вызовов и без всякого цикла организуется полный перебор всех элементов массива.

Примечание. Понимание механизма вызова процедур6 делает возможность реализации их “самовызова” абсолютно очевидной; даже просто зная о факте разрешения вызова из одной процедуры другой, можно предсказать существование рекурсивности. Главная же проблема рекурсии заключается в том, чтобы организованный рассматриваемым способом процесс каким-то образом завершался.

Теперь, рассматривая функцию ind_max как единое целое и не обращая внимания на ее внутреннюю логику, обсудим второй рекурсивный алгоритм — сортировку массива, описанную в рекурсивной процедуре sort2. Ее логика работы такова. В массиве размерности n находится максимальный элемент, и он меняется местами с последним. В результате самый последний элемент массива займет свое окончательное место и останется рассортировать массив уже меньшего размера, т.е. n – 1. Аналогичным образом задача последовательно решается для все меньшего и меньшего массива, пока не останется массив из одного элемента, в котором, естественно, сортировка уже не требуется: условие p > 2 предотвращает вызов sort2(1) и процесс рекурсии благополучно завершается.

Примечание. Имеющийся в sort2 цикл вывода массива на экран играет вспомогательную роль. Читатели при желании могут без труда самостоятельно оформить его в виде рекурсивной процедуры (печатаем первый элемент, а затем вызываем процедуру вывода оставшегося массива!), реализовав тем самым чисто рекурсивную программу без единого цикла.

Основная программа состоит из единственной строки sort2(n), которая запускает процесс сортировки, начиная с полного массива.

Примечание для учителей. Вполне возможно, что приведенное решение задачи для некоторых школ покажется слишком сложным. В этом случае вполне можно ограничиться рекурсивным решением ее части — нахождением положения максимума в массиве. Вообще сам факт наличия вопроса о рекурсии7 в тексте официальных “министерских” билетов для выпускных экзаменов в пору, когда слово “программирование” для многих методистов стало едва ли не ругательным, весьма наглядно демонстрирует тот идейный разброд, который внесла в содержание курса информатики энергичная борьба за наполнение школьного курса прикладными офисными технологиями!

Все обсуждавшиеся выше примеры рассматривали одномерные массивы данных. Они являются наиболее простыми и, кроме того, естественным образом согласуются с принципами организации памяти компьютера: согласно классическим идеям фоннеймановской архитектуры, память — это линейный массив пронумерованных ячеек. Следовательно, остается лишь получить формулу пересчета значений индексов в адреса ОЗУ и с элементами такого массива можно легко работать.

В математике, физике и некоторых других науках тем не менее широко используются и многомерные массивы. Поэтому такие структуры не могли не появиться в языках программирования. Фактически есть два способа определения многомерных массивов: непосредственный и создание сложной структуры. Мы ограничимся обсуждением двумерных массивов; обобщение для большей размерности делается аналогично. На языке Паскаль, например, эти два способа описания массивов выглядят так:

m1: ARRAY [1..3, 1..5] OF REAL;

m2: ARRAY [1..3] OF ARRAY [1..5] OF REAL;

Примечание. Обращение к элементам массивов m1 и m2 отличаются: они записываются как m1[i,j] и m2[i][j] соответственно.

В некоторых простых языках программирования типа Basic используется только традиционная математическая (“матричная”) форма представления массивов, а в языках с более развитыми средствами создания данных, в частности Паскале, допустимы обе формы.

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

С математической точки зрения для увеличения размерности массива достаточно формально приписать еще один индекс. Однако для реализации такой структуры в памяти компьютера потребуется как-то приспособить многомерную структуру данных к хранению в одномерной памяти. “За исключением языка Fortran, все языки хранят двумерные массивы как последовательности строк… Такое размещение вполне естественно, поскольку сохраняет идентичность двумерного массива и массива массивов”. [4] Приведенный рисунок поясняет идею формирования двумерного массива данных в “линейном” ОЗУ компьютера.

Учитывая, что все элементы массива однородны (имеют один и тот же тип и, следовательно, занимают одинаковое место в памяти), получить формулу пересчета индексов в требуемый адрес ОЗУ является несложной задачей. И хотя школьных знаний для этого вполне достаточно, мы не будем сейчас этим заниматься. Заметим лишь, что в 32-разрядных процессорах Intel специально предусмотрены аппаратные методы адресации, в которые заложены такие формулы для данных стандартной длины (1, 2, 4 и даже 8 байт), что существенно облегчает для программиста (или для компилятора) доступ к элементам массивов. Заинтересовавшиеся читатели могут познакомиться с формулами для масштабированной базово-индексной адресации (одномерные массивы) и для аналогичного метода со смещением (двумерные), например, по книге [5].

Литература

1. Примеры задач к билетам. Информатика, 2006, № 6, с. 3–16.

2. Примеры задач к билетам. Информатика и образование, 2006, № 3, с. 24–30.

3. Фридланд А.Я. Информатика и компьютерные технологии: Основные термины: Толковый словарь / А.Я. Фридланд, Л.С. Ханамирова, И.А. Фридланд. М.: ООО “Издательство Астрель”: ООО “Издательство АСТ”, 2003, 272 с.

4. Бен-Ари М. Языки программирования. Практический сравнительный анализ. М.: Мир, 2000, 366 с.

5. Гук М. Процессоры Intel: от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.

2. Изображение на бумажном носителе состоит из нескольких частей. Отсканировать части изображения и объединить их в одно растровое изображение. Отретушировать получившееся изображение и сохранить его в файле.

Решение данной задачи (после сканирования частей изображения) может быть выполнено в любом растровом графическом редакторе (в частности, в редакторе Paint). Для получения качественного итогового изображения рекомендуется воспользоваться редактором Adobe Photoshop.

Не будем здесь приводить детального описания решения задачи.

3. Определить информационный объем переданного сообщения за определенный период времени при заданной пропускной способности канала.

Пример. Модем передает сообщения со скоростью 14 400 бит в секунду. Изображение какого размера (в формате без сжатия) может передать модем за три минуты постоянной работы, если используется палитра из 65 тысяч цветов?

Решение. Предположим для определенности, что палитра составляет 65536 = 216 цветов. Тогда для кодирования информации об одной точке требуется
2 байта. 14 400 бит/с = 1800 байт/с. За 3 мин. = 180 с будет передано 180 х 1800 = 324 000 байт (316,4 Кб) изображения или информация о 162 000 точек изображения.

Варианты заданий

1. Информация по электронной почте через модем передается со скоростью 9600 бит/с. Сколько времени понадобится, чтобы передать по электронной почте субботний выпуск газеты “Комсомольская правда”, если ее объем 3 условных печатных листа (1 условный печатный лист газеты с иллюстрациями 512 Кб)?

2. В течение урока 12 учеников пишут диктант в 10 000 символов. Оцените, сколько минут понадобится, чтобы переслать поочередно работы всех учеников на ПК учителя при скорости пересылки в 9600 бит/с?

1 Действительно, для однократного вычисления по единственной не слишком сложной формуле обычно пользуются калькулятором, а не пишут программу.

2 В Паскале указаны граничные значения индекса (точнее говоря, тип данных ограничение, частным случаем которого как раз является диапазон целых чисел), в Си — количество элементов, в VBA — максимальное значение индекса (минимальное, как правило, равно 0, что упрощает расчеты с индексами, но есть оператор его установки в 1).

3 real, float и variant соответственно.

4 У автора, как у практика, большое сочувствие вызывает предлагаемая ученикам в образцах к билетам задача “написать и отладить программу ввода и сортировки… массива из 20 элементов”.

5 Авторы рекомендуют провести сравнение рекурсивного поиска положения максимума с написанной традиционным способом программой ind_max, приведенной выше.

6 Многие методисты охотно включают в программу школьного курса информатики изучение стека и других динамических структур данных; при этом ни один из них не упоминает, что именно этот самый стек, аппаратным образом организованный, лежит в основе механизма реализации вложенных процедур (и даже передачи им параметров!).

7 Рекурсию можно считать понятием третьего(!) уровня сложности в программировании: алгоритмические структуры — автономные процедуры и функции — особенности их “самовызова”.

Билет № 8

1. Основные понятия и операции формальной логики. Законы логики. Логические переменные. Логические выражения и их преобразования. Построение таблиц истинности логических выражений

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

Под логическимвысказыванием понимается любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Например, логическим высказыванием будет “Земля — третья планета от Солнца”, но не является таковым “Довольно морозная в этом году зима”.

Чаще на практике приходится иметь дело с высказывательнымиформами — повествовательными предложениями, прямо или косвенно содержащими переменные; высказывательная форма становится логическим высказыванием, если значения всех переменных, входящих в нее, заданы. Например, высказывательная форма “x кратно 5” при x = 34 ложна, а при x = 105 — истинна. В языках программирования высказывательные формы записываются в виде логических выражений.

Буквы, обозначающие переменные высказывания, называются высказывательнымипеременными (логическимипеременными).

Простые логические высказывания могут быть объединены в более сложные — составные — с использованием логическихопераций. Основными логическими операциями являются НЕ (отрицание, или инверсия), И (конъюнкция, или логическое умножение), ИЛИ (дизъюнкция, или логическое сложение).

Рассмотрим более подробно логические операции.

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

Операция инверсии(отрицания) выполняется над одним операндом (так в математике называются величины, над которыми выполняют ту или иную операцию). Общее правило, заложенное в построение таблицы истинности для этой операции, звучит так: отрицаниеизменяетзначениеоперанданапротивоположное.

Обозначение операции: A, .

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

В литературе операцию дизъюнкции обозначают по-разному: ИЛИ, . В языках программирования также имеется эта операция. В Pascal и Вasic она обозначается OR, в С/C++, JavaScript — ||, и т.д.

Логическим сложением эту операцию называют по той причине, что если заменить значение истина на 1, а ложь — на 0, то таблица истинности в определенной мере будет соответствовать таблице сложения в двоичной системе счисления. В действительности роль дизъюнкции в алгебре логики аналогична роли операции сложения в арифметике.

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

В литературе операцию конъюнкции обозначают по-разному: И, , & (достаточно часто в записи выражений знак конъюнкции пропускают по аналогии со знаком умножения в записи алгебраических выражений). В языках программирования также присутствует эта операция. В Pascal и Basic она обозначается AND, в С/C++, JavaScript — &&, и т.д.

Логическим же умножением эту операцию называют по той причине, что если заменить значение истина на 1, а ложь — на 0, то таблица истинности будет соответствовать таблице умножения в двоичной системе счисления.

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

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

Свойствалогическихопераций (или законы логики; знак “” обозначает “эквивалентно”, “тождественно истинно”):

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

Пример 1. Упростить выражение и убедиться, что результат равносилен исходному выражению.

(в записи выражения знак конъюнкции пропущен).

Преобразование выполним последовательно.

Рассмотрим вторую скобку: . По закону поглощения получаем Y.

В третьей скобке используем закон де Моргана: .

Таким образом, получили . Используя законы коммутативный, противоречия, а также правило , приходим к выводу, что выражение .

Таким образом, .

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

Пример 2. Доказать, что выражение является тавтологией1.

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

Проведем доказательство путем составления таблицы истинности для данного выражения:

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

Литература

1. Шауцукова Л.З. Информатика: Учебное пособие для 10–11-х классов общеобразовательных учреждений. 2-е изд., дораб. М.: Просвещение, 2002, 416 с.

2. Андреева Е.В. Математические основы информатики. Элективный курс: Учебное пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина. М.: БИНОМ. Лаборатория Знаний, 2005, 328 с.

3. Семакин И., Залогова Л., Русаков С., Шестакова Л. Информатика: учебник по базовому курсу. М.: Лаборатория Базовых Знаний, 1998.

4. Угринович Н. Информатика и информационные технологии. Учебное пособие для общеобразовательных учреждений. М.: БИНОМ, 2001, 464 с. (Введение в информатику, с. 13–16.)

5. .

1Тавтология — тождественно истинное выражение.

2. С помощью электронной таблицы вычислить значение функции, заданной рекуррентным соотношением

Пример. Получить в электронной таблице первые 15 значений функции n!

Решение. Зададим факториал рекуррентным соотношением: an = an-1•n, a1 = 1

Пусть столбец A хранит значения n, а столбец
B — n!. Тогда в ячейки A2:A16 занесем значения n от 1 до 15. В ячейку B2 поместим значение 1, а в ячейке B3 запишем формулу =B2 * A3, выражающую записанное рекуррентное соотношение; далее скопируем эту формулу во все последующие ячейки столбца и получим требуемый результат.

 

Варианты заданий

Получить в электронной таблице первые k значений последовательности (k задается учителем).

.

.3. Представить на языке программирования вычислительный алгоритм, записанный в виде блок-схемы. (Получить результат в виде значения переменной.)

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

Решение.

QBasic

B = 0 : C = 1

While B <> 11

C = C + B * C

B = B + 1

Wend;

PRINT C

Pascal

Var b, c: longint;

Begin

B := 0; C := 1;

While B <> 11 do

Begin

C := C + B * C;

B := B + 1

End;

Writeln(C)

End.

C++

#include <iostream.h>

void main()

{ long B, C;

B = 0; C = 1;

while (B != 11)

{ C = C + B * C;

B++; }

cout << C;

}

Результат вычислений: 39 916 800.

Вариантызаданий

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

1. Вывести значение переменной K для n = 12 981.

2. Вывести значение переменной P при k = 5.

3. Вывести значение переменной K для n = 12 981.

4. Какое количество членов ряда будет просуммировано при e = 10–2?

.



Скачать документ

Похожие документы:

  1. Примерные ответы на профильные билеты

    Документ
    Примерныеответынапрофильныебилеты Е.А. Еремин, А.П. Шестаков От авторов Уважаемые ... . М.: Энергия, 1973, 144 с. 5. Еремин Е.А., Шестаков А.П. Примерныеответынапримерныебилеты // Информатика, 2002, № 13 (350), с. 9–13 ...
  2. Профильное обучение

    Сценарий
    ... (Методическая консультация. Профильная школа). Профильное обучение: вопросы и ответы : [ответына некоторые актуальные вопросы] ... . Анализ существующего положения дел. Еремин Е. А. Примерныеответынапрофильныебилеты / Е. А. Еремин, А. П. Шестаков. ...
  3. Ответы на экзаменационные билеты по литературе 11 класс

    Экзаменационные билеты
    ... билетов полностью соответствует примерным экзаменационным билетам по литературе для образовательных учреждений, осуществивших переход напрофильное ...
  4. Примерные ответы на теоретические вопросы билетов профильный уровень билет № 1 понятие информации виды информации ее свойства классификации по различным основаниям проблема определения выбор способа представления информации в соответствии

    Документ
    Примерныеответына теоретические вопросы билетов. Профильный уровень Билет № 1 Понятие информации. Виды ... так, чтобы на них можно было ответить «да» или ... в Америке и мангустов — на острове Ямайка. Билет № 11 Информационные основы управления ...
  5. Примерные билеты по физике для сдачи экзамена по выбору выпускниками xi (xii) классов общеобразовательных учреждений российской федерации пояснительная записка

    Документ
    ... изучавших физику на базовом и напрофильном уровнях. Содержание билетов учитывает требования ... 2) плакаты и таблицы для ответовна теоретические вопросы, 3) непрограммируемый калькулятор ... именно статистические исследования? Примерныебилеты по физике для ...

Другие похожие документы..