Алгоритм и его свойства

Вид материала

Документы

Содержание А, в, м, n, summa, z1, z2, z3, prima14, first_value. Тип целый Тип вещественный Тип логический Тип литерный (символьный) Список индексов Представление основных структур программирования на языке паскаль Логические операции Оператор присваивания Оператор присваивания Условный оператор

Подобный материал:

• Программы: Основы алгоритмизации и программирования Тема урока : «Алгоритм и его свойства», 162.16kb.
• Расширенный алгоритм Евклида, 78.19kb.
• Конспект урока по информатике на тему: «Линейные алгоритмы», 85.45kb.
• Лекция Алгоритм его свойства и формализация. Принципы разработки алгоритмов и программ, 498.99kb.
• Тест по теме "Алгоритм и его свойства", 17.58kb.
• 8 Понятие об алгоритме и исполнителе алгоритмов. Свойства алгоритмов, 109.92kb.
• Тест Томаса Килмана, матрица стратегий поведения в конфликте, алгоритм, 116.81kb.
• Понятие алгоритма и его свойства., 198.88kb.
• Алюминий, его физические и химические свойства, 54.07kb.
• Волновой алгоритм (Алгоритм Ли), 30.36kb.

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

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

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

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

Например:

А, В, М, N, SUMMA, Z1, Z2, Z3, PRIMA14, FIRST_VALUE.

В стандартном Паскале знак подчеркивания не используется.

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

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

Тип целый содержит подмножество целых констант, при этом кардинальное число подмножества различается для разных ЭВМ. Для ЭВМ с двухбайтовым словом числа чаще всего находятся в диапазоне допустимых значений от -32768 до 32767. Такой тип переменной описывается служебным словом INTEGER. К целочисленным также относятся типы: BYTE, SHORTINT, WORD, LONGINT. Эти данные различаются внутренним представлением и диапазоном возможных значений (-128... 127 для SHORTINT и -2147483648 ... 2147483647 для LONGINT). Примеры целых чисел:

0,-3, 17, 193,-10000,5.

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

Если i и j идентификаторы переменной целого типа, то в описательной части программы должна присутствовать запись:

i, j: integer.

Стандартные операции для целых – это четыре действия арифметики: сложение, вычитание, умножение и деление нацело. Последняя операция должна давать целый результат, опуская возможный остаток. Эти операции над целыми числами производятся абсолютно точно, и результатами этих операций снова являются целые числа. В Паскале есть еще две операции над целыми числами: div и mod. Эти операции имеют по два целых операнда (аргумента): если значения а и b неотрицательны и b  0, то a div b и a mod b – это частное и остаток, возникающие при делении а на b. Например,

17 div 3 = 5, 17 mod 3 = 2, 8 div 2 = 4, 8 mod 2 = 0, 1 div 5 = 0, 1 mod 5 = 1.

Эти операции одного старшинства с умножением и делением, что важно иметь в виду при вычислениях выражений.

Тип вещественный (или действительный) обозначает подмножество вещественных констант. В то время как арифметические действия с целыми дают точные результаты, для арифметических действий над вещественными числами (операции сложения, вычитания, умножения, деления) допускается неточность в пределах ошибок округления. В этом и состоит явное различие между типами "целый" и "вещественный", характерное для большинства языков программирования. Для чисел вещественного типа в языке Турбо Паскаль определено пять стандартных вещественных типов: вещественный (REAL), с одинарной точностью (SINGLE), с двойной точностью (DOUBLE), с повышенной точностью (EXTENDED) и сложный (СОМР). На первых порах обойдемся типом REAL. Диапазон допустимых значений для типа REAL от 2.9* 10-39 до 1.7*10"38, область памяти для размещения – 6 байт, точность 11-12 знаков.

К этому типу относится подмножество вещественных чисел, которые могут быть представлены в формате с фиксированной точкой и с плавающей десятичной точкой. Числа с фиксированной точкой записываются в виде целой и дробной частей числа. Например: 5.45, -0.001, 17.0, -19.1919, 0.143. Запись числа не может начинаться или заканчиваться точкой. Числа с плавающей точкой используются для записи чисел, изменяющихся в широком диапазоне значений (от очень маленьких до очень больших). Десятичный порядок числа записывается буквой Е. Например, 65.4Е22 соответствует 65.4* 10"22. Числа с плавающей точкой: 0.547Е+З, 5.47Е+2, 54.7Е+1, 547.0Е0, 5470Е-1, 54700Е-2 представляют одно и тоже число 547.

Для обработки действительных (вещественных) чисел предусмотрены следующие операции: сложение (+), вычитание (-), умножение (*), деление (/). Операции возведение в степень в Паскале не существует. Если с = аb, то с рассчитывают по формуле с = .

Если а и b переменные вещественного типа, то в описательной части программы должно присутствовать

a, b: real;

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

Тип логический содержит всего два значения, которые обозначаются как истина и ложь (TRUE и FALSE). Слово BOOLEAN описывает логические переменные. Логические переменные используются для хранения результатов логических вычислений. Значения TRUE и FALSE являются по своей сути идентификаторами констант. Для булевых переменных разрешены только сравнения ">" (больше), "<" (меньше), "=" (равно) и "<>" (неравно). Другими допустимыми операциями являются: логическое сложение (AND), логическое умножение (OR), отрицание (NOT). Переменные типа BOOLEAN занимают 1 байт памяти.

Тип литерный (символьный) включает множество печатаемых символов. Символьный тип CHAR – представляет собой тип данных, предназначенный для хранения одного символа (буквы, знака или кода). В переменную этого типа на компьютере IBM может быть помещен любой из 256 символов расширенного кода ASCII. Это буквы [ 'A'...'Z', 'a'...'z'], цифры ['0'...'9'], знаки препинания и специальные символы. Переменная типа CHAR в памяти занимает 1 байт. Значения для переменных типа CHAR задаются в апострофах. Кроме того, имеется возможность задавать значения указанием числового значения ASCII-кода. В этом случае перед числом, обозначающим код ASCII символа, ставится знак (#). Например, СН:= #65 - присвоение переменной СН символа с ASCII кодом 65, то есть символа 'А'. Описание символьной переменной:

u, v:char;

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

CONST year = 1998; time = 12.05;

year – константа целого типа, так как не имеет в записи числа десятичной точки; time – константа вещественного типа.

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

VAR

a: INTEGER;

d, с: REAL;

b,e,f,g:CHAR;

Запрет на автоматическое преобразование типов еще не означает, что в Паскале нет средств преобразования данных. Для преобразования данных в языке существуют встроенные функции, которые получают в качестве параметра значение одного типа, а возвращают результат в виде значения другого типа. Для преобразования данных типа CHAR (символ) в целое число предназначена функция ORD, обратное преобразование INTEGER в CHAR осуществляет функция CHR.

В частности, для преобразования REAL в INTEGER имеются даже две встроенные функции такого рода; ROUND округляет REAL до ближайшего целого, a TRUNC усекает REAL путем отбрасывания дробной части.

trunc(3.14) = 3, trunc(-3.14) = -3, trunc(3.7) = 3.

round(3.14) = 3, round(3.7) = 4, round(-3.14) - -3.

Структуры данных

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

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

А [1], G [1,5], RAD [К, L], S [3, 4, 5].

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

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

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

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

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

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



В этом примере n = 4, m = 8.

Доступ к элементу массива задается списком из двух индексов:

а₂₄ или А(2,4) – определяет элемент 2-й строки 4-го столбца;

а_iк или А(i, k) – определяет элемент i-й строки k-гo столбца.

Индекс I имеет диапазон изменений от 1 до 3, а индекс к - соответственно от 1 до 8.

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

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

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

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

При обработке данных комбинированные типы, такие как описания людей или материальных объектов, часто встречаются в файлах (или наборах данных) и представляют собой записи существенных характеристик человека или объекта. Поэтому термин запись стал широко использоваться для обозначения подобной совокупности структурированных данных. Отдельные компоненты записи называются полями. Например, запись, предназначенная для хранения информации о городах состоит из пяти полей: название города, его географические координаты (долгота, широта, высота) и количество населения. К этой записи, как к переменной, обращаются по имени переменной ГОРОД, а к отдельным полям путем использования составного имени: ГОРОД.ИМЯ или

ГОРОД.НАСЕЛЕНИЕ.

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

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

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

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

ПРЕДСТАВЛЕНИЕ ОСНОВНЫХ СТРУКТУР ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ ПАСКАЛЬ

Операции и выражения

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

Выражение не просто имеет некоторое значение, но и обладает совершенно определенным типом, который зависит от операндов и операций.

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

1. Операции более низкого уровня выполняются раньше, чем операции более высокого уровня.

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

Эти правила действуют для всех типов выражений.

Арифметические операции и выражения

Арифметические выражения имеют тип real или integer, причем мы всегда под real будем понимать также single, double, extended и comp, а под integer – byte, word, shortint и longint.

Пример арифметического выражения: (- b + sqrt(sqr( b)–4*a*c))/(2*a)

При составлении выражений следует выполнять следующие правила:

1. Записывать все составные части выражений в одну строку.

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

3. Нельзя записывать подряд два знака арифметических операций.

К арифметическим операциям относятся: первый уровень *; /, mod и div; второй уровень +, -. То есть при вычислении арифметического выражения действуют обычные правила старшинства операций: сначала выполняются умножение, деление, деление нацело и нахождение остатка от деления нацело в том порядке, в каком они входят в выражение, а затем сложение и вычитание. Между знаком div (или mod) и числами, участвующими в делении, должно находиться хотя бы по одному пробелу.

Несколько примеров:

5 + 2 * 10 = 25;

10.2 * 5 -7 + 8.6/2 = 22.3;

(5 + 105)div7 = 5

Тип результата в зависимости от типа операндов:

Запишем несколько обычных математических выражений на Паскале.

Если при расстановке скобок возникнут сомнения, вспомните правило: "Лишние скобки не мешают".

Нельзя размещать два знака операций рядом; последовательности символов 3 * - 2, х1 / - х2 - это не выражения, выражениями будут 3 * (-2), х1 / (-х2).

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

Правила записи стандартных функций:

1. Имя функции записывается буквами латинского алфавита.
   
2. Аргумент функции записывается в круглых скобках после имени функции.
   

3. Аргументом функции может быть константа, переменная или арифметическое выражение.

Приведем ряд стандартных математических функций.

abs(x) х

ехр(х) е^x

cos(x) cos х

sin(x) sin x

arctan(x) arctg

in(x) ln x

sqr(x) x²

sqrt(x)

random(x) Если х отсутствует, значением функции является случайное число типа real из диапазона 0<= ...<1. Если задается параметр х, значением функции будет случайное число из диапазона

Логические операции

Логические выражения имеют значение типа boolean, то есть true или false. Выражение, служащее для вычисления логического значения, называется логическим выражением или логическим условием.

Одним из видов логического выражения является отношение. Отношение – это два выражения, соединенные операцией отношения. Например,

у < 0, а > b, х = у, х < а - b.

Операции отношения: > (больше), < (меньше), > (не меньше), < (не больше), = (равно),  ( не равно) – на языке Паскаль записываются соответственно: >, <, >=, <=, =, <> и имеют более низкий приоритет по сравнению с арифметическими операциями. Иными словами, сначала выполняются арифметические операции, а потом операции отношения.

Условие a + bc + d нa языке Паскаль записывается так: а + b <> с + d.

Высказывания о значениях переменных могут быть истинными или ложными в зависимости от самих значений переменных. Так, если s = 5, t = 6, то высказывание s > t – ложное, высказывание s < t + 12 – истинное.

Логические значения упорядочены. Выражение true > false является истинным.

Из простых высказываний в Паскале разрешается строить более сложные. Пусть А и В – некоторые высказывания, тогда A and В – это новое высказывание, утверждающее истинность обоих высказываний А и В; A or В – это новое высказывание, утверждающее истинность хотя бы одного из высказываний А и В. Если С – высказывание, то not С – это новое высказывание, утверждающее, что С – ложное высказывание.

Операции над высказываниями (логические операции) and, or, not называются соответственно конъюнкцией, дизъюнкцией и отрицанием.

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

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

(х > у) or (у > z) and not ((x > 0) or (z > х))

устанавливается следующий порядок логических операций: 4 3 2 1

(х > у) or (у > z) and not ({x > 0) or (z > х))

При х = –1, z = -2, у = 1 результатом будет значение true.

(х > 0) - false, (z > х) – false;

(х > 0) or (z > х) – false;

not ((x > 0) or (z > x)) – true;

(x > y) - false, (y > z) – true;

(y > z) and not ((x > 0) or (z > x)) – true.

В конечном итоге false or true дает true.

Оператор присваивания

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

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

Оператор присваивания является важнейшим оператором любого языка программирования. С его помощью можно присвоить переменной значение выражения. Выражение оценивается, то есть определяется его значение, и это значение присваивается переменной. В результате прежнее значение переменной перезаписывается, а поэтому старое значение утрачивается. Знаком присваивания в Паскале является совокупность знаков ( := ). Например, в операторе присваивания Y := (А * X + В) * X + С справа от знака :=, записано выражение (А * X + В) * X + С, а слева – переменная Y. Нужно запомнить: слева не может быть выражение.

Пусть i = 1. После выполнения оператора присваивания i := i + 1, переменная i будет иметь значение 2.

Условный оператор

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

Структура условного оператора:

IF <условие>ТНЕN <оператор1 > ELSE <оператор2>,

где IF, THEN, ELSE - зарезервированные слова (если,.то, иначе);

<условие> - произвольное выражение логического типа;

<оператор1>,<оператор2> - любые операторы языка.

I Оператор if | :



Условный оператор работает по следующему алгоритму. Вначале вычисляется условное выражение <условие>. Если результат есть TRUE (истина), то выполняется <оператор1 >, а <оператор2> пропускается; если результат есть FALSE (ложь), наоборот, <оператор1 > пропускается, а выполняется <оператор2>. Например:

var х, у, max : real;

if x > max

then у := max else у :=x;

Этот условный оператор читается: если условие х > max выполняется, то у := max, иначе у := х.

Часть ELSE <оператор2> условного оператора может быть опущена. Тогда при значении TRUE условного выражения выполняется <оператор1>, в противном случае этот оператор пропускается (рис. 37).

Если требуется выполнить после then или else несколько операторов, они обрамляются командами begin и end, образуя тем самым составной оператор.