Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin)
 
(не показано 166 промежуточных версий 7 участников)
Строка 1: Строка 1:
−
==Алгоритм==
+
[[Категория:Основы программирования]]
−
<small>'''Лекция 1'''</small>
+
[[Страница курса Основы программирования|К основной странице курса]]
−
<h3>Свойства алгоритма</h3>
 
−
<ul>
 
−
<li>''дискретность''</li>
 
−
<li>''элементарность команд''</li>
 
−
<li>''определенность команд''</li> 
 
−
:каждая команда имеет четкое однозначное значение
 
−
<li>''конечность''</li> 
 
−
:каждый А. должен когда-то завершаться при любом наборе исходных данных
 
−
<li>''результативность''</li> 
 
−
:после выполнения А. известно, что считать результатом
 
−
<li>''массовость''</li> 
 
−
:применимость ко множеству исходных данных
 
−
</ul>
 
  
−
<h3>Связанные понятия</h3>
+
== Алгоритм ==
 +
[http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC '''Алгоритм'''] — набор команд, определяющих порядок действий для решения поставленной задачи.
  
−
'''''Спецификация задачи''''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
+
С алгоритмом всегда связан '''исполнитель алгоритма''' - устройство, имеющее систему команд.
  
−
'''''Исполнитель алгоритма''''' — устройство, имеющее некоторую систему команд, и способное их исполнять.
+
В частности, процессор компьютера выступает исполнителем машинных команд.
−
:Процессор — исполнитель машинных кодов.
+
=== Свойства алгоритма ===
 +
* Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
 +
* Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
 +
* Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
 +
* Результативность — после выполнения алгоритма известно, что считать результатом.
 +
* Массовость — применимость алгоритма ко множеству исходных данных.
  
 +
''<u>Пример алгоритма</u>.''
 +
:Дано: <tt>x, y, z</tt>.
 +
:Найти <tt>max</tt>
  
−
<tt>'''Пример.'''
+
Алгоритм 1. (''словесное описание'')
−
:Дано: x,y,z.
 
−
:Найти max</tt>
 
  
−
'''А.1.''' (''словесное описание'').
+
Если x>y и x>z, то максимум — это x
 +
Если y>x и y>z, то максимум — это y
 +
Если z>x и z>y, то максимум — это z
  
−
Если x>y и x>z, то максимум - это x
+
Алгоритм 2. (''псевдокод'')
−
Если y>x и y>z, то максимум - это y
 
−
Если z>x и z>y, то максимум - это z
 
−
 
 
−
'''А.2.''' (''псевдокод'').
 
  
 
  max := x
 
  max := x
Строка 39: Строка 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.  
  
−
<h3>Способы описания алгоритмов</h3>
+
Отличия языка PascalABC.NET от обычного языка Паскаль.
−
<ul>
 
−
<li>''словесный''</li>
 
−
<li>''псевдокод''</li>
 
−
<li>''блок-схемы''
 
−
</ul>
 
  
−
<tt>'''Пример.''' А.2., представленный блоксхемой.</tt>
+
=== Компиляторы и интерпретаторы ===
−
[[Изображение:2.JPG|none]]
+
Схема компиляции в машинный код
−
<ul>
 
−
<li>''диаграммы деятельности (activity diagram) UML''
 
−
</ul>
 
−
<tt>'''Пример.''' А.2., представленный диаграммой деятельности</tt>
 
−
[[Изображение:2-1.JPG|none]]
 
−
<ul>
 
−
<li>''язык программирования (ЯП)''</li>
 
−
</ul>
 
  
−
'''''Команды алгоритма''''' также называются:
+
Схема компиляции в промежуточный код. JIT-компиляция
−
:* операторы Я.
 
−
:* инструкции Я.
 
  
 +
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
  
−
==Правила записи программ на Object Pascal==
+
'''Синтаксис''' - правила записи конструкций, '''семантика''' - смысл конструкций.
−
'''По [http://it.mmcs.sfedu.ru/files?func=fileinfo&id=24 Шпаргалке]'''
 
−
:Пример программы, вычисляющей  длину и площадь круга.
 
−
:Общие правила записи программ на Паскале. Оформление, комментарии
 
  
−
'''PascalABC.NET'''. Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
+
== Синтаксис и семантика ЯП ==
 +
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
  
−
<small>'''Лекция 2'''</small>
+
=== Определения ===
−
==Синтаксис и семантика ЯП==
+
'''Синтаксис''' — формальные правила описания конструкций ЯП.
−
<h3>Определения</h3>
 
−
'''''Синтаксис''''' — формальные правила описания конструкций ЯП.
 
  
−
'''''Семантика''''' — описывает смысл конструкций ЯП, а также задает ряд ограничений.
+
'''Семантика''' — описывает смысл конструкций ЯП, а также задает ряд ограничений.
  
−
<h3>Способы описания синтаксиса</h3>
+
=== Способы описания синтаксиса ===
  
 
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
 
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
  
−
<tt>'''Пример.'''</tt>
+
''<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>
−
:так называемый '''''нетерминал''''' ('''''нетерминальный символ''''').
+
:так называемый '''нетерминал''' ('''нетерминальный символ''').
 
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>)
 
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>)
  
 
* ''РБНФ'' (Расширенные БНФ)
 
* ''РБНФ'' (Расширенные БНФ)
  
−
:'''[]''' — 0 или 1 повторение.  
+
:'''[]''' — 0 или 1 повторение.  
−
:'''{}''' — 0 и более повторений
+
:'''{}''' — 0 и более повторений
  
−
<tt>'''Пример.'''</tt>
+
''<u>Пример</u>.''
 
  <идентификатор> ::= <буква> {<буква> | <цифра>}
 
  <идентификатор> ::= <буква> {<буква> | <цифра>}
 +
 
* ''Синтаксические диаграммы'' (Вирт, Паскаль)
 
* ''Синтаксические диаграммы'' (Вирт, Паскаль)
  
−
 
+
'''Грамматика языка''' — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
−
'''''Грамматика языка''''' — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
 
 
:Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила.
 
:Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила.
−
 
  
 
'''Замечание 1.''' Способы 1-3 эквивалентны.
 
'''Замечание 1.''' Способы 1-3 эквивалентны.
Строка 111: Строка 164:
 
'''Замечание 2.''' Синтаксис определяет лексемы языка.
 
'''Замечание 2.''' Синтаксис определяет лексемы языка.
  
−
 
+
=== Лексемы Паскаля ===
−
<h3>Лексемы Паскаля</h3>
 
  
 
# ''спецсимволы: '' <tt>''':= += *'''</tt>
 
# ''спецсимволы: '' <tt>''':= += *'''</tt>
Строка 123: Строка 175:
 
::<span style="color: green">//...</span>
 
::<span style="color: green">//...</span>
  
−
<h3>[http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных ЯП]</h3>
+
== Переменные и их описание ==
−
(самостоятельно на форуме)
 
−
 
 
−
 
 
−
==Переменные и их описание==
 
  
−
<h3>Основные сведения</h3>
+
=== Основные сведения ===
  
−
'''''Переменная''''' — это ячейка памяти компьютера, имеющая ''имя'' и ''тип''.
+
'''Переменная''' — это ячейка памяти компьютера, имеющая ''имя'' и ''тип''.
 
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
 
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
  
−
В языке Pascal любая переменная перед использованием должна быть описана.
+
В языке ''Pascal'' любая переменная перед использованием должна быть описана. <br />
−
 
 
 
Обычно переменные описываются в '''''разделе описаний'''''.
 
Обычно переменные описываются в '''''разделе описаний'''''.
  
−
 
+
<xh4> Синтаксис в виде РБНФ </xh4>
−
'''Синтаксис в виде РБНФ'''
+
  <программа> ::= ['''program''' <имя>;]  
−
  <программа>::= ['''program''' <имя>;]  
 
 
                 <раздел описаний>  
 
                 <раздел описаний>  
 
                 '''begin'''
 
                 '''begin'''
 
                   <операторы>
 
                   <операторы>
 
                 '''end.'''
 
                 '''end.'''
−
  <операторы>::= <оператор>{; <оператор>}
+
  <операторы> ::= <оператор>{; <оператор>}
−
  <раздел описаний>::= {<секция раздела описаний>}
+
  <раздел описаний> ::= {<секция раздела описаний>}
−
  <секция раздела описаний>::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
+
  <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
 
   
 
   
−
<tt>'''Пример секции описания переменных.'''</tt>
+
''<u>Пример</u> секции описания переменных.''
−
<source lang="Pascal">var
+
<source lang="Pascal">
−
  a,b: real;
+
var
−
  i: integer;</source>
+
  a,b: real;
 +
  i: integer;
 +
</source>
  
−
  <секция описания переменных>::= '''var'''<подсекция>{< подсекция>}
+
  <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>}
−
  <подсекция>::= <список имен>: <тип>;
+
  <подсекция> ::= <список имен>: <тип>;
−
  <список имен>::= <имя>{,<имя>}
+
  <список имен> ::= <имя>{,<имя>}
−
  <тип>::= <имя>
+
  <тип> ::= <имя>
  
 +
=== Внутриблочные переменные ===
  
−
<h3>Внутриблочные переменные</h3>
+
В PascalABC.NET возможно ''внутриблочное'' описание переменных:
  
−
В PascalABC.NET возможно внутриблочное описание переменных:
+
<source lang="Pascal">
−
 
+
begin
−
<source lang="Pascal">begin
 
 
   var i,j: integer;
 
   var i,j: integer;
 +
  var r: real := 5.2;
 +
  var Pi := 3.14;
 +
</source>
  
−
  var r: real:=5.2;
+
В последнем случае происходит '''''автоопределение''''' типов.
−
 
 
−
  var Pi:=3.14;</source>
 
  
−
В последнем случае происходит ''автоопределение'' типов.
+
== Основные типы ==
−
 
 
−
(синтаксис  внутриблочных описаний на дом)
 
−
 
 
−
 
 
−
==Типы==
 
 
* ''Целые''
 
* ''Целые''
−
:integer (4 байта)
+
:<tt>'''integer'''</tt> (4 байта)
−
:shortint (1)
+
:'''<tt>int64</tt>''' (8)
−
:smallint (2)
+
:'''<tt>byte</tt>''' (1)
−
:int64 (8)
 
  
 
* ''Вещественные''
 
* ''Вещественные''
−
:real (8)
+
:'''<tt>real</tt>''' (8)
−
:single (4)
 
  
 
* ''Символьные''
 
* ''Символьные''
−
: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]
  
 
* ''Логический''
 
* ''Логический''
−
:boolean (1) | ['''True''' '''False''']
+
:'''<tt>boolean</tt>''' (1) ['''<tt>''True''</tt>''' '''<tt>''False''</tt>''']
−
 
 
−
 
 
−
==Основные операторы. Их синтаксис и семантика.==
 
−
 
 
−
<H3>Оператор присваивания :=</H3>
 
−
 
 
−
<h4>Синтаксис</h4>
 
−
<переменная> ''':=''' <выражение>
 
−
 
 
−
<tt>'''Пример использования оператора присваивания.'''</tt>
 
−
a ''':=''' ( 3 + 5 ) * 8;
 
−
b := a + 2;
 
−
 
 
−
<h4>Семанитика</h4>
 
−
Вычисляется выражение в правой части, при этом вместо имен переменных подставляются их значения.
 
−
Затем результат вычисления записывается в переменную в правой части.
 
−
 
 
−
'''Ограничение.''' Тип выражения должен быть ''совместим по присваиванию'' с переменной.
 
−
Например:
 
−
*одинаковые типы совместимы.
 
−
*выражение типа integer можно присвоить переменной типа real, обратное неверно.
 
−
 
 
−
<h4>Операторы присваивания += и *=</h4>
 
−
 
 
−
<tt>'''Пример.'''</tt>
 
−
d += 1; //прибавить 1 к d
 
−
d *= 2; //умножить d на 2
 
−
 
 
−
<small>'''Лекция 3'''</small>
 
−
<h4>Примеры использования :=</h4>
 
−
 
 
−
*<tt>'''Перемена местами двух значений.'''</tt>
 
−
:<tt>Дано:  x, y;</tt>
 
−
  <source lang="Pascal">
 
−
var x, y: integer;
 
−
begin
 
−
  read( x, y );
 
−
  var v:= x;
 
−
  x:=y;
 
−
  y:=v;
 
−
  writeln ( x, ' ', y );
 
−
end.
 
−
</source>
 
−
 
 
−
Это стандартное решение.
 
−
В PascalABC.NET на основе этого алгоритма определена стандартная процедура Swap( x, y ).
 
−
 
 
−
Однако, существуют и другие решения. Например:
 
−
<source lang="Pascal">
 
−
var x, y: integer;
 
−
begin
 
−
  read( x, y );
 
−
  x:=x + y;
 
−
  y:=x - y;
 
−
  x:=x - y;
 
−
  writeln ( x, ' ', y );
 
−
end.
 
−
</source>
 
−
 
 
−
 
 
−
* <tt>'''Использование промежуточных переменных в вычислениях.'''</tt>
 
−
:<tt>Дано:  x: real;
 
−
:Найти:  x<sup>15</sup>;</tt>
 
−
 
 
−
<tt>'''Решение 1.'''</tt>
 
−
<source lang="Pascal">
 
−
y:= x*x;
 
−
z:= y*y;
 
−
t:= z*z;
 
−
p:= t*z;
 
−
q:= p*x*y;
 
−
</source>
 
−
<tt>'''Решение 2.'''</tt>
 
−
<source lang="Pascal">
 
−
y:= x*x;
 
−
z:= y*x;
 
−
t:= z*y;
 
−
p:= t*t*t;
 
−
</source>
 
−
<tt>'''Решение 3.'''</tt>
 
−
<source lang="Pascal">
 
−
y:= x*x;
 
−
x:= x*y*y;
 
−
t:= x*x*x;
 
−
</source>
 
−
 
 
−
Заметим, что в первом решении используется 6 операций умножения, в во 2м и 3м — 5. Возникает задача:
 
−
:'''''найти x<sup>n</sup> за минимальное число ходов.'''''
 
−
:Об этом читай [http://it.mmcs.sfedu.ru/forum?func=view&id=22350&catid=1 тему].
 
−
 
 
−
<H3>Оператор ввода</H3>
 
−
 
 
−
<h4>Синтаксис</h4>
 
−
'''read''' (<список переменных>) | '''readln''' (<список переменных>)
 
−
 
 
−
С процедурой ввода связан ряд ''ошибок'' (например, если переменная используется в качестве делителя и вводится 0, или если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.
 
−
 
 
−
<h4>Обработка ошибок ввода</h4>
 
−
 
 
−
Обработка ошибок ввода
 
−
 
 
−
<h3>Оператор вывода</h3>
 
−
 
 
−
Вывод по формату :a и :a:b
 
−
 
 
−
Вывод с помощью writelnFormat
 
−
 
 
−
<H3>Условный оператор</H3>
 
−
 
 
−
Синтаксис, семантика
 
−
 
 
−
'''Примеры'''
 
−
 
 
−
# Поиск min(a, b)
 
−
# Упорядочение a, b по возрастанию. Необходимость составного оператора. Синтаксис, семантика
 
−
# Вычисление функции по нескольким взаимоисключающим веткам и цепочечные if
 
−
# Найти среднее среди a, b,c (a, b,c попарно не равны)
 
−
 
 
−
Самостоятельно
 
−
 
 
−
# Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику
 
−
# Является ли 4-угольник ABCD корректно заданным
 
−
 
 
−
<small>'''Лекция 4'''</small>
 
−
<h3>Арифметические выражения</h3>
 
−
 
 
−
Операции div и mod. x div y = x/y, округленное до ближайшего целого, x mod y = x - (x div y)*y. Примеры использования.
 
−
 
 
−
Порядок действий в арифметических выражениях
 
−
 
 
−
Тип арифметического выражения
 
−
 
 
−
Стандартные функции. Вычисление степени x^y.
 
−
Логические выражения
 
−
 
 
−
Операции and, or, not, xor. Таблицы истинности.
 
−
 
 
−
Сокращенное использование логических выражений
 
−
 
 
−
Таблица приоритетов операций
 
−
 
 
−
# унарные
 
−
# * / div mod and shl shr
 
−
# + - or xor
 
−
# in отношения
 
−
 
 
−
Логические переменные. Пример с определением того, лежит ли точка на границе прямоугольника
 
−
 
 
−
Побитовые and, or, xor.
 
−
 
 
−
Операции shl, shr
 
−
 
 
−
<h3>Оператор case выбора варианта</h3>
 
−
 
 
−
Синтакстис, семантика
 
−
 
 
−
Примеры
 
−
 
 
−
# День недели
 
−
# цифра или буква
 
−
 
 
−
<small>'''Лекция 5'''</small>
 
−
<h3>Циклы с предусловием (while) и постусловием (repeat)</h3>
 
−
 
 
−
Заголовок, тело, итерации
 
−
 
 
−
Синтаксис и семантика
 
−
 
 
−
Отличия
 
−
 
 
−
Примеры
 
−
 
 
−
# Факториал
 
−
# Сумма четных двузначных
 
−
 
 
−
Моделирование repeat с помощью while
 
−
 
 
−
Моделирование while с помощью repeat
 
−
 
 
−
Зацикливание
 
−
 
 
−
<h3>Оператор цикла с параметром (for)</h3>
 
−
 
 
−
Синтаксис, семантика: моделирование for с помощью while, ограничения
 
−
 
 
−
Примеры
 
−
 
 
−
# Факториал
 
−
# Сумма четных двузначных
 
−
 
 
−
<h3>Примеры использования циклов I</h3>
 
−
 
 
−
#Табулирование функции. использование for и while
 
−
 
 
−
Погрешность округления вещественных чисел и вычислительная погрешность.
 
−
 
 
−
<small>'''Лекция 6'''</small>
 
−
<h3>Примеры использования циклов II</h3>
 
−
 
 
−
Поиск минимального среди введенных.
 
−
 
 
−
Рекуррентные последовательности.
 
−
 
 
−
Числа Фибоначчи.
 
−
 
 
−
Суммирование рядов (конечных и бесконечных).
 
−
 
 
−
Алгоритм Евклида нахождения НОД.
 
−
 
 
−
Разложение целого числа на простые множители.
 
−
 
 
−
<small>'''Лекция 7'''</small>
 
−
<h3>Примеры использования циклов III</h3>
 
−
 
 
−
Поиск заданного значения среди введенных.
 
−
 
 
−
Операторы break и continue. Как обойтись без них.
 
−
 
 
−
Схема Горнера.
 
−
 
 
−
Поиск нуля функции на отрезке.
 
−
 
 
−
<small>'''Лекция 8'''</small>
 
−
<H3>Вложенные циклы</H3>
 
−
 
 
−
Метод окаймления и метод последовательной детализации.
 
−
 
 
−
Переборные задачи. Необходимость оптимизации самого внутреннего цикла.
 
−
 
 
−
Вспомогательные алгоритмы и их параметры. Подпрограммы. Мотивировка введения подпрограмм.
 
−
 
 
−
<small>'''Лекция 9'''</small>
 
−
==Процедуры==
 
−
 
 
−
Пример вычисления среднего арифметического и среднего геометрического.
 
−
 
 
−
Синтаксис описания процедуры. Синтаксис вызова процедуры.
 
−
 
 
−
Входно-выходные параметры. Процедура Swap.
 
−
 
 
−
Формальные и фактические параметры. Семантические правила при вызове.
 
−
 
 
−
<H3>Функции</H3>
 
−
 
 
−
Синтаксис. Вызов функции. Переменная Result.
 
−
 
 
−
Примеры: Sign, ReadInteger и т.п., SumN.
 
−
 
 
−
Сравнение с процедурами на примере Sign.
 
−
 
 
−
Нежелательность var-параметров в функциях.
 
−
 
 
−
Стандартные подпрограммы с передачей по ссылке: readln, Inc, Dec.
 
−
 
 
−
<H3>Локальные и глобальные переменные</H3>
 
−
 
 
−
Инициализация глобальных и локальных переменных значениями по умолчанию.
 
−
 
 
−
Понятие пространства имен.
 
−
 
 
−
Глобальные переменные и побочный эффект.
 
−
 
 
−
<small>'''Лекция 10'''</small>
 
−
 
 
−
Понятие области видимости и времени жизни объекта.
 
−
 
 
−
Изменение глобальной переменной как побочный эффект. Нежелательность такого изменения. При необходимости изменения глобальной переменной - передать ее как параметр.
 
−
 
 
−
Принцип локальности: чем локальнее объявлена переменная, тем лучше. Распространение принципа локальности на внутриблочные переменнные: вспомогательные переменные, используемые в блоке алгоритма, следует делать внутриблочными.
 
−
 
 
−
Понятие ссылки как другого имени объекта. Внутренний механизм передачи параметра по ссылке.
 
−
 
 
−
Перегрузка имен подпрограмм (на примере swap).
 
−
 
 
−
<small>'''Лекция 11'''</small>
 
−
 
 
−
Параметры по умолчанию - на примере DoOp(a,b: integer; var res: integer; op: char := '+').
 
−
 
 
−
Предварительное объявление подпрограмм.
 
−
 
 
−
==Процедурные переменные==
 
−
 
 
−
Процедурные переменные как параметры подпрограмм. Функции обратного вызова (callback).
 
−
 
 
−
Пример.
 
−
<source lang="delphi">
 
−
procedure DoActions(Act1, Act2, Act3: procedure);
 
−
begin
 
−
  Act1;
 
−
  Act2;
 
−
  Act3;
 
−
end;
 
−
</source>
 
−
 
 
−
Пример. Вычисление определённого интеграла методом прямоугольников - Integral(a,b,N,f)
 
−
 
 
−
Вызов нескольких действий. Операции += и -= для процедурных переменных.
 
−
 
 
−
Оператор exit досрочного завершения подпрограммы
 
−
 
 
−
<small>'''Лекция 12'''</small>
 
−
==Методы разработки подпрограмм==
 
−
 
 
−
Метод "сверху вниз" и метод "снизу вверх" (на примере таблицы простых чисел).
 
−
 
 
−
Когда эффективен каждый метод:
 
−
 
 
−
* сверху-вниз - когда задача четко поставлена и имеется четкий алгоритм ее решения;
 
−
* сниз-вверх - когда задача нечетко поставлена. когда решается группа взаимосвязанных задач из дной области, когда в задаче нет четко выделенного главного алгоритма, когда необходимо приступать к решению задачи, попутно уточняя алгоритм.
 
−
 
 
−
<H3>Вызов подпрограммы на этапе выполнения</H3>
 
−
 
 
−
Понятие программного стека.
 
−
 
 
−
Запись активации, ее структура.
 
−
 
 
−
Алгоритм вызова подпрограммы на этапе выполнения.
 
−
 
 
−
<small>'''Лекция 13'''</small>
 
−
 
 
−
Пример, иллюстрирующий алгоритм вызова процедуры.
 
−
 
 
−
Замечания:
 
−
 
 
−
* о накладных расходах, связанных с вызовом маленьких и больших подпрограмм
 
−
* о проблеме переполнения программного стека при наличии больших локальных переменных и при передаче больших локальных переменных п значению
 
−
* о проблеме доступа к глобальным переменным
 
−
 
 
−
==Модули==
 
−
 
 
−
Определение
 
−
 
 
−
Структура модуля с разделами интерфейса и реализации.
 
−
 
 
−
Принцип сокрытия информации.
 
−
 
 
−
Преимущества разделения модуля на интерфейс и реализацию.
 
−
 
 
−
<small>'''Лекция 14'''</small>
 
−
 
 
−
Упрощенная структура модуля.
 
−
 
 
−
Разделы инициализации и финализации.
 
−
 
 
−
Схема компиляции программы с модулями.
 
−
 
 
−
Алгоритм поиска имен в модулях. Модуль как пространство имен.
 
−
 
 
−
Системный модуль PABCSystem
 
−
 
 
−
<small>'''Лекция 15'''</small>
 
−
 
 
−
Документирующие комментарии ///
 
−
 
 
−
Библиотеки. Отличие библиотек от модулей. Подключение библиотек в PascalABC.NET.
 
−
 
 
−
Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.
 
−
 
 
−
Использование перечислимого типа в for и case.
 
−
 
 
−
==Массивы==
 
−
 
 
−
Понятие структурированного типа данных.
 
−
 
 
−
Определение массива.
 
−
 
 
−
Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.
 
−
 
 
−
<small>'''Лекция 16'''</small>
 
−
 
 
−
Обращение к элементам массивов.
 
−
 
 
−
Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
 
−
 
 
−
Динамические массивы. Хранение в памяти.
 
−
 
 
−
Инициализация массивов.
 
−
 
 
−
Присваивание массивов. Сравнение массивов.
 
−
 
 
−
Присваивание a := nil для динамических массивов.
 
−
 
 
−
Цикл foreach.
 
−
 
 
−
Именная и структурная эквивалентность типов.
 
−
 
 
−
<small>'''Лекция 17'''</small>
 
−
<H3>Массивы как параметры подпрограмм</H3>
 
−
 
 
−
При передаче статического массива должна соблюдаться именная эквивалентность
 
−
<source lang="delphi">
 
−
  procedure xxx(a: array [1..100] of integer); // неверно
 
−
 
−
  type IArr = array [1..100] of integer;
 
−
  procedure yyy(a: IArr);
 
−
</source>
 
−
Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово <tt>const</tt>, которое также запрещает изменять данные внутри п/п.
 
−
<source lang="delphi">
 
−
 
 
−
  procedure zzz(const a: IArr);
 
−
  procedure sss(var a: IArr);
 
−
 
 
−
</source>
 
−
Динамический массив
 
−
можно передавать в виде <tt>array of integer</tt>, т.к. для него определена структурная эквивалентность типов.
 
−
<source lang="delphi">
 
−
  procedure ttt(a: array of integer);
 
−
</source>
 
−
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
 
−
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
 
−
Массивы как возвращаемые значения функции
 
−
 
 
−
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
 
−
 
 
−
<h3>Переменное число параметров подпрограмм</h3>
 
−
 
 
−
П/п можно создавать с переменным количеством параметров.
 
−
Для этого исп. ключевое слово params.
 
−
При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним.
 
−
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
−
 
 
−
<small>'''Лекция 18'''</small>
 
−
==Шаблоны подпрограмм==
 
−
 
 
−
Часто требуется выполнять одно и то же действие для разных типов данных.
 
−
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
−
 
 
−
Выход - шаблоны.
 
−
 
 
−
Пример:
 
−
 
 
−
  procedure Print<T> (array of T);
 
−
 
 
−
В момент вызова п/п происходит:
 
−
 
 
−
* выведение типов шаблона по фактическим параметрам
 
−
* инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.
 
−
 
 
−
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
−
 
 
−
<H3>Задачи на одномерные массивы</H3>
 
−
 
 
−
* инвертирование массива (шаблон)
 
−
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
−
 
 
−
можно с for и break,
 
−
 
 
−
можно и другим способом - с while
 
−
 
 
−
* поиск с барьером (шаблон). Его преимущества
 
−
* минимальный элемент массива и его индекс
 
−
* слияние двух упорядоченных массивов в один упорядоченный (барьер)
 
−
* сдвиг элементов массива влево (шаблон)
 
−
 
 
−
знакомство со значением default(T), Т - тип
 
−
 
 
−
<small>'''Лекция 19'''</small>
 
−
 
 
−
<h3>Задачи на одномерные массивы</h3>
 
−
 
 
−
pas-файл с задачами
 
−
 
 
−
doc-файл
 
−
 
 
−
используется тип IArr =  array [1..size] of integer
 
−
 
 
−
* сдвиг элементов массива вправо (ShiftRight)
 
−
 
 
−
[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]
 
−
 
 
−
* циклический сдвиг элементов массива вправо (CycleShiftRight)
 
−
* удаление элемента по заданному индексу (Delete)
 
−
* вставка элемента по заданному индексу (Insert)
 
−
 
 
−
<H3>Задачи с процедурными переменными в качестве параметров</H3>
 
−
 
 
−
Определяется тип IUnPred = function (x: integer): boolean
 
−
 
 
−
* поиск элемента по заданному условию (Find)
 
−
* количество элементов, удовлетворяющих условию (Count)
 
−
* условный минимум (MinElem)
 
−
* удаление всех элементов, удовлетворяющих условию (DeleteAll)
 
−
 
 
−
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
 
−
 
 
−
<small>'''Лекция 20'''</small>
 
−
==Сортировки==
 
−
 
 
−
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)
 
−
 
 
−
* '''Пузырьковая'''
 
−
 
 
−
Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.
 
−
 
 
−
* '''Вставками''' (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)
 
−
 
 
−
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
 
−
Асимптотическая сложность алгоритмов
 
−
 
 
−
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
 
−
 
 
−
    c1*f(n) ≤ число шагов ≤ c2*f(n)
 
−
 
 
−
'''Замечание 1.''' Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n<sup>2</sup>).
 
−
 
 
−
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
 
−
 
 
−
<small>'''Лекция 21'''</small>
 
−
==Алгоритм бинарного поиска в отсортированном массиве==
 
−
 
 
−
Его асимптотическая сложность - Θ(logn).
 
−
Двумерные массивы
 
−
 
 
−
Двумерный массив как матрица (соответствие индексов строкам и столбцам)
 
−
 
 
−
Элементы строки. Элементы столбца (рисунки)
 
−
 
 
−
Понятие замороженного индекса
 
−
 
 
−
<H3>Задачи на двумерные массивы</H3>
 
−
 
 
−
* Вывод матрицы
 
−
** внешний цикл по строкам
 
−
** если внешним сделать цикл по столбцам будет выведена транспонированная матрица
 
−
 
 
−
* Сумма элементов в j-том столбце
 
−
 
 
−
* Сумма элементов в каждом столбце
 
−
** использование функции для нахождения суммы в j-ом столбце
 
−
* Минимальный элемент в каждой строке
 
−
** в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.
 
−
 
 
−
'''Замечание.''' Решать такие задачи можно и реализуя алгоритм полностью,  и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.
 
−
 
 
−
* Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
 
−
 
 
−
<small>'''Лекция 22'''</small>
 
−
 
 
−
* Поиск элемента в матрице
 
−
 
 
−
если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,
 
−
 
 
−
иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА
 
−
 
 
−
==Записи==
 
−
 
 
−
<source lang="delphi">
 
−
type <имя записи>= record
 
−
  <поля записи>
 
−
end;
 
−
</source>
 
−
 
 
−
Поля записей
 
−
 
 
−
Инициализация записей при описании (на примере Student)
 
−
 
 
−
Доступ к полям записей. Точечная нотация.
 
−
 
 
−
'''Замечание.''' Для записей имеет место именная эквивалентность типов.
 
−
 
 
−
Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).
 
−
 
 
−
Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке  (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.
 
−
 
 
−
Оператор with.
 
−
 
 
−
<source lang="delphi">
 
−
with <переменная типа запись> do
 
−
begin
 
−
  <поле>:=<значение>
 
−
end;
 
−
</source>
 
−
 
 
−
Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)
 
−
 
 
−
<H3>Методы в записях</H3>
 
−
 
 
−
На примере Student.Print.
 
−
 
 
−
Запись как пространство имен
 
−
 
 
−
Запись выступает для своих полей и методов в качестве модуля (поскольку является набором данных и связанных с ними процедур и функций, оформленных как единое целое).
 
−
 
 
−
Методы работают в некотором окружении, в роли которого выступают поля записи и другие методы.
 
−
 
 
−
Создается окружение при описании переменной типа запись.
 
−
 
 
−
* Сравнение s.Print и Print(s)
 
−
 
 
−
'''s.Print''' - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.
 
−
 
 
−
'''Print(s)''' - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.
 
−
 
 
−
* Метод Init - инициализатор полей записи.
 
−
 
 
−
<small>'''Лекция 23'''</small>
 
−
==Создание простейших графических объектов==
 
−
 
 
−
<source lang="delphi">
 
−
RPoint = record x, y: integer end;
 
−
RRectangle = record p1,p2: RPoint end;
 
−
</source>
 
−
 
 
−
Для каждого типа определяются методы Print, Draw, MoveOn
 
−
 
 
−
<H3>Записи как средство упаковки параметров</H3>
 
−
 
 
−
'''Пример.'''
 
−
Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:
 
−
 
 
−
<source lang="delphi">
 
−
Rectangle(x1,y1, x2,y2: integer)
 
−
Rectangle(p1,p2: RPoint)
 
−
Rectangle(r: RRectangle)
 
−
 
 
−
Line(x1,y1, x2,y2: integer)
 
−
Line(p1,p2: RPoint)
 
−
Line(r: RRectangle)
 
−
</source>
 
−
 
 
−
<H3>Переменная типа запись как объект</H3>
 
−
 
 
−
В модуле можно выносить реализацию методов записи в раздел реализации. При этом в разделе интерфейса внутри определения типа запись описываются только заголовки методов, а в разделе реализации перед именем метода необходимо писать <Имя записи>.
 
−
 
 
−
Поля записи как состояние объекта.
 
−
 
 
−
Методы записи как действия, воздействующие на состояние объекта.
 
−
 
 
−
Методы делятся на две категории
 
−
* меняющие состояние объекта (MoveOn для RPoint)
 
−
* осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)
 
−
 
 
−
Сортировка массива записей.
 
−
 
 
−
<small>'''Лекция 24'''</small>
 
−
==Индексная сортировка==
 
−
 
 
−
Часто физически переставлять элементы массива или вообще невозможно, или долго (в силу достаточно большого размера, например).
 
−
В этом случае удобно использовать ''перестановку индексов'' вместо перестановки самих элементов.
 
−
 
 
−
Идея заключается в том, чтобы описать '''индексный массив''' index, который взаимооднозначно сопоставляет ''реальным'' индексам элемента ''виртуальные'' таким образом, чтобы относительно ''виртуальных'' массив оказался упорядоченным.
 
−
 
 
−
----
 
−
 
 
−
'''Пример.'''
 
−
 
 
−
Дан массив целых (с реальными индексами):
 
−
  '''5'''[1]  '''15'''[2]  '''3'''[3]  '''1'''[4]  '''9'''[5]  '''8'''[6]  '''20'''[7]  '''12'''[8]
 
−
 
 
−
А так выглядит отсортированный массив по виртуальным индексам:
 
−
  '''1'''[1]  '''3'''[2]  '''5'''[3]  '''8'''[4]  '''9'''[5]  '''12'''[6]  '''15'''[7]  '''20'''[8]
 
−
 
 
−
Т.е.
 
−
  index[1] = 4
 
−
  index[2] = 3
 
−
  index[3] = 1
 
−
  index[4] = 6
 
−
  index[5] = 5
 
−
  index[6] = 8
 
−
  index[7] = 2
 
−
  index[8] = 7
 
−
 
 
−
----
 
−
Соответственно, алгоритм сортировки меняется таким образом, что вместо перемены местами самих элементов упорядочиваемого массива меняется '''содержимое элементов index'''.
 
−
 
 
−
Вначале удобно положить элементы index соответствующими '''тождественной''' подстановке (т.е. a[i] = i).
 
−
<source lang="delphi">
 
−
type CmpFunc = function (const s1,s2: Student): boolean;
 
−
 
 
−
procedure BubbleIndexStudentSort(const a: StArr; var Index: IArr; n: integer; Cmp: CmpFunc);
 
−
begin
 
−
  for var i:=1 to n do
 
−
    Index[i] := i;
 
−
  for var i:=n downto 2 do
 
−
  for var j:=1 to i-1 do
 
−
    if Cmp(a[Index[j+1]],a[Index[j]]) then
 
−
      Swap(Index[j+1],Index[j]);
 
−
end;
 
−
 
 
−
procedure WriteArrByIndex(const a: StArr; const Index: IArr; n: integer);
 
−
begin
 
−
  for var i:=1 to n do
 
−
    writeln(a[Index[i]].name,' ',a[Index[i]].course,' ',a[Index[i]].group);
 
−
end;
 
−
</source>
 
−
 
 
−
==Множества==
 
−
 
 
−
Описание множеств. Множества-константы. Пустое множество.
 
−
 
 
−
Операции над множествами:
 
−
s1+s2 - объединение
 
−
s1*s2 - пересечение
 
−
s1-s2 - разность
 
−
s += s1
 
−
s -= s1
 
−
s *= s1
 
−
s1<s2 - строгое вложение
 
−
s1<=s2 - нестрогое вложене
 
−
s1>s2 - строгое вложение
 
−
s1<=s2 - нестрогое вложене
 
−
i in s - принадлежность
 
−
 
−
Include(s,i);
 
−
Exclude(s,i);
 
−
Вывод множеств.
 
−
 
 
−
Цикл foreach по множеству.
 
−
 
 
−
Пример использования множеств: решето Эратосфена.
 
−
Алгоритм.
 
−
 
 
−
<small>'''Лекция 25'''</small>
 
−
<H3>Алгоритм Эратосфена</H3>
 
−
 
 
−
Код алгоритма Эратосфена
 
−
<source lang="delphi">
 
−
const n = 10000;
 
−
var primes: set of byte;
 
−
begin
 
−
  primes := [2..n];
 
−
  for var i:=2 to round(sqrt(n)) do
 
−
  begin
 
−
    if not (i in primes) then
 
−
      continue;
 
−
    var x := 2*i;
 
−
    while x<=n do
 
−
    begin
 
−
      Exclude(primes,x);
 
−
      x += i;
 
−
    end;
 
−
  end;
 
−
  for var i:=0 to n do
 
−
    if i in primes then
 
−
        write(i,' ');
 
−
end.
 
−
</source>
 
−
 
 
−
<H3>Статические методы записей</H3>
 
−
<source lang="delphi">
 
−
type RRectangle = record
 
−
  class function EqualSquare(const r1,r2: RRectangle): boolean;
 
−
  class function CreateRandom: RRectangle;
 
−
end;
 
−
</source>
 
−
 
 
−
<H3>Символы</H3>
 
−
 
 
−
Коды символов. Однобайтовые и двухбайтовые кодировки.
 
−
ASCII - стандарт на символы с кодами 0..127.
 
−
Unicode.
 
−
Однобайтовые кодировки: Windows, DOS (CP866), Koi8
 
−
 
 
−
Литеральные константы-символы:
 
−
#13 - символ возврата "каретки"
 
−
#10 - символ перехода на следующую строку
 
−
#9  - символ табуляции
 
−
 
 
−
<H4>Стандартные подпрограммы работы с символами</H4>
 
−
OrdUnicode(c)
 
−
ChrUnicode(i)
 
−
Succ(c)
 
−
Pred(c)
 
−
Inc(c,5)
 
−
Dec(c,5)
 
−
Ord(c)
 
−
Chr(i)
 
−
UpperCase(c)
 
−
LowerCase(c)
 
−
 
 
−
Для символов с кодами 0..127
 
−
OrdUnicode(c)=Ord(c)
 
−
ChrUnicode(i)=Chr(i)
 
−
 
 
−
char - тип, содержащий ряд статических методов:
 
−
 
 
−
char.IsDigit(c)
 
−
char.IsLetter(c)
 
−
char.IsLetterOrDigit(c)
 
−
char.IsLower(c)
 
−
char.IsUpper(c)
 
−
char.ToLower(c)
 
−
char.ToUpper(c)
 
−
 
 
−
<small>'''Лекция 26'''</small>
 
−
==Строки==
 
−
 
 
−
Тип string
 
−
 
 
−
Отводится память (до 2 Гб), равная длине строки, плюс некоторая дополнительная информация
 
−
 
 
−
Строки - массивы символов, индексируемые с 1: s[i] - i - тый символ строки.
 
−
var s := 'IT'; // s[1]='I', s[2]='T'
 
−
 
 
−
Операции со строками:
 
−
 
 
−
s1+s2 
 
−
s1 += s2 
 
−
s1<s2 
 
−
...
 
−
 
 
−
<H3>Основные подпрограммы работы со строками</H3>
 
−
 
 
−
'''Length(s)''' - функция, возвращающая длину строки s
 
−
 
 
−
'''SetLength(s,n)''' - процедура, устанавливающая длину строки s равной n
 
−
 
 
−
'''Copy(s,from,len)''' - функция, возвращающая подстроку s с позиции from длины len
 
−
 
 
−
'''Insert(subs,s,form)''' - процедура, вставляющая подстроку subs в строку s с позиции from
 
−
 
 
−
'''Delete(s,from,len)''' - процедура, удаляющая из строки s len символов с позиции from
 
−
 
 
−
'''Pos(subs,s)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s или 0, если подстрока не найдена
 
−
 
 
−
'''PosEx(subs,s,from=1)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s, начиная с позиции from, или 0, если подстрока не найдена
 
−
 
 
−
'''TrimLeft(s)''' - функция, возвращающая строку s, в которой удалены все начальные пробелы
 
−
 
 
−
'''TrimRight(s)''' - функция, возвращающая строку s, в которой удалены все заключительные пробелы
 
−
 
 
−
'''Trim(s)''' - функция, возвращающая строку s, в которой удалены все удаляет все начальные и заключительные пробелы
 
−
 
 
−
<h4>Преобразование строка <-> число</h4>
 
−
 
 
−
'''Str(x,s)''' - процедура, преобразующая целое или вещественное выражение x к строковому представлению и записывающая результат в строку s
 
−
 
 
−
'''Val(s,x,errcode)''' - процедура, преобразующая строку s к целому или вещественному значению и записывающая результат в целую или вещественную переменную x. Переменная errcode  - целая; если преобразование невозможно, то в errcode содержится номер первого символа, вызвавшего ошибку
 
−
 
 
−
'''IntToStr(i)''' - функция, преобразующая целое x в строку
 
−
 
 
−
'''StrToInt(s)''' - функция, преобразующая строку s к целому; может генерировать исключение
 
−
 
 
−
'''FloatToStr(i)''' - функция, преобразующая вещественное x в строку
 
−
 
 
−
'''StrToFloat(s)''' - функция, преобразующая строку s к вещественному; может генерировать исключение
 
−
 
 
−
<H3>Некоторые задачи на строки</H3>
 
−
 
 
−
Посимвольная обработка
 
−
 
 
−
* Строка 'ABCD...XYZ'
 
−
* Сумма всех цифр в строке s
 
−
 
 
−
Использование стандартных подпрограмм
 
−
 
 
−
* Вывести индексы всех вхождений подстроки s1 в s (на Delete, PosEx)
 
−
 
 
−
==Ссылки==
 
−
*[[Конспекты|Другие конспекты]]
 

Текущая версия на 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., представленный блок-схемой.

Max flowchart.png

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. Синтаксис определяет лексемы языка.

Лексемы Паскаля

  1. спецсимволы: := += *
  2. ключевые слова (begin, end, if, for)
  3. идентификаторы (a, b1)
  4. константы (2, 'ABC', #5)
  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]
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Основы_программирования_—_Осенний_семестр;_Михалкович_С.С.;_2008;_I&oldid=4930»