Вопрос

Понятие алгоритма. Свойства и способы записи алгоритма. Исполнитель алгоритма. Система команд исполнителя.

Ответ

Понятие алгоритма.

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

Свойства и способы записи алгоритма

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

— вербальный, когда алгоритм описывается на человеческом языке;

— символьный, когда алгоритм описывается с помощью набора символов;

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

Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Внешний вид основных блоков, применяемых при написании блок схем, приведен на рисунке:

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

В алгоритмах линейной структуры действия выполняются последовательно одно за другим:

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

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

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

Алгоритм обладает следующими свойствами:

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

2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

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

Стр 1 из 3

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

Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.

Основными свойствами алгоритма являются:

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

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

3. Результативность(решение задачи, для которой разработан алгоритм должно быть достигнуто за конечное число шагов).

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

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

Основные алгоритмические структуры:

1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.

2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);

· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

3) Разветвляющий алгоритм –алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

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

Языки программирования, классификация языков программирования. Понятие о системе программирования.

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

Языки программирования – искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов).

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

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

Интерпретатор (каждая инструкция, вводимая в ПК, сразу же преобразуется в машинный код и выполняется);

Компилятор (в машинный код переводится только вся программа в целом).

Изначально программирование производилось с помощью машинных кодов. Машинный код представляет собой запись команд для компьютера в виде чисел, представленных в двоичной системе счисления.

Язык машинных кодов и язык Ассемблера относятся к языкам низкого уровня, т.е. уровня приближенного к машинной логике.

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

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

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

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

Пример.

program Primer; {вычисление суммы двух чисел}

x,y,s: integer;

WriteLn(‘Введите через пробел два числа ‘);

ReadLn(x,y);

s := x + y;

WriteLn(‘Сумма чисел равна ‘,s);

Оператор присваивания. Выражение, приоритеты в выражениях.

Оператор присваивания – основной оператор любого языка программирования. Общая форма записи оператора:

имя величины := выражение

Например, V:=A; или V:=A+1;

переменная := выражение;

левая_часть := правая_часть;

Оператор работает справа налево, то есть сначала вычисляется то, что записано в правой части, а затем результат записывается «в левую часть».

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

Как только в программе встречается переменная, для неё в памяти отводится место. Оператор присваивания помещает значение переменной или значение выражения в отведённое место.

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

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

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

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

— одноместный минус;

— операция NOT;

— операции типа умножения;

— операции типа сложения;

— операции сравнения (отношения).

Одноместный минус применим к операндам арифметического типа. Операция NOT– к операндам логических и целых типов. Если в одном выражении несколько операций одного приоритета, то они выполняются, начиная слева. Приоритеты можно изменить, поставив скобки. В логических выражениях необходимы скобки во избежание конфликта типа по приоритету.

Например, если в выражении … (X > 5) AND (Y > 10) … не поставить скобки, то будет синтаксическая ошибка, так как приоритет операции AND выше приоритета операций сравнения >.

операции типа умножения – это *, /, div, mod, and

операции типа сложения – это +, -, or, xor

операции сравнения – это <>, <, >, <=, >=, in

Сравнение строк символов выполняется слева направо посимвольно. Более короткие строки дополняются пробелами справа.

Оператор цикла с заранее известным количеством повторений

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

В общем виде инструкция for записывается следующим образом:

for счетчик := нач_знач to кон_знач do

// здесь инструкции, которые надо выполнить несколько раз

Переменная счетчик, выражение нач_знач и кон_знач должны быть целого типа.

Если в инструкции for вместо слова to записать downto, то поле очередного выполнения инструкций тела цикла значение счетчика будет не увеличиваться, а уменьшаться.

Текстовые.

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

var Имя_переменной: text;

где:

Имя_переменной – имя переменной, которая впоследствии будет связана с файлом;

text — соответствующий тип переменной.

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

Типизированные.

Типизированным называется файл, который состоит из однородных элементов, относящихся к одному и тому же типу. Такими элементами могут

быть переменные различных типов и массивы. Каждый элемент такого файла

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

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

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

его нельзя просматривать и редактировать с помощью обычного текстового редактора.

Для того, чтобы в типизированный файл можно было производить

запись или считывать из него информацию, его следует связать с помощью

процедуры assign с файловой переменной подобно тому, как мы это уже

делали с текстовыми файлами. Например, так:

assign (nab,‘D:\inf\nabor’);

В общем виде описание файловой переменной для типизированного файла выглядит следующим образом:

var Имя_переменной: file of Тип;

где:

Имя_переменной – имя переменной, связанной с типизированным

файлом;

file – служебное слово;

Тип – тип элементов, из которых состоит данный файл.

Подобно текстовым файлам, типизированные файлы открываются для чтения процедурой resetи для записи процедурой rewrite, а закрываются процедурой close.

Непосредственное чтение данных из файла производится с помощью следующего оператора:

read (Имя_переменной1, Имя_переменной2);

где:

Имя_переменной1 –имя файловой переменной;

Имя_переменной2 – имя обычной переменной, относящейся к тому же типу, что и элементы типизированного файла.

Запись в файл производится оператором:

write (Имя_переменной1, Имя_переменной2);

Операторы writeln и readln для записи и чтения в типизированном файле использовать нельзя, так как данный тип не содержит строк.

Процедура seek (Имя_переменной, п);

где:

seek – служебное слово, которое в переводе с англ. «искать»;

Имя_переменной – имя файловой переменной;

n – порядковый номер элемента в файле (нумерация начинается с нуля).

Если в ходе работы программы необходимо установить, какой элемент

файла является текущим, то для этого используется функция filepos.

Общий вид описания данной функции:

filepos(Имя_переменной): longint;

Аргументом данной функции является имя файловой переменной, а

значением – порядковый номер текущего элемента в файле.

Нетипизированные.

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

Описание нетипизированной файловой переменной имеет следующий общий вид:

var Имя_переменной: file;

где:

Имя_переменной – имя связываемой с нетипизированным файлом файловой переменной.

Связывание файловой переменной с файлом производится так же, как и

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

rewrite. Формат этих процедур также аналогичен формату других видов

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

Для непосредственной записи информации в нетипизированный файл используется оператор blockwrite.

Общий вид данного оператора следующий:

blockwrite (Имя_переменной1, Имя_переменной,n);

где:

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, из которой данные передаются в файл;

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

Чтение информации из файла производится оператором blockread.

Общий вид данного оператора:

blockread (Имя_переменной1, Имя_переменной2,n);

где:

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, в которую передаются данные из файла;

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

Стандартные модули Паскаля.

В Турбо Паскале имеется 8 стандартных модулей, в которых содержится множество различных типов, констант, процедур и функций. Этими модулями являются SYSTEM, DOS, CRT, GRAPH, OVERLAY, TURBO3, GRAPH3. Модули Паскаля GRAPH, TURBO 3, GRAPH 3 выделены в отдельные TPU -файлы, а остальные входят в состав библиотечного файла TURBO.TPL. Лишь один модуль Паскаля SYSTEM подключается к любой программе автоматически, все остальные становятся доступны только после указания их имен в списке подключаемых модулей.

Модуль Паскаля SYSTEM. В него входят все процедуры и функции стандартного Паскаля, а также встроенные процедуры и функции, которые не вошли в другие стандартные модули (например, INC , DEC , GETDIR и т.п.). Модуль Паскаля SYSTEM подключается к любой программе независимо от того, объявлен ли он в предложении USES или нет, поэтому его глобальные константы, переменные, процедуры и функции считаются встроенными в Турбо Паскаль.

Модуль Паскаля PRINTER делает доступным вывод текстов на матричный принтер. В нем определяется файловая переменная LST типа TEXT , которая связывается с логическим устройством PRN.

Модуль Паскаля CRT.В нем сосредоточены процедуры и функции, обеспечивающие управление текстовым режимом работы экрана. С его помощью можно перемещать курсор в любую точку экрана, менять цвет выводимых символов и фона, создавать окна. Кроме того, в данный модуль включены также процедуры «слепого» чтения клавиатуры и управления звуком.

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

Модуль Паскаля DOS. В модуле собраны процедуры и функции, открывающие доступ к средствам дисковой операционной системы MS — DOS .

Модуль Паскаля OVERLAY. Данный модуль необходим при разработке громоздких программ с перекрытиями. Турбо Паскаль обеспечивает создание программ, длина которых ограничивается лишь основной оперативной памятью. Операционная система MS — DOS оставляет программе около 580 Кбайт основной памяти. Память такого размера достаточна для большинства исполняемых программ, тем не менее, использование программ с перекрытиями снимает это ограничение.

Модули Паскаля TURBO 3 и GRAPH 3 введены для обеспечения совместимости с ранней версией системы Турбо Паскаль.

Структура модулей Паскаля:

Unit <имя_модуля>;
interface <интерфейсная часть>;
implementation < исполняемая часть >;
begin
<инициирующая часть>;
end.

Здесь UNIT – зарезервированное слово (единица); начинает заголовок модуля;

· <имя_модуля> — имя модуля (правильный идентификатор);

· INTERFACE – зарезервированное слово (интерфейс); начинает интерфейсную часть модуля;

· IMPLEMENTATION – зарезервированное слово (выполнение); начинает исполняемую часть модуля;

· BEGIN – зарезервированное слово; начинает инициирующую часть модуля; причем конструкция begin <инициирующая часть> необязательна;

· END – зарезервированное слово – признак конца модуля.

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

Компиляция модулей Паскаля.

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

При компиляции модуля или основной программы в режиме COMPILE все, упоминаемые в предложении USES модули, должны быть предварительно откомпилированы, и результаты компиляции должны быть помещены в одноименные файлы с расширением TPU (от англ. Turbo Pascal Unit). Файл с расширением TPU создается автоматически при компиляции модуля Паскаля.

В режиме MAKE компилятор проверяет наличие TPU -файлов для каждого объявленного модуля. Если какой-либо файл не найден, система ищет одноименный файл с расширением PAS , т.е. файл с исходным текстом модуля Паскаля. Если таковой файл найден, система приступает к его компиляции. Кроме того, в этом режиме система следит за возможными изменениями исходного текста любого используемого модуля. Если в PAS -файл внесены изменения, то независимо от того, есть ли в каталоге соответствующий TPU -файл или нет, система откомпилирует его перед компиляцией основной программы. Более того, если изменения внесены в интерфейсную часть, то будут откомпилированы все другие модули, обращающиеся к нему. Режим MAKE существенно облегчает процесс разработки крупных программ с множеством модулей Паскаля: программист избавляется от необходимости следить за соответствием TPU -файлов их исходному тексту, т.к. система делает это автоматически.

В режиме BUILD существующие TPU -файлы игнорируются, система пытается отыскать и откомпилировать соответствующие PAS — файлы для каждого модуля Паскаля. После компиляции можно быть уверенным, что учтены все сделанные в текстах модулей Паскаля исправления и изменения.

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

Метод бинарного поиска

В случае, если массив упорядочен, то применяется метод бинарного поиска.

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива;

· Если образец равен среднему элементу, то задача решена.

· Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz) и за новое значение verh принимается sred+1, а значение niz не меняется.

· Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1) и за новое значение niz принимается sred-1, а значение verh не меняется.

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz – verh)/2+verh вычисляется новое значение sred и поиск продолжается.

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

Сортировка массива

Под сортировкой массива подразумевается процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке.

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

Сортировка методом обмена

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

Типизированные указатели

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

Указатель, как и любая другая переменная программы, должен быть объявлен в разделе объявления переменных.

В общем виде объявление типизированного указателя выглядит след образом:

Имя_указателя: ^Тип;

где:

Имя_указателя – имя переменноц-указателя;

Тип – тип переменной, на которую указывает переменная-указатель;

Значок ^ показывает, что объявляемая переменная является указателем.

Нетипизированные указатели

Чтобы хранить указатели, вам требуется переменная-указатель, а для создания переменной-указателя вам необходим ссылочный тип (или тип «указатель»). Простейшим ссылочным типом является стандартный тип с именем Pointer. Переменная типа Pointer — это общий (нетипизированный) указатель, то есть, просто адрес. Он не содержит информации о том, на что он указывает.

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

Списки

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

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

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

Упорядоченный список

Как правило, списки упорядочены. Порядок следования элементов в списке определяется содержимым одного из полей.

Удаление элемента из списка

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

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

Очереди.

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

Например, пусть у нас есть очередь из трех элементов А,В,С, в которую первым был помещен элемент А, затем — элемент В, а последним — элемент С. После удаления элемента А первым элементом очереди будет элемент В. При этом элемент А остался в массиве на своем месте, но его уже нет в очереди, так как указатель начала очереди указывает на элемент В, т. е. следующий элемент массива. Если мы добавим в очередь новый элемент D, то он будет помещен в конец очереди, определяемый указателем конца. Очередь, в которой нет ни одного элемента, называется пустой. В этом случае оба указателя показывают на одно и то же место. Операции над очередями: Init — создает пустую очередь; Empty — возвращает значение true, если очередь пуста, и false в противном случае; Insert — добавляет элемент в конец очереди; Remove — удаляет элемент из начала очереди.

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

Бинарное дерево должно реализовывать следующие операции:

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

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

Получение значения текущего элемента

Поиск заданного элемента: если искомый элемент находится в дереве, то возвращается указатель на него, в противном случае возвращается nil, сигнализирующий о неуспехе поиска значения

Удаление узла из дерева

Уничтожение бинарного дерева

Основные понятия объектно-ориентированного программирования: наследование, полиморфизм, инкапсуляция.

Объектно-ориентированное программирование (ООП) – это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира, его поведение.

Язык Object Pascal, поддерживая концепцию объектно-ориентированного программирования, дает возможность определять классы.

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

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

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

В Object Pascal ограничение доступа к полям объекта реализуется при помощи свойств объекта. Свойство объекта характеризуется полем, сохраняющим значение свойства, и двумя методами, обеспечивающими доступ к полю свойства. Метод установки значения свойства называется методом записи свойства (write), а метод получения значения свойства – методом чтения свойства (read).

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

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

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

Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.

Основными свойствами алгоритма являются:

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

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

3. Результативность(решение задачи, для которой разработан алгоритм должно быть достигнуто за конечное число шагов).

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

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

Основные алгоритмические структуры:

1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.

2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);

· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

3) Разветвляющий алгоритм –алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

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

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

1. СЛОВЕСНАЯ ЗАПИСЬ АЛГОРИТМОВ

Словесная форма записей алгоритмов на естественных языках применяется при ориентации на исполнителя-человека. Команды алгоритма нумеруют для возможности ссылки на них. Форма записи команд не формализуется. В командах помимо слов могут использоваться специальные символы и формулы.

2. ГРАФИЧЕСКИЕ СХЕМЫ АЛГОРИТМОВ

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

Наименование Обозначение Функции
1. Ввод-вывод Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод)
2.Процесс Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных
3. Решение Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий
4. Пуск Начало выполнения программы
5. Останов Конец выполнения программы

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

3. ПСЕВДОКОД

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

алгоритм ЕВКЛИД ;

Начало

пока первое число не равно второму числу

Начало

если первое число больше второго числа

то заменить первое число на разность первого и

второго чисел

иначе заменить второе число на разность второго

и первого чисел

Все

взять первое число в качестве ответа;

Конец

Конец

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

4. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

Для записи алгоритмов, ориентированных на исполнителя-автомат, которым является компьютер, были разработаны формальные языки, получившие наименование ЯЗЫКИ ПРОГРАММИРОВАНИЯ.

2. Алгоритм. Свойства алгоритмов. Способы записи алгоритмов. Основные структуры алгоритмов.

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Основными свойствами алгоритма являются:

  1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
  2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
  3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
  4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

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

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

Блок-схемой называется графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются ГОСТами.

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

  • линейный;
  • ветвящийся;
  • циклический.

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

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

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

Выделяют три наиболее распространенные на практике способа записи алгоритмов:

  • словесный (запись на естественном языке);
  • графический (запись с использованием графических символов);
  • программный (тексты на языках программирования).

Словесный способ – способ записи алгоритма на естественном языке. Данный способ очень удобен, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить логику действий.

В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника

S=a*b,

где S – площадь прямоугольника; а, b – длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

Словестный способ записи алгоритма выглядит так:

  • Начало алгоритма.
  • Задать численное значение стороны a.
  • Задать численное значение стороны b.
  • Вычислить площадь S прямоугольника по формуле S=a*b.
  • Вывести результат вычислений.
  • Конец алгоритма.

Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.

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

Название символа Обозначение
и пример заполнения
Пояснения
Пуск-останов Начало, завершение алгоритма или подпрограммы
Ввод-вывод данных Ввод исходных данных или вывод результатов
Процесс Внутри прямоугольника записывается действие, например, расчетная формула
Решение Проверка условия, в зависимости от которого меняется направление выполнения алгоритма
Модификация Организация цикла
Предопределенный процесс Использование ранее созданных подпрограмм
Пояснения

Пояснения:

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

  • блок Решение обозначает проверку условия

Если условие выполняется, то есть a>b, то следующим выполняется действие по стрелке «Да». Если условие не выполняется, то осуществляется переход по стрелке «Нет».

  • блок Модификация используется для организации циклических (повторяющихся) действий.

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

устройство ввода или вывода дисплей магнитный диск

В качестве примера графического способа описания алгоритмов с помощью блок-схем запишем алгоритм нахождения площади прямоугольника:

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

Последовательность выполнения сверху вниз и слева направо принята за основную.

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

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

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

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

Алгоритмы

Выделяют три наиболее распространенные на практике способа записи алгоритмов:

  • словесный (запись на естественном языке);
  • графический (запись с использованием графических символов);
  • программный (тексты на языках программирования).

Словесный способ записи алгоритмов

Словесный способ – способ записи алгоритма на естественном языке. Данный способ очень удобен, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить логику действий.

В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника

S=a*b,

где S – площадь прямоугольника; а, b – длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

Словестный способ записи алгоритма выглядит так:

  • Начало алгоритма.
  • Задать численное значение стороны a.
  • Задать численное значение стороны b.
  • Вычислить площадь S прямоугольника по формуле S=a*b.
  • Вывести результат вычислений.
  • Конец алгоритма.

Графический способ описания алгоритмов

Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.

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

Название символа Обозначение
и пример заполнения
Пояснения
Пуск-останов Начало, завершение алгоритма или подпрограммы
Ввод-вывод данных Ввод исходных данных или вывод результатов
Процесс Внутри прямоугольника записывается действие, например, расчетная формула
Решение Проверка условия, в зависимости от которого меняется направление выполнения алгоритма
Модификация Организация цикла
Предопределенный процесс Использование ранее созданных подпрограмм
Пояснения

Пояснения:

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

  • блок Решение обозначает проверку условия

Если условие выполняется, то есть a>b, то следующим выполняется действие по стрелке «Да». Если условие не выполняется, то осуществляется переход по стрелке «Нет».

  • блок Модификация используется для организации циклических (повторяющихся) действий.

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

В качестве примера графического способа описания алгоритмов с помощью блок-схем запишем алгоритм нахождения площади прямоугольника:

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

Последовательность выполнения сверху вниз и слева направо принята за основную.

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

Программный способ записи алгоритмов

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

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

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

Запись алгоритма на языке программирования называется компьютерной программой.

Рубрики: Дети

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *