Алгоритм и его свойства
| Вид материала | Документы |
- Программы: Основы алгоритмизации и программирования Тема урока : «Алгоритм и его свойства», 162.16kb.
- Расширенный алгоритм Евклида, 78.19kb.
- Конспект урока по информатике на тему: «Линейные алгоритмы», 85.45kb.
- Лекция Алгоритм его свойства и формализация. Принципы разработки алгоритмов и программ, 498.99kb.
- Тест по теме "Алгоритм и его свойства", 17.58kb.
- 8 Понятие об алгоритме и исполнителе алгоритмов. Свойства алгоритмов, 109.92kb.
- Тест Томаса Килмана, матрица стратегий поведения в конфликте, алгоритм, 116.81kb.
- Понятие алгоритма и его свойства., 198.88kb.
- Алюминий, его физические и химические свойства, 54.07kb.
- Волновой алгоритм (Алгоритм Ли), 30.36kb.
Язык Ассеблера – это язык, предназначенный для представления в удобочитаемой форме программ, записанных на машинном языке. Он позволяет программисту пользоваться мнемоническими кодами операций, по своему усмотрению присваивать символические имена регистрам ЭВМ и ячейкам памяти, а также задавать наиболее удобные в том или ином контексте схемы адресации. Кроме того, язык Ассемблера обеспечивает представление констант в различных системах счисления (например, в десятичной или шестнадцатиричной).
Язык Макроассемблера является расширением языка Ассемблера за счет включения макросредств и предоставляет средства определения и использования новых, более мощных команд как последовательностей базовых инструкций, что несколько повышает его уровень.
Языки Ассемблера и Макроассемблера применяются системными программистами-профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной, как по времени выполнения, так и по потребному объему памяти, программы.
Приведем краткий перечень наиболее распространенных языков программирования высокого уровня, которые имеют преимущественное распространение в настоящее время, причем имеют по несколько версий.
Бейсик представляет собой простой язык программирования, разработанный в 1964 году для использования новичками. Работа в среде Бейсика первоначально велась только в режиме интерактивной (диалоговой) интерпретации. В настоящее время имеются и компиляторы с этого языка. В этом языке широко используются разного рода умолчания, что считается плохим тоном в большинстве современных языков. Несмотря на это, Бейсик очень популярен, в особенности на ПЭВМ. Существует множество его диалектов. Бейсик является одним из наиболее динамичных языков. Не без оснований этот язык иногда сравнивают с питоном, заглатывающим и переваривающим все новое, что появляется в других языках программирования. Уровень Бейсика нельзя определить однозначно. Современные диалекты весьма развиты и мало чем напоминают своего предка.
Язык Фортран был разработан в 1956 году, затем появились новые его версии Фортран-II, Фортран-IV, Фортран-66, Фортран-77, Фортран-8х, Фортран-88. В свое время этот язык был поистине "рабочей лошадью" научных работников и широко используется в настоящее время, несмотря на его ограниченность и корявость. Он предоставляет пользователям большие возможности для обработки числовых данных, особенно комплексных чисел. Еще в версии Фортран-II впервые была реализована идея раздельной компиляции модулей, что дало возможность создавать библиотеки научных подпрограмм.
Язык программирования СИ первоначально разработан в 70-х годах. В настоящее время в СИ сочетаются достоинства современных высокоуровневых языков и возможность доступа к аппаратным средствам машины на уровне, который обычно ассоциируется с языком Ассемблера. СИ имеет синтаксис, обеспечивающий чрезвычайную краткость программ, а компиляторы, вследствие особенностей языка, способны генерировать быстрые и эффективные программы на машинном коде.
Язык программирования APL создан в 1969 году. К числу его основных преимуществ относятся богатый набор мощных операторов, позволяющих работать с многомерными массивами как с единым целым, а также предоставление пользователю возможности определять собственные операторы. Основное его назначение – обработка массивов.
FORTH – гибкий и достаточно простой язык, разработанный в 1971 году. Важная его особенность - открытость (расширяемость). Программист может добавлять новые операции, типы данных и операторы. Последнее достигается путем связывания любой строки программы с заданным программистом словом, которое затем может использоваться наравне со стандартными операторами. Однако расширение языка ведет к снижению эффективности.
Характеристика языка программирования Паскаль
Одним из наиболее популярных языков программирования является язык Паскаль. Первая версия языка программирования Паскаль была разработана на кафедре информатики Стэнфордского университета швейцарским ученым Никлаусом Виртом в 1968 году, и названа в честь французского ученого Блеза Паскаля. Прошло много времени с момента появления Паскаля на рынке программных продуктов, прежде чем он получил всеобщее признание вследствие разработки языка программирования Турбо Паскаль (ТП) – диалекта языка, созданного американской фирмой Борланд. Эта фирма объединила очень быстрый компилятор с редактором текста и добавила к стандартному Паскалю мощное расширение, что способствовало успеху первой версии этого языка. С тех пор Турбо Паскаль значительно расширился. Появились новые графические процедуры, возможность использования при написании программ языка программирования низкого уровня Ассемблер, возможность создавать объектно-ориентированные программы и многое другое. В лингвистической концепции Паскаля пропагандируется системный подход, выражающийся, в частности, в расчленении крупных проблем на меньшие по сложности и размеру задачи, легче поддающиеся решению Набор операторов стандартного Паскаля относительно мал и легко изучаем. Но это порождает проблему расширения языка в приложениях. В Турбо Паскале эта проблема решается за счет поставок большого количества библиотек разнообразных процедур, готовых к употреблению в прикладных программах.
Влияние Паскаля ощущается в настоящее время в разных языках программирования. Так, среди новых диалектов Бейсика есть Паскаль с символикой Бейсика. Даже в язык СИ встраивается все больше элементов, порожденных Паскалем.
С момента создания первой версии языка Паскаль прошло много времени и язык значительно преобразился, но тем не менее стандартный Паскаль является основой более поздних версий Турбо Паскаля. В дальнейшем в описании языка будут встречаться оба эти названия. Будем использовать название Паскаль, если утверждение верно и в стандартном Паскале и в Турбо, а Турбо Паскаль, если в последних версиях имеются отличия. При изучении сложных конструкций языка имеет смысл говорить только о Турбо Паскале.
Алфавит языка Паскаль
Любой естественный язык состоит из нескольких основных элементов: символов, слов, словосочетаний и предложений. В алгоритмическом языке программирования имеются аналогичные структурные элементы: символы, слова, выражения (словосочетания) и операторы (предложения). При этом слово образуется из последовательности символов, выражение представляет собой группу слов, а оператор – определенную комбинацию слов и выражений.
Язык программирования Паскаль, как и любой другой, имеет свой алфавит. Алфавитом языка программирования называют набор символов (разрешенный к использованию и воспринимаемый компилятором), с помощью которого могут быть образованы величины, выражения и операторы данного языка. Алфавит языка Паскаль включает в себя все символы, представленные в кодировочной таблице, которая в настоящий момент загружена в оперативную память или хранится в ПЗУ компьютера. Каждому символу алфавита соответствует индивидуальный числовой код от 0 до 255. Символы с кодами от 0 до 127 представляют собой так называемую основную таблицу кодов ASCII. Их состав и порядок определены американским стандартом на коды обмена информацией (идентичны для всех IBM-совместимых компьютеров).
Символы, используемые для составления идентификаторов:
- латинские строчные и прописные буквы,
- арабские цифры от 0 до 9,
- символ подчеркивания (в Турбо Паскале).
Символы разделители:
- пробел, основное назначение которого разделение ключевых слов и имен,
- - управляющие символы (ASCII - коды от 0 до 31). Эти символы могут применяться при описании строчных и символьных констант. Управляющие символы с ASCII – кодом 9 (табуляция), а также 10 и 13 (замыкающее строку) используются в качестве разделителей при написании программ.
Специальные символы, выполняющие определенные функции при построении различных конструкций языка:
+ - * / { } [ ] ( ) < > ? ' : ; # @ $
Составные символы – группа символов, которые воспринимаются компилятором как единое целое:
<= => := (* *) (..) ..
"Неиспользуемые" символы, символы так называемой расширенной таблицы ASCII, то есть символы, имеющие коды от 128 до 255 ( в этой области находятся символы алфавита русского языка и символы псевдографики на IBM-совместимых компьютерах), а также некоторые символы из основной таблицы ASCII (например: &, !, %, " и другие). Их можно использовать в тексте комментариев и в виде значений констант строк или констант символов.
Зарезервированные слова (BEGIN, END, PROGRAM и другие), несущие определенную смысловую нагрузку в языке программирования. Зарезервированное слово – это слово, которое в языке Паскаль имеет определенное смысловое значение. Еще говорят служебное слово или ключевое слово – это слова синонимы. Имя служит для обозначения каких-либо объектов. В языке Паскаль различают два вида имен: стандартные и даваемые пользователем ЭВМ.
Структура программы на Паскале
Программы, написанные на языке программирования Турбо Паскале, строятся в соответствии с правилами, представляющими собой несколько расширенные и "ослабленные" правила синтаксиса стандартного Паскаля. Приведем пример программы на Турбо Паскале. Надо сразу подчеркнуть, что программа написана для процесса обучения, поскольку в жизненной ситуации она не пригодится.
PROGRAM Addition;
{ ADDITION.PAS - Программа суммирования двух введенных целых чисел}
VAR
Numbe r_1, Number_2, Sum: INTEGER;
BEGIN
Write (' Введите первое число: ');
ReadLn(Number_1);
Write ('Введите второе число:');
ReadLn (Number_2);
Sum := Numbe r_1 + Number_2;
WriteLn (' Сумма введенных чисел равна: '.Sum);
END.
Любую программу, написанную на Паскале можно условно разделить на две основные части:
- раздел объявлений и описаний;
- раздел основного блока.
В разделе объявлений и описаний программист сообщает компилятору, какими идентификаторами он обозначает данные (константы и переменные), а также определяет собственные типы данных, которые он в дальнейшем намеревается использовать в данной программе. В Турбо Паскале есть возможность подключать используемые в программе объекты, описанные в другом месте. Такие объекты называются модулями и о них мы будем говорить позже.
"Процедура" и "функция" – термины, применяемые в Паскале для обозначения специальным образом оформленной последовательности команд (подпрограммы). Доступ к такой подпрограмме может быть осуществлен из любого места основного блока программы, а также из любой процедуры или функции, описание которых следует ниже. В разделе описаний содержится описание процедур и функций в виде текста процедур и функций, который строится по правилам аналогичным правилам построения программы.
Основной блок программы состоит из последовательности операторов, причем работа программы начинается именно с первого оператора основного блока программы. Тело основного блока программы ограничено словами BEGIN и END.
Структура рассмотренной программы имеет следующий вид:
PROGRAM Addition;
{Раздел описаний}
BEGIN
{Раздел операторов}
END.
Необходимо обратить внимание на наличие точки после служебного слова END. После последнего оператора END всегда ставится точка, тем самым компилятор получает информацию об окончании текста программы.
Слово PROGRAM зарезервировано в Паскале и означает начало программы. Далее записывается имя программы (в приведенном примере – Addition). В Турбо Паскале можно опускать объявление имени оператором PROGRAM без каких-либо последствий для программы.
Строки программы обычно выделяют некоторые смысловые фрагменты текста и могут не связываться с конкретными действиями в программе. Программа записывается в свободной форме, операторы не привязаны к определенной позиции строки в отличие от других языков программирования. Расположение текста программы по строкам – дело вкуса программиста, а не требование синтаксиса языка. В то же время рекомендуется программу записывать в такой внешней форме, чтобы ее можно было легко читать и понимать. Для этого широко используются пробелы, пустые строки и комментарии. Рекомендуется смысловые части выделять одинаковыми отступами от начала строки.
Пробел в Паскале используется как разделитель отдельных конструкций языка, следовательно необходимо внимательно следить за его присутствием в качестве разделителя.
Соответствующие строчные и прописные буквы являются эквивалентными, если только это не связано с текстовыми константами.
Разделитель ; отмечает конец оператора или описания. Использование особого разделителя позволяет располагать несколько операторов на одной строке.
После заголовка программы следует текст, заключенный в фигурные скобки. Это комментарий. Комментарий – выделенная фигурными скобками информация для пояснения, которая не исполняется программой. Кроме фигурных скобок { }, могут использоваться также пары символов (* и *) слева и справа от комментария соответственно.
В нашем примере в разделе описаний объявлены три переменные Number_1, Number_2, Sum как переменные целого типа. Имена переменных записаны через запятую, а перед служебным словом INTEGER стоит двоеточие.
Зарезервированное слово BEGIN в следующей строке сигнализирует компилятору о начале другой части программы – раздела операторов. Write, WriteLn, ReadLn служат для вывода и ввода информации и являются стандартными процедурами. В Турбо Паскале есть возможность использования некоторых стандартных процедур без предваряющего описания этих процедур (общее правило гласит: все процедуры должны быть описаны). По своей сути оператор
Write('Введите первое число:');
является оператором обращения к встроенной процедуре вывода данных. Свое название она получила от write - записать, a writeln - записать строку.
Процедура write осуществляет вывод объектов перечисленных в скобках через запятую. В данном случае выводится текстовая константа 'Введите первое число:'.
ReadLn (Number_1); – стандартная процедура ввода численного значения переменной с именем Number_1. При выполнении программы машина предоставит возможность ввести с клавиатуры численное значение этой переменной. Два следующих оператора аналогичны.
Оператор
Sum := Number_1 + Number_2;
- оператор присваивания, один из основных операторов языков программирования. В его левой части указывается имя переменной, правая часть представляет собой выражение того же типа, что и переменная. Выполняется оператор так: вычисляется численное значение выражения в правой части и результат записывается в переменную слева. Другими словами, оператор присваивания - вычислитель. Переменная Sum принимает значение суммы двух переменных Numbe r_1 и Number_2.
WriteLn(' Сумма введенных чисел равна: '.Sum);
выводит два объекта – текстовую константу и переменную. Оператор write выводит строку на экран и оставляет курсор в конце только что выведенной строки. Оператор writeln после вывода устанавливает курсор в начало следующей строки.
Синтаксические диаграммы
Оператор
содержит некоторое синтаксическое понятие,
Рис. 8
Рис. 9
содержит символы, входящие в исходный текст.
Рис. 10
Для описания синтаксиса языка часто используются синтаксические диаграммы. Синтаксическая диаграмма является направленным графом, при прохождении которого автоматически строится синтаксически правильная программа. В диаграмме следует различать два типа символов:
Синтаксические диаграммы отражают лишь небольшую часть синтаксиса. Каждое понятие, заключенное в прямоугольник, требует, в свою очередь, некоторого определения. Структуру программы на Паскале можно представить следующей схемой (рис.8):
На диаграмме видно, что заголовок может быть, а может нет. После заголовка идет собственно программа в виде некоторого блока. Понятие блок требует расшифровки (рис. 9).
Диаграмма для описания представлена на рис. 10.
Из синтаксической диаграммы видно, что не все перечисленные разделы обязательны в каждой программе. В приведенном примере присутствует только описание переменных.
СТАНДАРТНЫЕ ТИПЫ ДАННЫХ
Данные
Одна из характерных особенностей современных ЭВМ состоит в возможности получать, накапливать и хранить большие объемы информации, содержащие формализованные сведения об окружающем человека мире. Поступившая в ЭВМ информация может быть обработана с целью извлечения из нее требуемых пользователю сведений в зависимости от его интересов и потребностей практики.
Информация, хранящаяся в памяти ЭВМ и доступная для обработки, состоит из данных. Данные в определенной степени являются приближенным отражением действительности, поскольку в них игнорируются некоторые свойства и характеристики реальных объектов, несущественные для решаемой задачи.
Применение ЭВМ для хранения и обработки данных приводит к разделению данных и их смыслового содержания. ЭВМ, как правило, имеют дело с данными как таковыми, а большая часть интерпретирующей информации в явной форме не фиксируется. Ее должен знать пользователь и применять при анализе данных, полученных от ЭВМ.
Рассмотрим, например, программу численного анализа, предназначенную для решения систем обыкновенных дифференциальных уравнений. Эта программа получает в качестве исходных данных некоторые числа и вырабатывает в результате другие числа. Она " не знает ", описывают ли дифференциальные уравнения механические или электромагнитные явления. Ответственность за интерпретацию результатов в контексте их применения лежит на пользователе программы.
Каждый из параметров для задания свойства должен быть представлен либо отдельным значением, либо совокупностью значений. Значения могут характеризовать как количественную, так и качественную сторону объекта. Так, параметр масса может задаваться количественно (например, 1275), параметр цвет - качественно (например, красный); одни параметры - масса, длина, ширина, высота, стоимость, цвет - могут относиться к объекту в целом, другие -характеризовать разные свойства деталей, из которых состоит изделие (массу, стоимость, материал и т. п.). Параметр может иметь и более сложную структуру, отражая одновременно и название детали, и ее серийный номер, и массу, и объем, и положение в пространстве (координаты). Это уже агрегированные параметры.
В научных и инженерных расчетах наиболее распространенным параметром является отдельное измерение. Такие данные являются скалярами и представляют собой отдельные числа и слова (символьные последовательности).
Известным примером скаляра является константа. Это элемент данных, который имеет фиксированное имя, фиксированный тип и фиксированное значение. Для обозначения константы используется ее явная запись или выбранный идентификатор. Например, обозначение 3.141592 задает константу вещественного типа, значение которой фиксировано как число 3.141592, а имя (внешнее представление для пользователя ЭВМ) изображается ее значением. Такая интерпретация константы общепринята в математике. Разработчик алгоритма может пожелать связать с константой вещественного типа, представленной значением 3.141592, имя Р, которое является символической константой.
Скаляром может быть также и строка символов, образованная последовательностью литер. Например, слово "ВЛАДИМИР" задает константу
литерного типа, значение которой фиксировано как цепочка литер "ВЛАДИМИР", а имя представлено ее же значением. При необходимости этой константе можно поставить в соответствие уникальный идентификатор (имя) и использовать его как символьную константу. Итак, константа – некоторая неизменная величина. Константа может задаваться числом или идентификатором.
Наряду с константами широко используются и переменные. Переменной называется объект, имеющий фиксированное имя, фиксированный тип и изменяющееся в зависимости от применяемых действий значение.
Типы данных
Следует иметь в виду, что при решении задач ЭВМ оперирует не со значениями, а с их обозначениями, которыми являются конфигурации битов, байтов или слов. Чтобы ЭВМ могла при выполнении операций распознавать принадлежность этих конфигураций к тому или иному типу данных, необходимо при разработке алгоритмов, и особенно программ, прямо указывать эту принадлежность. Достигается это путем явного описания типов используемых данных. В зависимости от типа, заданного в описании переменной, она может принимать текущие значения только указанного типа. Например, если тип переменной А указан как "целый", то она в данный момент времен может иметь любое значение из допустимого множества целых чисел {...-3, -2, -1,0,1,2,3,...}; если тип переменной В указан как "логический", то текущее значение может быть одним из двух { истина, ложь}.
Каждый тип данных характеризуется так называемым кардинальным числом - количеством различных значений, принадлежащих типу. Для каждого типа данных должен быть строго определен набор операций, которые можно применять при обработке данных этого типа.
Изначально определенные типы данных называются простыми, причем те из них, которые непосредственно "встроены" в ЭВМ, носят название стандартных типов. Каждый алгоритмический язык программирования предоставляет пользователю набор различных типов элементарных данных, средства их описания и операторы обработки, обеспечивающие выполнение над данными тех или иных действий. Компилятор связывает имя элемента данных с определенным адресом памяти ЭВМ, по которому в процессе выполнения программы хранится значение именованного элемента данных, что освобождает программиста от необходимости знать этот адрес.