Обрабатываемые объекты

Код ОГЭ: 1.3.5. Обрабатываемые объекты: цепочки символов, числа, списки, деревья

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

К базовым абстрактным структурам данных, которые используются в информатике, относятся:

• целые и вещественные числа,
• символы,
• логические значения.

Для их обработки в языках программирования существуют соответствующие типы данных. Для хранения данных создаются переменные. Конкретные данные выступают в качестве значения переменной. Каждая переменная однозначно определяется своим именем (идентификатором). Тип данных, к которому относится переменная, говорит о том, какие действия можно производить над хранящимися в переменной данными.

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

• каким образом эта структура организована (логическая организация структуры) — какие более элементарные объекты входят в ее состав и какие операции можно над ними выполнять;
• перечень операций, которые можно выполнять над структурой в целом.

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

Таким образом, для объединения базовых структур в составную необходимо указать правила доступа к отдельным элементам этой структуры и операции над структурой в целом.

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

Более сложные структуры программисту предстоит создавать в программах самостоятельно, используя базовые структуры данных. Обычно их размер изменяется в ходе работы программы. Такие структуры называются динамическими. К ним обычно относят списки, деревья (графы) и др.

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

Цепочки символов

Пример 1.
Имеется некоторый алгоритм, который преобразует одну цепочку символов в другую по таким правилам: вычисляется длина исходной цепочки; значение суммы приписывается в конец этой цепочки. Затем в полученной цепочке каждая цифра, кроме 0, заменяется меньшей на единицу (9 заменяется на 8, 8 — на 7 и т. д.). Полученная последовательность символов записывается в обратном порядке.

Получившаяся цепочка символов и есть результат работы алгоритма. Например, если первоначально имелась цепочка символов 9ВАЛ, то результатом работы алгоритма будет 3ЛАВ8.

Какая последовательность символов получится, если применить к исходной цепочке ALL4U этот алгоритм дважды (то есть сначала применить алгоритм к исходной цепочке, а затем применить его к полученному результату)?

Решение. Выполним этот алгоритм дважды по шагам:

• 1) Вычислим длину цепочки: 5 символов.
• 2) Припишем длину в конец: ALL4U5.
• 3) Заменим цифры на меньшие (5 — на 4, 4 — на 3): ALL3U4.
• 4) Перепишем цепочку в обратном порядке: 4U3LLA.

Применим алгоритм второй раз:

• 5) Вычислим длину цепочки: 6 символов.
• 6) Припишем длину в конец: 4U3LLA6.
• 7) Заменим цифры на меньшие (6 — на 5, 4 — на 3, 3 — на 2): 3U2LLA5.
• 8) Перепишем цепочку в обратном порядке: 5ALL2U3.

Ответ: 5ALL2U3.

Списки

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

Типовые операции над элементами списка:

• получение доступа к определенному узлу (обход списка);
• добавление узла перед или после указанного элемента;
• удаление заданного узла;
• поиск заданного элемента;
• объединение нескольких списков в один;
• разбиение одного списка на несколько списков;
• копирование списка и др.

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

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

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

У некоторых видов списков добавление, удаление и доступ к значениям элементов всегда осуществляются только в крайних узлах (первом или последнем). К ним относятся стеки и очереди.

Стек — разновидность списка, в котором все включения и исключения узлов (и как правило, всякий доступ) производятся только на одном его конце. Этот концевой элемент называется вершиной стека. Иногда стек называют списком LIFO (Last In — First Out — последним вошел, первым вышел).

Механизм стека напоминает железнодорожный тупик, из которого первым может выехать только поезд, въехавший в него последним.

Очередь — разновидность списка, в котором все включения элементов производятся на одном его конце, а удаление узлов (и обычно всякий доступ) — на другом. Эти узлы называются началом и концом очереди. Иногда очередь называют списком FIFO (First In — First Out — первым вошел, первым вышел).

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

Деревья

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

• а) корни поддеревьев являются потомками корня всего дерева;
• б) множества элементов поддеревьев не пересекаются друг с другом.

Узлы, которые не имеют ни одного потомка, называются листьями (или концевыми узлами).

Таким образом, каждый узел дерева является корнем некоторого поддерева, которое содержится в дереве, или листом. Образуется иерархическая структура узлов: все элементы связаны между собой отношениями вида «предок» — «потомок».

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

Типовые операции над элементами дерева:

• добавление элемента в дерево,
• удаление элемента из дерева,
• обход дерева,
• поиск элемента в дереве.

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

Решение. Построим дерево решения задачи. В качестве корня дерева примем стартовый пункт маршрута — Г. Из него существует только один путь — в пункт Б длиной 1. Добавим в дерево узел, подпишем его. Соединим оба узла линией (ребром) и припишем ему расстояние от Г до Б.

К узлу Б добавим поддерево, содержащее узлы всех доступных из Б населенных пунктов — А, В и К. Соединим эти узлы с Б и припишем каждому ребру суммарное расстояние от начала маршрута (пункта Г) до соответствующего пункта.

Для каждого из полученных листов дерева продолжим рассмотрение возможных маршрутов. Начнем с узла В, поскольку путь до него — самый короткий. Из пункта В достижим только пункт Д, добавим узел в дерево и рассчитаем расстояние до него (3 + 8 = 11). Достигнута конечная цель маршрута, но он может оказаться не самым коротким. Поэтому продолжим построение дерева но будем обрывать его, как только на очередном пути будет получено расстояние больше найденного (>11).

Из пункта А достижимы два других пункта — Д и К. Расстояние до Д больше предыдущего, поэтому по–прежнему будем сравнивать длины всех маршрутов с 11. Расстояние до К (12) уже превышает эту величину, следовательно, эту ветвь дерева обрываем. Аналогично с поддеревом узла К — расстояние до доступного пункта А больше 11.

В результате получен самый короткий маршрут от Г до Д (длиной 11) — ГБВД.

Ответ: ГБВД.

Пример 3.
У исполнителя Калькулятор в системе команд имеются команды:
1. прибавить 1
2. умножить на 3

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

прибавить 1; прибавить 1; умножить на 3; умножить на 3
3 + 1 = 4;   4 + 1 = 5;   5 х 3 = 15;   15 х 3 = 45.

Требуется записать последовательность номеров команд, чтобы получить результат 36 из числа 2 не более чем за 4 шага.

Решение. Построим дерево поиска решений для обратной задачи — получения числа 2 из числа 36 с помощью двух обратных команд: разделить на 3; вычесть 1. Такой способ значительно эффективнее решения прямой задачи.

Корнем дерева будем считать узел с исходным числом 36. К нему можно применить одну из двух возможных операций — поэтому из корневого узла будет исходить два ребра. Поскольку не каждое число возможно разделить на 3, то некоторые узлы дерева будут иметь только одно ребро — для операции вычитания. Узлы, полученные вычитанием, будем располагать в левой ветви; узлы, полученные делением, — в правой ветви. Каждому ребру припишем соответствующую операцию.

Поскольку по условию можно использовать для преобразований не более 4–х шагов, после 5–го уровня прекратим добавление узлов к дереву.

В итоге видим, что число 2 может быть получено только на одном пути (на рисунке он выделен жирной линией). Выпишем команды, приведшие к решению обратной задачи: делить на 3; делить на 3; вычесть 1; вычесть 1. Для решения прямой задачи следует выписать исходные команды в противоположном порядке: прибавить 1; прибавить 1; умножить на 3; умножить на 3. Номера этих команд: 1122.
Ответ: 1122.

Конспект урока по информатике «Обрабатываемые объекты».

Вернуться к Списку конспектов по информатике.