Понятия и свойства алгоритмов

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

Команды школьного АЯ

Команда присваивания. Служит для вычисления выражений и присваивания их значений переменным. Общий вид: А  :=  В, где знак  ":="  означает команду заменить прежнее значение переменной, стоящей в левой части, на вычисленное значение выражения, стоящего в правой части.  
Например,   a := (b+c) * sin(Pi/4);   i := i+1.

Команды ввода и вывода.

• ввод имена переменных
• вывод имена переменных, выражения, тексты.

Команды   если   и   выбор. Применяют для организации ветвлений.

Команды   для   и   пока. Применяют для организации циклов.

Пример записи алгоритма  на школьном АЯ

алг Сумма квадратов (арг цел n, рез цел S) 

   дано | n > 0 

   надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i 

   ввод n; S:=0 

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

   S:=S+i*i 

   кц 

   вывод "S = ", S

кон

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

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

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

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

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

1. Базовая  структура  "следование". Образуется последовательностью действий, следующих одно за другим:

Школьный алгоритмический язык	Язык блок-схем
действие 1  действие 2  . . . . . . . . .  действие n

2. Базовая  структура  "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:

• если—то;
• если—то—иначе;
• выбор;
• выбор—иначе.

Школьный алгоритмический язык	Язык блок-схем
1. если—то
если условие    то действия  все
2. если—то—иначе
если условие    то действия 1    иначе действия 2  все
3. выбор
выбор    при условие 1: действия 1    при условие 2: действия 2    . . . . . . . . . . . .    при условие N: действия N  все
4. выбор—иначе
выбор    при условие 1: действия 1    при условие 2: действия 2    . . . . . . . . . . . .    при условие N: действия N    иначе действия N+1  все

 

Примеры структуры ветвление

 

Школьный алгоритмический язык	Язык блок-схем
если x > 0    то y := sin(x)  все
если a > b    то a := 2*a; b := 1    иначе b := 2*b  все
выбор     при n = 1: y := sin(x)     при n = 2: y := cos(x)     при n = 3: y := 0  все
выбор    при a > 5: i := i+1    при a = 0: j := j+1    иначе i := 10; j:=0  все

 
  

3. Базовая  структура  "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:

Школьный алгоритмический язык	Язык блок-схем
Цикл типа пока.   Предписывает выполнять тело цикла до тех пор,   пока выполняется условие, записанное после слова пока.
нц пока условие     тело цикла     (последовательность действий)  кц
Цикл типа для.   Предписывает выполнять тело цикла для всех значений         некоторой переменной (параметра цикла) в заданном диапазоне.
нц для i от i1 до i2    тело цикла    (последовательность действий)  кц

 

Примеры структуры цикл

 

Школьный алгоритмический язык	Язык блок-схем
нц пока i <= 5    S := S+A[i]    i := i+1  кц
нц для i от 1 до 5     X[i] := i*i*i    Y[i] := X[i]/2  кц

 

 

 

Пример 1. Вычислить сумму элементов числового массива   A = (a₁ , a₂ , ... , a_N ). 

 

Тест 

 

Данные		Результат
N=5	A=(3, 5, -2, 6, 3)	S=15.0

 

 

Демонстрация

Школьный  АЯ  алг Сумма (арг цел N, арг вещ            таб A[1:N], рез вещ S)   дано N>0 нач цел i  S:=0   нц для i от 1 до N     S := S + A[i]   кц кон

Исполнение алгоритма i S   0  1 0 + a1 = 0+3 = 5  2 a1 + a2 = 3+5 = 8  3 a1+a2+a3 = 8-2 = 6  4 a1+a2+a3+a4 = 6+6 = 12  5 a1+a2+a3+a4+a5 = 12+3=15

 

  

Блок-схема

 

   

 

 

Самостоятельная работа студентов

 Составить алгоритмы   для решения  следующих задач

1. Вычислите длину окружности, площадь круга и объём шара одного и того же заданного радиуса.
2. Вычислите периметр и площадь прямоугольного треугольника по длинам двух его катетов.
3. По координатам трёх вершин некоторого треугольника найдите его площадь и периметр.

 

1.1.3 Данные: понятие и типы. Основные базовые

 и структурированные  типы данных.

Программа в процессе выполнения всегда обрабатывает какие-либо данные. Данные могут представлять собой целые и дробные числа, символы, строки, массивы, множества и др. Так как компьютер всего лишь машина, для которой данные — это последовательность нулей и единиц, он должен абсолютно точно "знать", как их интерпретировать. По этой причине все данные в языке Delphi подразделены на типы. Для описания каждого типа данных существует свой стандартный идентификатор: для целых — Integer, для дробных — Real, для строк — string и т.д. Программист может образовывать собственные типы данных и давать им произвольные имена (о том, как это делается, мы поговорим чуть позже).

Тип данных показывает, какие значения принимают данные и какие операции можно с ними выполнять. Каждому типу данных соответствует определенный объем памяти, который требуется для размещения данных. Например, в языке Delphi существует тип данных Byte. Данные этого типа принимают значения в целочисленном диапазоне от 0 до 255, могут участвовать в операциях сложения, вычитания, умножения, деления, и занимают 1 байт памяти.

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

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

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

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

Понятие типа данных в  Турбо Паскаль

Для обработки ЭВМ данные представляются в виде величин и их совокупностей. С понятием величины связаны такая  важная характеристика, как ее тип.

Тип определяет:

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

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

Иерархия типов в языке Паскаль  такая:

• Простые
• Порядковые
• Целые
• Логические
• Символьные
• Перечисляемые
• Интервальные
• Вещественные
• Структуированные
• Массивы
• Строки
• Множества
• Записи
• Файлы
• Указатели
• Любая программа, написанная на любом языке программирования, по большому счету предназначена для обработки данных. В качестве данных могут выступать числа, тексты, графика, звук и др. Одни данные являются исходными, другие – результатом, который получается путем обработки исходных данных программой.
• Данные хранятся в памяти компьютера. Программа обращается к ним с помощью имен переменных, связанных с участками памяти, где хранятся данные.
• Переменные описываются до основного кода программы. Для них указываются ее имя и тип хранимых данных.
• В языке программирования Паскаль достаточно много типов данных. Кроме того, сам пользователь может определять свои типы данных.
• Тип переменной определяется тем, с какими данными она связана.
• Переменные типа integer могут быть связаны только с целыми значениями обычно в диапазоне от -32768 до 32767. В Pascal есть другие целочисленные типы.
• Переменные типа real хранят вещественные (дробные) числа.
• Переменная булевского (логического) типа может принимать только два значения - true (1, правда) или false (0, ложь).
• Символьный тип (char) может принимать значения из определенной упорядоченной последовательности символов.
• Интервальный тип определяется пользователем и формируется только из порядковых типов. Представляет собой подмножество значений в конкретном диапазоне.
• Можно создать собственный тип данных простым перечислением значений, которые может принимать переменная данного типа. Это так называемый перечисляемый тип данных.
• Все вышеописанное – это простые типы данных. Но бывают и более сложные, структурированные, которые базируются на простых типах.
• Массив – это структура, занимающая в памяти единую область и состоящая из фиксированного числа компонентов одного типа.
• Строки представляет собой последовательность символов. Причем количество этих символов не может быть больше 255 включительно. Такое ограничение характерная черта Pascal.
• Запись – это структура, состоящая из фиксированного числа компонент, называемых полями. В разных полях данные могут иметь разный тип.
• Множества представляют собой совокупность любого числа элементов, но одного и того же перечисляемого типа.
• Файлы для Pascal представляют собой последовательности однотипных данных, которые хранятся на устройствах внешней памяти (кстати, жесткий диск – это тоже внешняя память).
• Понятие такого типа данных как указатель связано с динамическим хранением данных в памяти компьютера. Часто использование динамических типов данных является более эффективным в программирование, чем статических.