Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I — различия между версиями
Admin (обсуждение | вклад) (→Оператор присваивания :=) |
Admin (обсуждение | вклад) м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin) |
||
(не показано 117 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | + | [[Категория:Основы программирования]] | |
− | + | [[Страница курса Основы программирования|К основной странице курса]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | : | ||
− | |||
− | + | == Алгоритм == | |
+ | [http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC '''Алгоритм'''] — набор команд, определяющих порядок действий для решения поставленной задачи. | ||
− | ''''' | + | С алгоритмом всегда связан '''исполнитель алгоритма''' - устройство, имеющее систему команд. |
− | + | В частности, процессор компьютера выступает исполнителем машинных команд. | |
− | + | === Свойства алгоритма === | |
+ | * Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя). | ||
+ | * Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат. | ||
+ | * Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных. | ||
+ | * Результативность — после выполнения алгоритма известно, что считать результатом. | ||
+ | * Массовость — применимость алгоритма ко множеству исходных данных. | ||
− | '' | + | ''<u>Пример алгоритма</u>.'' |
− | :Дано: x,y,z. | + | :Дано: <tt>x, y, z</tt>. |
− | :Найти max | + | :Найти <tt>max</tt> |
− | + | Алгоритм 1. (''словесное описание'') | |
− | Если x>y и x>z, то максимум | + | Если x>y и x>z, то максимум — это x |
− | Если y>x и y>z, то максимум | + | Если y>x и y>z, то максимум — это y |
− | Если z>x и z>y, то максимум | + | Если z>x и z>y, то максимум — это z |
− | + | Алгоритм 2. (''псевдокод'') | |
max := x | max := x | ||
Строка 38: | Строка 31: | ||
Если z<max то max := z | Если z<max то max := z | ||
+ | '''Эквивалентными''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных. | ||
+ | Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости. | ||
− | |||
− | + | '''Спецификация задачи''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | === Способы описания алгоритмов === | |
− | + | 1. ''Словесный'' | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | '''' | + | 2. ''Псевдокод'' |
− | |||
− | |||
− | + | 3. ''Блок-схемы'' | |
− | |||
− | |||
− | |||
− | '' | + | ''<u>Пример</u>.'' А.2., представленный блок-схемой. |
+ | [[Изображение:max_flowchart.png|none]] | ||
− | + | 4. ''Язык программирования (ЯП)'' | |
− | |||
− | |||
− | |||
− | ''''' | + | Для языка программирования команды алгоритма называются '''''операторами''''' или '''''инструкциями'''''. |
− | < | + | === Основные характеристики алгоритма=== |
+ | |||
+ | * правильность работы | ||
+ | * скорость выполнения | ||
+ | * объем занимаемой памяти | ||
+ | * сложность написания | ||
+ | * возможность распараллеливания | ||
+ | |||
+ | === Основные характеристики программы === | ||
+ | Те же, что и у алгоритма, а также: | ||
+ | |||
+ | * понятность при чтении | ||
+ | * модифицируемость (легкость изменения кода) | ||
+ | * масштабируемость (возможность изменения кода для решения родственной или более общей задачи) | ||
+ | * безопасность | ||
+ | |||
+ | Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы. | ||
+ | Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы. | ||
+ | |||
+ | === [http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных языков программирования] === | ||
+ | (самостоятельно на форуме) | ||
+ | |||
+ | == Язык программирования PascalABC.NET == | ||
+ | ===Правила записи программ на PascalABC.NET=== | ||
+ | '''[http://it.mmcs.sfedu.ru/files?func=fileinfo&id=24 Шпаргалка]''' | ||
+ | |||
+ | ===Пример программы, вычисляющей длину и площадь круга=== | ||
+ | <source lang="Pascal"> | ||
+ | program First; // заголовок программы – необязательная строка | ||
+ | { Программа вычисления длины окружности и площади круга | ||
+ | Автор: Михалкович С.С. Дата написания: 2.09.08 } | ||
+ | const Pi = 3.14; | ||
+ | var | ||
+ | r: real; // входные данные - радиус круга | ||
+ | S,C: real; (* выходные данные - площадь круга и длина окружности *) | ||
+ | begin | ||
+ | write('Введите радиус окружности: '); | ||
+ | readln(r); | ||
+ | S := Pi*r*r; | ||
+ | C := 2*Pi*r; | ||
+ | writeln('Длина окружности равна ',С); | ||
+ | writeln('Площадь круга равна ',S); | ||
+ | end. | ||
+ | </source> | ||
+ | |||
+ | ===Структура программы на языке Паскаль=== | ||
+ | |||
+ | <source lang="Pascal"> | ||
+ | Заголовок программы | ||
+ | Раздел описаний (описываются все используемые в программе переменные и определяются их типы) | ||
+ | begin | ||
+ | операторы (разделяются ;) | ||
+ | end. | ||
+ | </source> | ||
+ | |||
+ | Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу. | ||
+ | |||
+ | ===Система программирования PascalABC.NET=== | ||
+ | Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET]) | ||
+ | |||
+ | Общая характеристика PascalABC.NET. | ||
+ | |||
+ | Отличия языка PascalABC.NET от обычного языка Паскаль. | ||
+ | |||
+ | === Компиляторы и интерпретаторы === | ||
+ | Схема компиляции в машинный код | ||
+ | |||
+ | Схема компиляции в промежуточный код. JIT-компиляция | ||
+ | |||
+ | Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения | ||
+ | |||
+ | '''Синтаксис''' - правила записи конструкций, '''семантика''' - смысл конструкций. | ||
+ | |||
+ | == Синтаксис и семантика ЯП == | ||
+ | // В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка. | ||
+ | |||
+ | === Определения === | ||
+ | '''Синтаксис''' — формальные правила описания конструкций ЯП. | ||
+ | |||
+ | '''Семантика''' — описывает смысл конструкций ЯП, а также задает ряд ограничений. | ||
+ | |||
+ | === Способы описания синтаксиса === | ||
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60). | * ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60). | ||
− | '' | + | ''<u>Примеры</u>.'' |
<цифра> ::= 0|1|2|3|4|5|6|7|8|9 | <цифра> ::= 0|1|2|3|4|5|6|7|8|9 | ||
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра> | <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра> | ||
+ | <список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов> | ||
<tt>'''0, 1, ... 9'''</tt> | <tt>'''0, 1, ... 9'''</tt> | ||
− | :называют | + | :называют '''терминалами''' ('''лексемами''') — это "конечные символы", т.е. по умолчанию известные в ЯП. |
<tt>'''<цифра>'''</tt> | <tt>'''<цифра>'''</tt> | ||
− | :так называемый | + | :так называемый '''нетерминал''' ('''нетерминальный символ'''). |
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>) | :Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>) | ||
Строка 96: | Строка 152: | ||
:'''{}''' — 0 и более повторений | :'''{}''' — 0 и более повторений | ||
− | '' | + | ''<u>Пример</u>.'' |
<идентификатор> ::= <буква> {<буква> | <цифра>} | <идентификатор> ::= <буква> {<буква> | <цифра>} | ||
+ | |||
* ''Синтаксические диаграммы'' (Вирт, Паскаль) | * ''Синтаксические диаграммы'' (Вирт, Паскаль) | ||
− | + | '''Грамматика языка''' — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ. | |
− | |||
:Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила. | :Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила. | ||
− | |||
'''Замечание 1.''' Способы 1-3 эквивалентны. | '''Замечание 1.''' Способы 1-3 эквивалентны. | ||
Строка 109: | Строка 164: | ||
'''Замечание 2.''' Синтаксис определяет лексемы языка. | '''Замечание 2.''' Синтаксис определяет лексемы языка. | ||
− | + | === Лексемы Паскаля === | |
− | |||
# ''спецсимволы: '' <tt>''':= += *'''</tt> | # ''спецсимволы: '' <tt>''':= += *'''</tt> | ||
Строка 121: | Строка 175: | ||
::<span style="color: green">//...</span> | ::<span style="color: green">//...</span> | ||
− | + | == Переменные и их описание == | |
− | |||
− | |||
− | ==Переменные и их описание== | ||
− | + | === Основные сведения === | |
− | + | '''Переменная''' — это ячейка памяти компьютера, имеющая ''имя'' и ''тип''. | |
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений. | :'''''Тип''''' определяет размер переменной и множество принимаемых ею значений. | ||
− | В языке Pascal любая переменная перед использованием должна быть описана. | + | В языке ''Pascal'' любая переменная перед использованием должна быть описана. <br /> |
− | |||
Обычно переменные описываются в '''''разделе описаний'''''. | Обычно переменные описываются в '''''разделе описаний'''''. | ||
− | + | <xh4> Синтаксис в виде РБНФ </xh4> | |
− | |||
<программа> ::= ['''program''' <имя>;] | <программа> ::= ['''program''' <имя>;] | ||
<раздел описаний> | <раздел описаний> | ||
Строка 146: | Строка 195: | ||
<секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>... | <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>... | ||
− | '' | + | ''<u>Пример</u> секции описания переменных.'' |
− | + | <source lang="Pascal"> | |
− | + | var | |
− | + | a,b: real; | |
+ | i: integer; | ||
+ | </source> | ||
<секция описания переменных> ::= '''var'''<подсекция>{< подсекция>} | <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>} | ||
Строка 155: | Строка 206: | ||
<список имен> ::= <имя>{,<имя>} | <список имен> ::= <имя>{,<имя>} | ||
<тип> ::= <имя> | <тип> ::= <имя> | ||
− | |||
− | + | === Внутриблочные переменные === | |
− | <source lang="Pascal">begin | + | В PascalABC.NET возможно ''внутриблочное'' описание переменных: |
+ | |||
+ | <source lang="Pascal"> | ||
+ | begin | ||
var i,j: integer; | var i,j: integer; | ||
var r: real := 5.2; | var r: real := 5.2; | ||
− | var Pi := 3.14;</source> | + | var Pi := 3.14; |
+ | </source> | ||
− | В последнем случае происходит ''автоопределение'' типов. | + | В последнем случае происходит '''''автоопределение''''' типов. |
− | == | + | == Основные типы == |
* ''Целые'' | * ''Целые'' | ||
− | :integer (4 байта) | + | :<tt>'''integer'''</tt> (4 байта) |
− | : | + | :'''<tt>int64</tt>''' (8) |
− | : | + | :'''<tt>byte</tt>''' (1) |
− | |||
* ''Вещественные'' | * ''Вещественные'' | ||
− | :real (8 | + | :'''<tt>real</tt>''' (8) |
− | |||
* ''Символьные'' | * ''Символьные'' | ||
− | :char (2 — Unicode) | + | :'''<tt>char</tt>''' (2 байта — Unicode) |
*''Строковые'' | *''Строковые'' | ||
− | :string | + | :'''<tt>string</tt>''' |
− | :string[200] | + | :'''<tt>string</tt>'''[200] |
− | :shortstring = string[255] | + | :'''<tt>shortstring</tt>''' = <tt>string</tt>[255] |
* ''Логический'' | * ''Логический'' | ||
− | : | + | :'''<tt>boolean</tt>''' (1) ['''<tt>''True''</tt>''' '''<tt>''False''</tt>'''] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | '' | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ''' | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Текущая версия на 09:40, 24 января 2014
Содержание
Алгоритм
Алгоритм — набор команд, определяющих порядок действий для решения поставленной задачи.
С алгоритмом всегда связан исполнитель алгоритма - устройство, имеющее систему команд.
В частности, процессор компьютера выступает исполнителем машинных команд.
Свойства алгоритма
- Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
- Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
- Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
- Результативность — после выполнения алгоритма известно, что считать результатом.
- Массовость — применимость алгоритма ко множеству исходных данных.
Пример алгоритма.
- Дано: x, y, z.
- Найти max
Алгоритм 1. (словесное описание)
Если x>y и x>z, то максимум — это x Если y>x и y>z, то максимум — это y Если z>x и z>y, то максимум — это z
Алгоритм 2. (псевдокод)
max := x Если y<max то max := y Если z<max то max := z
Эквивалентными называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных. Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.
Спецификация задачи — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
Способы описания алгоритмов
1. Словесный
2. Псевдокод
3. Блок-схемы
Пример. А.2., представленный блок-схемой.
4. Язык программирования (ЯП)
Для языка программирования команды алгоритма называются операторами или инструкциями.
Основные характеристики алгоритма
- правильность работы
- скорость выполнения
- объем занимаемой памяти
- сложность написания
- возможность распараллеливания
Основные характеристики программы
Те же, что и у алгоритма, а также:
- понятность при чтении
- модифицируемость (легкость изменения кода)
- масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
- безопасность
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы. Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
Обзор современных языков программирования
(самостоятельно на форуме)
Язык программирования PascalABC.NET
Правила записи программ на PascalABC.NET
Пример программы, вычисляющей длину и площадь круга
program First; // заголовок программы – необязательная строка
{ Программа вычисления длины окружности и площади круга
Автор: Михалкович С.С. Дата написания: 2.09.08 }
const Pi = 3.14;
var
r: real; // входные данные - радиус круга
S,C: real; (* выходные данные - площадь круга и длина окружности *)
begin
write('Введите радиус окружности: ');
readln(r);
S := Pi*r*r;
C := 2*Pi*r;
writeln('Длина окружности равна ',С);
writeln('Площадь круга равна ',S);
end.
Структура программы на языке Паскаль
Заголовок программы
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
begin
операторы (разделяются ;)
end.
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
Система программирования PascalABC.NET
Как скачать, инсталлировать. (сайт системы программирования PascalABC.NET)
Общая характеристика PascalABC.NET.
Отличия языка PascalABC.NET от обычного языка Паскаль.
Компиляторы и интерпретаторы
Схема компиляции в машинный код
Схема компиляции в промежуточный код. JIT-компиляция
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
Синтаксис - правила записи конструкций, семантика - смысл конструкций.
Синтаксис и семантика ЯП
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
Определения
Синтаксис — формальные правила описания конструкций ЯП.
Семантика — описывает смысл конструкций ЯП, а также задает ряд ограничений.
Способы описания синтаксиса
- БНФ (Бэкуса-Наура формы, 1960, Алгол-60).
Примеры.
<цифра> ::= 0|1|2|3|4|5|6|7|8|9 <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра> <список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов>
0, 1, ... 9
- называют терминалами (лексемами) — это "конечные символы", т.е. по умолчанию известные в ЯП.
<цифра>
- так называемый нетерминал (нетерминальный символ).
- Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется рекурсивным (как определение нетерминала <идентификатор>)
- РБНФ (Расширенные БНФ)
- [] — 0 или 1 повторение.
- {} — 0 и более повторений
Пример.
<идентификатор> ::= <буква> {<буква> | <цифра>}
- Синтаксические диаграммы (Вирт, Паскаль)
Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
- Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.
Замечание 1. Способы 1-3 эквивалентны.
Замечание 2. Синтаксис определяет лексемы языка.
Лексемы Паскаля
- спецсимволы: := += *
- ключевые слова (begin, end, if, for)
- идентификаторы (a, b1)
- константы (2, 'ABC', #5)
- комментарии (3 вида)
- {...}
- (*...*)
- //...
Переменные и их описание
Основные сведения
Переменная — это ячейка памяти компьютера, имеющая имя и тип.
- Тип определяет размер переменной и множество принимаемых ею значений.
В языке Pascal любая переменная перед использованием должна быть описана.
Обычно переменные описываются в разделе описаний.
<xh4> Синтаксис в виде РБНФ </xh4>
<программа> ::= [program <имя>;] <раздел описаний> begin <операторы> end. <операторы> ::= <оператор>{; <оператор>} <раздел описаний> ::= {<секция раздела описаний>} <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
Пример секции описания переменных.
var
a,b: real;
i: integer;
<секция описания переменных> ::= var<подсекция>{< подсекция>} <подсекция> ::= <список имен>: <тип>; <список имен> ::= <имя>{,<имя>} <тип> ::= <имя>
Внутриблочные переменные
В PascalABC.NET возможно внутриблочное описание переменных:
begin
var i,j: integer;
var r: real := 5.2;
var Pi := 3.14;
В последнем случае происходит автоопределение типов.
Основные типы
- Целые
- integer (4 байта)
- int64 (8)
- byte (1)
- Вещественные
- real (8)
- Символьные
- char (2 байта — Unicode)
- Строковые
- string
- string[200]
- shortstring = string[255]
- Логический
- boolean (1) [True False]