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

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

(общ.) Алгоритм – это система формальных правил однозначно приводящая к решению поставленной задачи.

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

Свойства:

А) Дискретность - алгоритм состоит из отдельных пунктов или шагов

Б) Определённость - каждый шаг алгоритма должен быть строго сформулирован.

(иметь точный смысл)

В) Связанность - на каждом следующем шаге используются результаты предыдущего.

Г) Конечность – алгоритм должен завершаться после конечного числа шагов

Д) Результативность – алгоритм должен приводить к получению конечных результатов

Е) Массовость – пригодность для решения широкого класса задач.

Ж) Эффективность – применение а. должно давать какой бы-то положительный временной результат (временной)

Способ записи:

А) Словесно-формульный

Б) Структурная схема и алгоритм (ССА)

В) Спец. языки (алгоритмические и псевдокоды)

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

Г) Графический способ

Линейные и разветвляющиеся алгоритмы. Cтруктурные схема алгоритмов. Правила выполнения.

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

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

Начало—ряд операторов—конец.

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

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

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

Циклы по числу повторений делятся на циклы с заданным числом повторений и итерационные.

ЦИКЛЫ

ЗАДАННОЕ ЧИСЛО ИТЕРАЦИОННЫЕ

СО СЧЁТЧИКОМ УПР. УСЛОВИЕМ

ПОСТ. УСЛОВИЕ ПРЕДУСЛОВИЕ

Общее замечание: вход только в начало цикла, а выход вследствие окончания цикла, оператором GOTO, процедурами прерхода и выхода, находящимся в теле цикла.

Циклические алгоритмы. Итерационные циклы. Вложенные циклы.

Циклы по числу повторений делятся на циклы с заданным числом повторений и итерационные.

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

Вложенные циклы – это, когда определённый цикл повторяется многократно в другом цикле охватывающем данный.

Массивы. Алгоритмы обработки массивов. Процедура BREAK

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

Пример: В[2] означает второй элемент массива В.

Пусть имеется некоторая последовательность величин 1, 2, 4, 8, 3. Все элементы этой последовательности имеют одно имя А. Отличаются они друг от друга индексами, например, A[1]=1, A[2]=2, A[3]=4, A[5]=8, A[6]=3.

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

Количество индексов в обозначении элемента массива определяет размерность массива. Массив может быть одномерным (один индекс S[4]), двумерным (два индекса N[2, 4]), трех мерным (три индекса Y[2, 4, 1]) и т.д.

Массив описывается в разделе описания переменных, при этом описание массива включает описание типа массива (тип его элементов, т.е. какие значения они могут принимать) и типа индексов. Например, массив вещественного типа с именем vector может быть описан следующим образом: var vector: array [1..50] of real

Это описание означает, что одномерный массив vector имеет 50 элементов типа real со значениями индекса 1, 2, ..., 50. Элементы этого массива будут иметь обозначения: vector[1], vector[2], ..., vector[50]

Двумерный массив matrix, с целочисленными компонентами можно определить следующим образом:

var matrix [1..10, 1..15] of integer

Двумерный массив часто называют матрицей. Первый индекс этого массива (номер строки матрицы) принимает значения из отрезка 1..10, а второй (номер столбца) - из отрезка 1..15. Компоненты массива могут иметь обозначения: matrix[1, 5], matrix[8, 8], matrix[i, j] и т.п.

Примеры:

program p2;

var matrix: array [1..3, 1..4] of integer; { определяется двумерный массив в 3 строки и 4 столбца с именем matrix}

i, j: integer;

begin

for i: =1 to 3 do

for j: =1 to 4 do

read(matrix[ i, j]); {заполнение двумерного массива на 3 строки и 4 столбца}

for i: =1 to 3 do

begin

writeln;

for j: =1 to 4 do write(matrix[ i, j]); {вывод элементов двумерного массива в виде таблицы}

end;

Структуризация. Восходящее программирование. Проектирование алгоритма перевода чисел из одной системы счисления в другую (2, 8, 10, 16).

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

7. Нисходящее программирование. Проектирование алгоритма выполнения арифметических операций (+, -, *, /) над числами с пл. точкой.

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

Язык TURBO PASCAL. Алфавит языка. Идентификаторы TURBO PASCAL.

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

Алфавит: буквы латинского от a до z, знак _.(если не char A = a)

Цифры – арабские 0-9, спец. символы +-*/=.,:; < > []{}()^& $@#%!

Пробелы (ASCII от 0 до 32) ограничители идентификаторов

Зарезервированные слова и параметры (не используются в качестве идентификаторов). Стандартные директивы absolute, assembler, external, far, forward, near и т.д..

Идентификаторы: имена констант, var’ных, меток, типов, obg-ов, процедур, функций(могут иметь произвольную длину, но значат только первые 63 символа, начинаются только с буквы или цифры).

Оператор условного перехода IF. Составной и пустой операторы.

IF< условие > THEN< операторы> ELSE < операторы>;

Оператор цикла со счетчиком.

FOR < идентификатор>: =< начальное состояние > TO< конечное состояние > DO< оператор>

FOR < идентификатор>: =< начальное состояние > DOWNTO< конечное состояние > DO< оператор>

Оператор цикла с предусловием.

Цикл ДО

WHILE< условие> DO< оператор>

Оператор цикла с постусловием.

Цикл ПОКА

REPEAT

Оператор;

UNTIL< условие>;

Подготовка и отладка программ в среде TurboPascal.

Меню run

Run- запуск на исполнение

Step over-пошаговое исполнение программы

Trace into- пошаговое исполнение программы только подпрограммы выполняются оператор за оператором

Go to cursor – выполнение до курсора

Program reset- завершение процесса отладки

Parameters- окно для ввода параметров для отладки

Меню compile

Compile- компиляция файла, находящегося в активном окне редактирования.

Make – условная компиляция изменённых модулей в ЕХЕ файл

Build- безусловная компиляция многомодульной программы с созданием ЕХЕ файла

Target…-выбор в окне таргет целевой платформы для приложения

Primary file…-открывает окно для указания главного файла, компилируемой программы.

Меню Debug:

Breakpoints- установка точек условного и безусловного перехода

Call stack – показывает процедуры выполнявшиеся ранее.

Watch – окно значений переменных

Output – окно результатов работы программы

User screen – просмотр результатов включая графику

Evaluate/ modify.. – окно изменения значений выражений

Add watch – окно значений и переменных вовремя отладки

Add breakpoint.. – окно установки точек прерывания программы

14. Константы в TURBO PASCAL (целые, вещественные, 16-ричные, логические, символьные, строковые константы, конструктор множества)

Константы - могут использоваться целые, вещественные, шестнадцатеричные числа, логические константы, символы, строки, множества и признак неопределённого указателя NIL.

Целые числа: от –2147483648 до 2147483647

Вещественные числа: (экспоненциальная часть) 3.14E5

16-ричное число: $(код 36 в ASCII) $00000000- $F…$F(8)

Логическая константа: True, False.

Символьная константа: любой символ в ‘ ‘, либо указатель внутри кода #83=’S’

Конструктор множества - список элементов множества в [].

[1, 2, 3, 4], [red, blue], [true, false]. В ТП разрешается объявление констант

const a=12/343;

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

Типизированные константы фактически являются переменными со статическим классом памяти. В отличие от простых констант, в описании типизированных указывается как значение константы, так и её тип.

Существуют типы:

Константа, константа-адрес, константа-массив, константа-запись, константа-объект, константа-множество.

Указательный тип:

Type ptr = ^integer;

Conct intptr: ptr=nil;

Структурированный тип:

1 массив (array)

2 множество (set of 1..4)

3 запись (record)

4Объектного типа (object)

Символьный тип.

Значением символьного типа является множество всех символов ПК. Каждому символу присваивается целое число в диапазоне 0..255.Это служит кодом внутреннего представления символа, его возвращает функция ORD. Для кодировки используется код ASCII – 7 битный код, т.е. с его помощью кодируется 128 символов (0..127). В то же время в 8-битном байте, отведённом для хранения символа в ТП, можно закодировать в 2 раза больше символов (0..255). (0-127ASCII, 128-255-может меняться на ПК разных типов).

0-31 – служебные коды (пробелы)

Модульное программирование. Оформление модуля в ТП.

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

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

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

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

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

UNIT< имя> -зарезервированное слово (единица), начинает заголовок модуля

INTERFACE< интерфейсная часть> - начинает интерфейсную часть

IMPLIMENTAITION< исполняемая часть>

BEGIN < инициируемая часть> END.

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

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

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

USES< имя вспомогательного модуля > - список связываемых модулей.

Интерфейсная часть –содержит объявление всех глобальных объектов модуля (типов, констант, переменных и программ), которые должны доступными основной программе или другим модулям. В интерфейсной части указываются только их заголовки. Объявление подпрограмм в интерфейсной части авто компилируется с использованием дальней модели памяти {far и near}, что обеспечивает доступ к подпрограмме из основной программы и др. модулей.Const, var объявленные в интерфейсной части модуля, как и глобальные константы и переменные помещаются в общий сегмент данных(max 65536 байт).

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

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

Стандартные модели:

SYSTEM, DOS, CRT, GRAPH, PRINTER, OVERLAY, TURBO3, GRARH3