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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin)
 
(не показано 128 промежуточных версий 4 участников)
Строка 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>.''
−
:Дано: x,y,z.  
+
:Дано: <tt>x, y, z</tt>.  
−
:Найти max
+
:Найти <tt>max</tt>
  
−
'''А.1.''' (''словесное описание'').
+
Алгоритм 1. (''словесное описание'')
  
−
  Если x>y и x>z, то максимум - это x
+
  Если x>y и x>z, то максимум — это x
−
  Если y>x и y>z, то максимум - это y
+
  Если y>x и y>z, то максимум — это y
−
  Если z>x и z>y, то максимум - это z
+
  Если z>x и z>y, то максимум — это z
  
−
'''А.2.''' (''псевдокод'').
+
Алгоритм 2. (''псевдокод'')
  
 
  max := x
 
  max := x
Строка 38: Строка 31:
 
  Если z<max то max := z
 
  Если z<max то max := z
  
 +
'''Эквивалентными''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.
 +
Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.
  
−
'''''Эквивалентными''''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.
 
  
−
<h3>Способы описания алгоритмов</h3>
+
'''Спецификация задачи''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
−
<ul>
 
−
<li>''словесный''</li>
 
−
<li>''псевдокод''</li>
 
−
<li>''блок-схемы''
 
−
</ul>
 
  
−
'''Пример.''' А.2., представленный блоксхемой.
+
=== Способы описания алгоритмов ===
−
[[Изображение:2.JPG|none]]
+
1. ''Словесный''
−
<ul>
 
−
<li>''диаграммы деятельности (activity diagram) UML''
 
−
</ul>
 
−
'''Пример.''' А.2., представленный диаграммой деятельности
 
−
[[Изображение:2-1.JPG|none]]
 
−
<ul>
 
−
<li>''язык программирования (ЯП)''</li>
 
−
</ul>
 
  
−
'''''Команды алгоритма''''' также называются:
+
2. ''Псевдокод''
−
:* операторы Я.
 
−
:* инструкции Я.
 
  
−
==Правила записи программ на Object Pascal==
+
3. ''Блок-схемы''
−
'''По [http://it.mmcs.sfedu.ru/files?func=fileinfo&id=24 Шпаргалке]'''
 
−
:Пример программы, вычисляющей  длину и площадь круга.
 
−
:Общие правила записи программ на Паскале. Оформление, комментарии
 
  
−
'''PascalABC.NET'''. Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
+
''<u>Пример</u>.'' А.2., представленный блок-схемой.
 +
[[Изображение:max_flowchart.png|none]]
  
−
<small>'''Лекция 2'''</small>
+
4. ''Язык программирования (ЯП)''
−
==Синтаксис и семантика ЯП==
 
−
<h3>Определения</h3>
 
−
'''''Синтаксис''''' — формальные правила описания конструкций ЯП.
 
  
−
'''''Семантика''''' — описывает смысл конструкций ЯП, а также задает ряд ограничений.
+
Для языка программирования команды алгоритма называются '''''операторами''''' или '''''инструкциями'''''.
  
−
<h3>Способы описания синтаксиса</h3>
+
=== Основные характеристики алгоритма===
 +
 
 +
* правильность работы
 +
* скорость выполнения
 +
* объем занимаемой памяти
 +
* сложность написания
 +
* возможность распараллеливания
 +
 
 +
=== Основные характеристики программы ===
 +
Те же, что и у алгоритма, а также:
 +
 
 +
* понятность при чтении
 +
* модифицируемость (легкость изменения кода)
 +
* масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
 +
* безопасность
 +
 
 +
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы.
 +
Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
 +
 
 +
=== [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.''' Синтаксис определяет лексемы языка.
  
−
 
+
=== Лексемы Паскаля ===
−
<h3>Лексемы Паскаля</h3>
 
  
 
# ''спецсимволы: '' <tt>''':= += *'''</tt>
 
# ''спецсимволы: '' <tt>''':= += *'''</tt>
Строка 121: Строка 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'''<подсекция>{< подсекция>}
−
  <подсекция>::= <список имен>: <тип>;
+
  <подсекция> ::= <список имен>: <тип>;
−
  <список имен>::= <имя>{,<имя>}
+
  <список имен> ::= <имя>{,<имя>}
−
  <тип>::= <имя>
+
  <тип> ::= <имя>
−
===Внутриблочные переменные===
 
  
−
В PascalABC.NET возможно внутриблочное описание переменных:
+
=== Внутриблочные переменные ===
  
−
<source lang="Pascal">begin
+
В PascalABC.NET возможно ''внутриблочное'' описание переменных:
 +
 
 +
<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>''']
−
 
 
−
 
 
−
==Основные операторы. Их синтаксис и семантика==
 
−
 
 
−
===Оператор присваивания := ===
 
−
 
 
−
<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 тему].
 
−
 
 
−
===Оператор ввода===
 
−
 
 
−
<h4>Синтаксис</h4>
 
−
'''read''' (<список переменных>) | '''readln''' (<список переменных>)
 
−
 
 
−
<h4>Семантика</h4>
 
−
Происходит считывание данных с клавиатуры и запись их в переменные из <списка переменных>. Вводить данные нужно либо через пробел, либо по нажатию <Enter>, при этом программа не перейдет к выполнению следующего оператора, пока не будут считаны все данные.
 
−
 
 
−
С процедурой ввода связан ряд ''ошибок'' (например, если переменная используется в качестве делителя и вводится 0, или если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.
 
−
 
 
−
<h4>Обработка ошибок ввода</h4>
 
−
 
 
−
Операторы, которые могут получать ошибку, заключаются специальный охранный блок <tt>'''try'''</tt>.
 
−
 
 
−
'''''Синтаксис.'''''
 
−
<source lang="Pascal">
 
−
try
 
−
  ...
 
−
  readln(a);
 
−
  ...
 
−
except
 
−
  <обработка ошибки>
 
−
end;
 
−
<продолжение работы>
 
−
</source>
 
−
 
 
−
'''''Семантика.'''''
 
−
 
 
−
Если внутри блока '''try''' происходит ошибка выполнения, то все последующие операторы в блоке игнорируются и выполнение программы переходит к блоку '''except'''. По выходе из '''except''' программа продолжает работу.
 
−
 
 
−
Если ошибки не происходит, то выполняются все операторы в блоке '''try''', блок '''except''' не выполняется и программа продолжает работу.
 
−
 
 
−
===Оператор вывода===
 
−
<h4>Синтаксис</h4>
 
−
'''write'''( <список выражений> ) | '''writeln'''( <список выражений> )
 
−
 
 
−
<h4>Семантика</h4>
 
−
Выражения в списке вычисляются и тих значения выводятся на экран.
 
−
В случае <tt>writeln</tt> после выводао существляется переход на новую строку.
 
−
 
 
−
<h4>Форматы вывода</h4>
 
−
После каждого выражения в списке вывода можно использовать формат вывода в виде <tt>''':a'''</tt>, где a — выражение целого типа.
 
−
После вещественного типа — <tt>''':a:b'''</tt>
 
−
 
 
−
<tt>'''a'''</tt> задает ширину поля вывода ( выравнивание по правому краю ).
 
−
<br><tt>'''b'''</tt> — количество знаков в дробной части.
 
−
 
 
−
<h4>Вывод с помощью write[ln]Format</h4>
 
−
'''''Синтаксис.'''''
 
−
'''writelnFormat'''( '<форматная строка>', <список выражений> )
 
−
<tt>'''Пример''' вывода с использованием форматной строки</tt>
 
−
<source lang="Pascal">writelnFormat( '{0} * {1} = {2}', a, b, a*b );</source>
 
−
<tt>Будет выведено:</tt>
 
−
a * b = '''a*b'''
 
−
 
 
−
В форматной строке тоже можно использовать формат вывода.
 
−
<br><tt>{0, 10}</tt> — 10 это ширина поля вывода
 
−
<br><tt>{0, 10:f3}</tt> — 3 это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).
 
−
 
 
−
===Условный оператор===
 
−
<h4>Синтаксис</h4>
 
−
'''if''' <условие> '''then''' <оператор<sub>1</sub>>
 
−
              '''else''' <оператор<sub>2</sub>>
 
−
 
 
−
<h4>Семантика</h4>
 
−
[[Изображение: If.jpg]]
 
−
<h4>Примеры использования для решения задач</h4>
 
−
 
 
−
<tt>'''Пример 1.''' Нахождение минимума.
 
−
<br>Дано: x,y; <br> Найти: min;</tt>
 
−
<source lang="Pascal">if x > y then
 
−
  min:= y
 
−
else
 
−
  min:= x;</source>
 
−
<tt>'''Пример 2.''' Упорядочение a, b по возрастанию.</tt>
 
−
<br>Ясно, что если a>b, — нужно [http://it.mmcs.rsu.ru/wiki/index.php/%D0%9A%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9_%D0%BA%D1%83%D1%80%D1%81%D0%B0_%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_1_%D1%81%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D1%80_%D0%98%D0%A2#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80.D1.8B_.D0.B8.D1.81.D0.BF.D0.BE.D0.BB.D1.8C.D0.B7.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F_:.3D поменять их местами]. <br>Но тут одним оператором не обойтись.
 
−
Для этого можно использовать '''''составной оператор''''' — один или больше операторов, заключенных в пару <tt>'''begin'''  - '''end''';</tt>:
 
−
<source lang="Pascal">if a > b then
 
−
begin
 
−
  var v:=b;
 
−
  b:=a;
 
−
  a:=v;
 
−
end;
 
−
</source>
 
−
 
 
−
<tt>'''Пример 3.''' Вычисление функции по взаимоисключающим веткам.</tt>
 
−
<br><math> y = \begin{cases} x, & x < 2 \\ x^2, & 2 < x < 3 \\ 1-x, & x \ge\; 3 \end{cases}</math>
 
−
<source lang="Pascal">if x < 2then
 
−
  y:= x
 
−
else
 
−
  if x < 3 then
 
−
    y:= x * x
 
−
  else
 
−
    y:= 1 - x;</source>
 
−
 
 
−
'''Замечание.'''Если по ветви '''<tt>else</tt>''' располагается другой оператор '''<tt>if</tt>''', то говорят, что возникает '''''цепочка вложенных операторов''''' '''<tt>if</tt>'''.
 
−
 
 
−
<tt>'''Пример 4.''' Найти среднее среди a, b,c (a, b,c попарно не равны).</tt>
 
−
Эта задача имеет несколько вариантов решения.
 
−
<source lang="Pascal">if a<b then
 
−
  if a<c then
 
−
    if b<c then
 
−
      sr:=b
 
−
    else
 
−
      sr:=c
 
−
  else
 
−
    sr:=a
 
−
else
 
−
  if a>c then
 
−
    if b>c then
 
−
      sr:=b
 
−
    else
 
−
      sr:=c
 
−
  else sr:=a;</source>
 
−
Очевидно, это не самое лучшее решение. <br>Можно воспользоваться стандартными функциями сравнения.
 
−
<source lang="Pascal">sr:= min( a, b );
 
−
if sr<c then
 
−
  sr:=min( max(a,b), c );</source>
 
−
 
 
−
 
 
−
''Самостоятельно.''
 
−
 
 
−
*<tt>Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику.</tt>
 
−
*<tt>Является ли 4-угольник ABCD корректно заданным.</tt>
 
−
 
 
−
<small>'''Лекция 4'''</small>
 
−
===Арифметические выражения===
 
−
<h4>Основные сведения</h4>
 
−
Каждое выражение имеет ''тип''.
 
−
<br>Выражение называется '''''арифметическим''''', если его тип — числовой.
 
−
:Оно строится посредством ''операций''( унарных или бинарных ) и ''операндов''.
 
−
 
 
−
Если <tt>a</tt> и <tt>b</tt> — одного типа, то и <tt>a '''op''' b</tt> принадлежит к тому же типу. ''Исключением'' является операция "'''/'''" —
 
−
:<tt>'''a / b'''</tt> — вещественное.
 
−
 
 
−
Если <tt>a</tt> и <tt>b</tt> принадлежат к различным тиапм, то выражение принадлежит к "'''старшему'''" типу.
 
−
<br><tt>Например:</tt>
 
−
byte < integer < int64
 
−
integer < real
 
−
 
 
−
В арифметические выражения могут входить стандартные функции:
 
−
:<tt>exp( x )</tt>
 
−
:<tt>ln( x )</tt>
 
−
:<tt>abs( x )</tt> //модуль x
 
−
:<tt>sin( x )</tt>
 
−
:<tt>cos( x )</tt>
 
−
:<tt>sqr( x )</tt> //квадрат x
 
−
:<tt>sqrt( x )</tt> //корень из x
 
−
:<tt>min( x, y )</tt>
 
−
:<tt>max( x, y )</tt>
 
−
:<tt>pow( x, y )</tt> //x в степени y
 
−
 
 
−
<h4>Порядок выполнения операций в арифметических выражениях</h4>
 
−
*Операции с большим приоритетом выполняются первыми
 
−
*Функции вычисляются до операций
 
−
*Выражение в скобках вычисляется раньше
 
−
*Операции с одинаковым приоритетом выполняются слева направо, если идут подряд.
 
−
 
 
−
<h4>Операции div и mod для целых</h4>
 
−
<tt>x '''div''' y = x / y, округленное до ближайшего целого по направлению к нулю.</tt> Это '''''результат''''' от ''целочисленного деления''.
 
−
<br><tt>x '''mod''' y = x - (x div y) * y.</tt> Это '''''остаток''''' от ''целочисленного деления''.
 
−
 
 
−
<tt>'''Пример использования.'''</tt>
 
−
<br>Целочисленные операции часто применяются для определения '''четности''' числа:
 
−
x '''mod''' 2 = 0  <->  x — четное
 
−
x '''mod''' 2 <> 0  <->  x — нечетное
 
−
 
 
−
===Логические выражения===
 
−
<h4>Основные сведения</h4>
 
−
Выражение назывется '''''логическим''''', если оно имеет тип <tt>'''boolea'''n.</tt>
 
−
<br><tt>'''Пример'''.</tt>
 
−
x < 0
 
−
a >= b
 
−
a <> 3
 
−
Это простые логические выражения. Однако, с помщью '''логических операций''' можно составлять сложные.
 
−
( бинарные )  ( унарные )
 
−
  a '''and''' b        '''not''' a
 
−
  a '''or''' b
 
−
  a '''xor''' b
 
−
 
 
−
<h4>Таблицы истинности логических операций</h4>
 
−
a | b | a '''and''' b | a '''or''' b | a '''xor''' b
 
−
 
−
T | T |    T    |  T    |    F
 
−
T | F |    F    |  T    |    T
 
−
F | T |    F    |  T    |    F
 
−
F | F |    F    |  F    |    T
 
−
'''
 
−
<h4>Сокращение вычислений логических выражений</h4>
 
−
Большинство современных компиляторов, в т.ч. PascalABC.NET производит '''''сокращенное вычисление логических выражений'''''.
 
−
<br>Это означает, что в выражении
 
−
a '''and''' b
 
−
если a — ложно, то b не вычисляется, а в
 
−
a '''or''' b
 
−
если a — истинно, b не вычисляется.
 
−
 
 
−
Это очень полезно при вычислении таких выражений, как, например,
 
−
( y <> 0 ) '''and''' (x / y > 0 )
 
−
Логически здесь все верно, однако, если бы не использовалось сокращенное вычисление, в случае равенства нулю y возникала бы ошибка деления на ноль.
 
−
 
 
−
<h4>Логические переменные</h4>
 
−
Можно описывать логические переменные ( тип <tt>boolean</tt> ). Им можно присваивать логические выражения.
 
−
<br>Эти переменные принимают одно из двух возможных значений:
 
−
:<tt>'''true'''</tt> ( истина )
 
−
:<tt>'''false'''</tt> ( ложь )
 
−
 
 
−
<tt>'''Пример''' использования логических переменных.</tt>
 
−
:<tt>Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон ( x1, x2 ) и ординатами горизонтальных ( y1, y2 ); точка M( x, y );</tt>
 
−
:<tt>Найти: находится точка внутри прямоугольника, снаружи, или лежит на границе;</tt>
 
−
 
 
−
<source lang="Pascal">
 
−
var inside, outside, bound: boolean;
 
−
begin
 
−
  inside:= ( x > x1 ) and ( x < x2 ) and ( y > y1 ) and ( y < y2 );
 
−
  outside:= ( x < x1 ) or ( x > x2 ) or ( y < y1 ) or ( y > y2 );
 
−
  bound:= not inside and not outside;
 
−
end.
 
−
</source>
 
−
 
 
−
===Приоритеты операций языка Object Pascal===
 
−
# унарные <tt>'''+ - not'''</tt>
 
−
# бинарные
 
−
:*имеющие смысл ''умножения'' <tt>'''* / div mod and shl shr'''</tt>
 
−
:*имеющие смысл ''сложения'' <tt>'''+ - or xor'''</tt>
 
−
:*операции ''отношения'' <tt>'''<> <= >= < > in'''</tt>
 
−
===Побитовые and, or, xor===
 
−
'''Замечание.''' Работают только с целыми.
 
−
 
 
−
Смысл такой — каждое целое переводится в '''двоичную''' систему счисления и производится ''побитовое'' применение этих операций.
 
−
<br><tt>'''Пример.'''</tt>
 
−
5 '''and''' 10
 
−
5<sub>10</sub> = 101<sub>2</sub>
 
−
<br>7<sub>10</sub> = 111<sub>2</sub>
 
−
 
 
−
101
 
−
    ( '''and''' )
 
−
111
 
−
———
 
−
101<sub>2</sub> = 5<sub>10</sub>
 
−
 
 
−
===Операции shl и shr===
 
−
''Побитовый'' '''сдвиг влево''' и '''сдвиг вправо''' соответственно.
 
−
<h4>shl</h4>
 
−
x '''shl''' n = x * 2<sup>n</sup>
 
−
Сдвигает двоичное представление x на n позиций влево.
 
−
<h4>shr</h4>
 
−
x '''shr''' n = x div 2<sup>n</sup>
 
−
Сдвигает двоичное представление x на n позиций вправо.
 
−
<h4>Примеры</h4>
 
−
x = 5<sub>10</sub> = 101<sub>2</sub>
 
−
 
−
x shl 2 = <—(<sup>2</sup>)101
 
−
              10100<sub>2</sub> = 20<sub>10</sub>
 
−
 
−
x shr 2 = 101—>(<sup>2</sup>)
 
−
          001<sub>2</sub> = 1<sub>10</sub>
 
−
 
 
−
===Оператор case выбора варианта===
 
−
<h4>Синтакстис</h4>
 
−
'''case''' <A> '''of'''
 
−
{<список выбора>: <оператор>;}
 
−
['''else''' <оператор>[;]]
 
−
'''end'''
 
−
 
 
−
<h4>Семантика</h4>
 
−
Вначале вычисляется выражение <A>, называемое '''''переключателем''''', и ищется в одном из <списков выбора>.
 
−
<br>Если знгачение попадает в какой-то <список выбора>, то выполняется соответствующий ему оператор, иначе, если есть ветвь <tt>'''else'''</tt>, то выполняется оператор по ветке <tt>'''else'''</tt>.
 
−
<h4>Ограничения</h4>
 
−
*выражение <A> должно иметь так называемый '''порядковый''' тип:
 
−
:''целый''
 
−
:''символьный''
 
−
:''перечислимый''
 
−
НО НЕ строковый или вещественный.
 
−
*значения в <списках выбора> не должны пересекаться.
 
−
<h4>Примеры использования оператора выбора</h4>
 
−
<tt>1.'''День недели'''</tt>
 
−
<source lang="Pascal">
 
−
case DayOfWeek of
 
−
  1..5: writeln( 'Будний' );
 
−
  6, 7: writeln( 'Выходный' );
 
−
  else writeln( 'Ошибка' );
 
−
end;</source>
 
−
<tt>1.'''Цифра или буква'''</tt>
 
−
<source lang="Pascal">
 
−
var c: char;
 
−
read( c );
 
−
case c of
 
−
  '0'..'9': writeln( 'Цифра' );
 
−
  'A'..'Z', 'a'..'z', 'а'..'я', 'А'..'Я', 'ё', 'Ё': writeln( 'Буква' );
 
−
end;</source>
 
−
 
 
−
<small>'''Лекция 5'''</small>
 
−
 
 
−
===Циклы с предусловием (while) и постусловием (repeat)===
 
−
<h4>Синтаксис цикла while</h4>
 
−
'''while''' <условие> '''do'''  <— '''''заголовок цикла'''''
 
−
  <оператор>  <— '''''тело цикла'''''
 
−
 
−
<условие>::= <логическое выражение>
 
−
<h4>Семантика цикла while</h4>
 
−
[[Изображение:Цикл_while_м.png]]
 
−
<h4>Синтаксис цикла repeat</h4>
 
−
'''repeat'''
 
−
  <операторы>
 
−
'''until''' <условие>
 
−
<h4>Семантика цикла repeat</h4>
 
−
[[Изображение:Цикл_repeat_м.png]]
 
−
<h4>Зацикливание</h4>
 
−
'''''Зацикливание''''' происходит, если:
 
−
*условие цикла с '''предусловием''' всегда ''истинно''
 
−
<tt>Пример.</tt>
 
−
<source lang="Pascal">while true do
 
−
  <оператор></source>
 
−
*условие цикла с '''постусловием''' всегда ''ложно''
 
−
<tt>Пример.</tt>
 
−
<source lang="Pascal">repeat
 
−
  <операторы>
 
−
until false</source>
 
−
'''''Итерация''''' — однократное повторение тела цикла
 
−
<h4>Отличия между циклами while и repeat</h4>
 
−
'''while'''
 
−
:тело может не выполниться ни разу
 
−
'''repeat'''
 
−
:тело выполнится хотя бы один раз
 
−
<h4>Примеры</h4>
 
−
*<tt>'''Сумма нечетных двузначных чисел'''</tt>
 
−
 
 
−
''С использованием while''
 
−
<source lang="Pascal">s:= 0; x:= 11;
 
−
while x < 100 do
 
−
begin
 
−
  s+= x;
 
−
  x+= 2;
 
−
end;</source>
 
−
''С использованием repeat''
 
−
<source lang="Pascal">s:= 0; x:= 11;
 
−
repeat
 
−
  s+= x;
 
−
  x+= 2;
 
−
until x = 99;</source>
 
−
 
 
−
*<tt>'''Факториал'''</tt>
 
−
 
 
−
''С использованием repeat''
 
−
<source lang="Pascal">var n: integer;
 
−
read( n );
 
−
var x:= n;
 
−
var p:=1;
 
−
 
 
−
repeat
 
−
  p*= x;
 
−
  x-= 1;
 
−
until x = 1;</source>
 
−
''С использованием while''
 
−
<source lang="Pascal">var n: integer;
 
−
read( n );
 
−
var x:= n;
 
−
var p:=1;
 
−
 
 
−
while x > 1 do
 
−
begin
 
−
  p*= x;
 
−
  x-= 1;
 
−
end;</source>
 
−
<h4>Моделирование repeat с помощью while</h4>
 
−
'''repeat'''            ''Op''
 
−
  '' Op''      ——>    '''while''' '''not''' A '''do'''
 
−
'''until''' A;          '''begin'''
 
−
                      ''Op''
 
−
                    '''end;'''
 
−
<h4>Моделирование while с помощью repeat</h4>           
 
−
'''while''' A '''do'''        '''if''' A '''then'''
 
−
  ''Op''        ——>    '''repeat'''
 
−
                      '' Op''
 
−
                      '''until not''' A
 
−
 
 
−
===Оператор цикла с параметром (for)===
 
−
<h4>Синтаксис</h4>
 
−
<заголовок цикла>
 
−
  <тело цикла>
 
−
 
 
−
<заголовок цикла>::= '''for''' <переменная>:=<выражение<sub>1</sub>> <направление> <выражение<sub>2</sub>> '''do'''
 
−
<тело цикла>::= <оператор>
 
−
<направление>::= '''to''' | '''downto'''
 
−
<h4>Семантика</h4>
 
−
var b:= <выражение<sub>1</sub>>;
 
−
var e = <выражение<sub>2</sub>>;
 
−
<переменная>:= b;
 
−
 
−
'''while''' <переменная> '''<>''' e '''do'''
 
−
'''begin'''
 
−
  <оператор>
 
−
  <получить следующее значение переменной>
 
−
  <переменная>'''+'''= 1; | <переменная>'''-'''= 1;
 
−
'''end;'''
 
−
 
 
−
<получить следующее значение переменной>::= <переменная>'''+'''= 1; | <переменная>'''-'''= 1;
 
−
'''<big>Ограничения:</big>'''
 
−
*выражения 1 и 2 должны быть совместимы по присваиванию с переменной
 
−
*переменная должна иметь порядковый тип ( такой же, как и в case — целый, символьный или перечислимый )
 
−
*переменная цикла for не должна меняться внутри цикла for
 
−
*переменная цикла for должна быть описана в той же п/п, где используется цикл
 
−
<h4>Дополнительные возможности PascalABC.NET</h4>
 
−
Возможно ''описание переменной цикла в его заголовке'':
 
−
<source lang="Pascal">for [var] i: integer:= 1 to 5 do
 
−
  <оператор></source>
 
−
'''Замечание!''' Значение переменной цикла после завершения цикла не определено.
 
−
 
 
−
===Примеры использования циклов===
 
−
<h4>Табулирование функции.</h4>
 
−
:<tt>Дана f( x ) на [a; b], разбитая на N частей.</tt>
 
−
:<tt>Выдать таблицу значений в точках разбиения.</tt>
 
−
<tt>'''Решение.'''</tt>
 
−
<source lang="Pascal">var a, b: real;
 
−
var N: integer;
 
−
read( a, b, N );
 
−
 
 
−
assert( N <> 0 );
 
−
assert( b > a );
 
−
var h:= ( b - a ) / N;</source>
 
−
''Дальнейшее решение с помощью'' '''for''':
 
−
<source lang="Pascal">for var i:= 0 to N do
 
−
begin
 
−
  writelnFormat( '{0,6:f2} {1,9:f4}', x, f( x ) );
 
−
  x+= h;
 
−
end;</source>
 
−
''Дальнейшее решение с помощью'' '''while''':
 
−
<source lang="Pascal">var eps:= h / 2;
 
−
while x < ( b + eps ) do
 
−
begin
 
−
  writelnFormat( '{0,6:f2} {1,9:f4}', x, f( x ) );
 
−
  x+= h;
 
−
end;</source>
 
−
'''Замечание!'''вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при представлении вещественного числа в памяти, называется '''''ошибкой округления'''''.
 
−
<br>Ошибка, которая возникает в результате вычислений с вещественными числами называется '''''вычислительной погрешностью'''''.
 
−
 
 
−
:'''Вывод.''' Вещественные числа нельзя сравнивать на равенство, можно только на ''больше/меньше''.
 
−
<small>'''Лекция 6'''</small>
 
−
<h4>Рекуррентные соотношения</h4>
 
−
Говорят, что последовательность данных
 
−
x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>,..., x<sub>n</sub>
 
−
является '''''рекуррентной''''', если
 
−
x<sub>k + 1</sub> = f( x<sub>k</sub> ), k = 1, 2, 3...
 
−
<h4>Вывод степеней двойки</h4>
 
−
<source lang="Pascal">var x:= 1;
 
−
for var i:=1 to 10 do
 
−
begin
 
−
  writeln( x );
 
−
  x*= 2;
 
−
end;</source>
 
−
<h4>Последовательность Фибоначчи</h4>
 
−
<math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math>
 
−
<source lang="Pascal">var a:= 1;
 
−
var b:= 1;
 
−
write( a, ' ', b, ' ' );
 
−
for var i:= 3 to 20 do
 
−
begin
 
−
  c:= a + b;
 
−
  write( c, ' ' );
 
−
  a:= b;
 
−
  b:= c;
 
−
end;</source>
 
−
<h4>НОД</h4>
 
−
<math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod  x_k\end{cases}</math>
 
−
 
 
−
<tt>'''Решение.'''</tt>
 
−
<source lang="Pascal">var a, b: integer;
 
−
read( a, b );
 
−
assert( (a > 0) and (b > 0) );
 
−
repeat
 
−
  c:= a mod b;
 
−
  a:= b;
 
−
  b:= c;
 
−
until c = 0;
 
−
writeln( a );</source>
 
−
 
 
−
<h4>Суммирование рядов (конечных и бесконечных)</h4>
 
−
*<math> \sum_{i=1}^n  \frac{a^i}{i!}</math>
 
−
Найдем рекуррентную связь между '''a<sub>i</sub>''':
 
−
x<sub>1</sub> = a
 
−
x<sub>i</sub> = x<sub>i-1</sub> * a / i, i = 2, 3..
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">read( a, n );
 
−
x:= a;
 
−
s:= x;
 
−
for var i:= 2 to n do
 
−
begin
 
−
  x*= a / i;
 
−
  s+= x;
 
−
end;</source>
 
−
*<math> \sum_{i=1}^\infty  (-1)^i\frac{a^i}{i}</math>
 
−
Для вычисления суммы ''бесконечного ряда'' в простейшем случае используют следующий метод:
 
−
:задается некоторый малый <tt>'''eps'''</tt> и сумма <math>\sum_{i=1}^\infty  x_i</math> вычисляется, пока <math>|x_i| <\ eps</math>
 
−
 
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">assert( (a > 0) and (a < 1) );
 
−
i:= 1;
 
−
s:= 0;
 
−
y:= -a;
 
−
repeat
 
−
  s+= y / i;
 
−
  i+= 1;
 
−
  y*= -a;
 
−
until abs( y / i ) < eps;</source>
 
−
<h4>Нахождение max в последовательности чисел</h4>
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">max:= - real.MaxValue;
 
−
for var i:= 1 to n do
 
−
begin
 
−
  read( x );
 
−
  if x > max then
 
−
    max:= x;
 
−
end;</source>
 
−
<h4>Разложение целого числа на простые множители</h4>
 
−
Будем делить x на p, начиная с ''p = 2''. Если делится нацело, то p — множитель, если не делится, то увеличиваем p на 1, пока ''x <> 1''.
 
−
 
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">read( x );
 
−
p:= 2;
 
−
repeat
 
−
  if x mod p = 0 then
 
−
  begin
 
−
    write( p, ' ' );
 
−
    x:=x div p;
 
−
  end
 
−
  else
 
−
    p+= 1;
 
−
until x = 1;</source>
 
−
 
 
−
<small>'''Лекция 7'''</small>
 
−
<h4>Оператор break</h4>
 
−
'''break''' — оператор ''досрочного завершения цикла''.
 
−
[[Изображение:break_м.png|none]]
 
−
<h4>Оператор continue</h4>
 
−
'''continue''' — оператор ''досрочного завершения текущей итерации'' цикла.
 
−
[[Изображение:continue_м.png|none]]
 
−
<h4>Поиск заданного значения среди введенных</h4>
 
−
<tt>'''Решение1'''.</tt> С использованием оператора ''break''.
 
−
<source lang="Pascal">var exists: boolean:= false;
 
−
for var i:= 1 to n do
 
−
begin
 
−
  read( x );
 
−
  if x = k then
 
−
  begin
 
−
    exists:= true;
 
−
    break;
 
−
  end;
 
−
end;</source>
 
−
<tt>'''Решение2'''.</tt>
 
−
<source lang="Pascal">var i:= 1;
 
−
var exists: boolean:= false;
 
−
repeat
 
−
  read( x );
 
−
  if x = k then
 
−
    exists:= true;
 
−
  i+= 1;
 
−
until (i > n) or exists;</source>
 
−
<h4>Обработка последовательности, признак завершения к. — ввод нуля.</h4>
 
−
:Вводятся числа. Конец ввода — ноль.
 
−
:Найти сумму и произвведение положительных чисел.
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">s:= 0;
 
−
p:= 1;
 
−
while True do
 
−
begin
 
−
  read( x );
 
−
  if x = 0 then
 
−
    break;
 
−
  if x < 0 then
 
−
    continue;  //фильтр
 
−
  s+= x;
 
−
  p*= x;
 
−
end;</source>
 
−
<h4>Вычисление значения многочлена. Схема Горнера</h4>
 
−
Необходимо вычислить
 
−
<math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math>
 
−
если
 
−
:a<sub>0</sub>...a<sub>n</sub> известны
 
−
:x дано
 
−
 
 
−
<tt>'''Решение1'''.</tt>
 
−
<source lang="Pascal">var p:= 1.0;
 
−
var s:= 0.0;
 
−
for var i:=0 to n do
 
−
begin
 
−
  read( a );
 
−
  s+= p * a;
 
−
  p*= x;
 
−
end;</source>
 
−
Это решение использует <tt>2(n + 1)</tt> умножений.
 
−
 
 
−
Однако есть и другое решение — '''схема Горнера'''.
 
−
Оно основана на том, что
 
−
<br><math>\ a_0x^2 + a_1x + a_2 = ((a_0)x + a_1)x + a_2</math>
 
−
 
 
−
<tt>'''Решение2'''.</tt>
 
−
<source lang="Pascal">read( a );
 
−
var res: real:= a;
 
−
for var i:=1 to n do
 
−
begin
 
−
  read( a );
 
−
  res*= x;
 
−
  res+= a;
 
−
end;</source>
 
−
Итого — всего <tt>n</tt> умножений.
 
−
<h4>Поиск нуля функции на отрезке</h4>
 
−
Требуется найти корень уравнения <tt>f( x ) = 0</tt>
 
−
*на отрезке <tt>[a; b]</tt>
 
−
*с заданной точностью eps
 
−
*<tt>f( x )</tt> непрерывна на этом отрезке
 
−
*имеет на нем ровно 1 корень, т.е. <tt>f(a ) * f( b ) < 0</tt>
 
−
 
 
−
Эта задача решается '''методом половинного деления'''.
 
−
<source lang="Pascal">assert( b > a );
 
−
var fa:= f( a );
 
−
var fb:= f( b );
 
−
assert( fa * fb < 0 );
 
−
 
 
−
while b - a > eps do
 
−
begib
 
−
  var x:= (b + a) / 2;
 
−
  var fx:= f( x );
 
−
  if f( x ) * f( a ) > 0 then
 
−
  begin
 
−
    a:= x;
 
−
    fa:= fx;
 
−
  end
 
−
  else
 
−
    b:= x;
 
−
end;</source>
 
−
<small>'''Лекция 8'''</small>
 
−
 
 
−
===Вложенные циклы===
 
−
<h4>Метод последовательной детализации</h4>
 
−
''Задача''.<tt> Вывести все простые числа <= n</tt>
 
−
<source lang="Pascal">writeln( 2 );
 
−
x:= 3;
 
−
while x <= n do
 
−
begin
 
−
  Если число x — простое, то
 
−
    writeln( x );
 
−
  x+= 2;
 
−
end;</source>
 
−
<h4>Метод окаймления</h4>
 
−
''Задача''. <tt>Вывести A<sup>k</sup>, A = 2..10</tt>
 
−
 
 
−
'''Метод окаймления''' заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "''размораживая''" некоторый параметр.
 
−
 
 
−
Итак, пусть A — фиксировано( "''заморожено''" ).
 
−
<source lang="Pascal">var p:= 1.0;
 
−
for var i:=1 to k do
 
−
  p*= A;
 
−
write( p );</source>
 
−
Теперь ''размораживаем'' A:
 
−
<source lang="Pascal">for A:=2 to 10 do
 
−
begin
 
−
  ...
 
−
end;</source>
 
−
<h4>Переборные задачи</h4>
 
−
Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
 
−
 
 
−
''Задача''
 
−
:<tt>Дано равенство: a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>, a,b,c — целые</tt>
 
−
:<tt>Вывести все такие тройки (a, b, c), что: a<=100, b<=1000, c<=1000;</tt>
 
−
<tt>'''Решение'''.</tt>
 
−
<source lang="Pascal">for var a:= 1 to 1000 do
 
−
  for var b:= 1 to 1000 do
 
−
    for var c:= 1 to 1000 do
 
−
      if a*a + b*b = c*c then
 
−
        writeln( a, b, c );</source>
 
−
Однако, ясно, что
 
−
a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup> <=> b<sup>2</sup> + a<sup>2</sup> = c<sup>2</sup>
 
−
<tt>'''Оптимизация'''</tt>
 
−
<source lang="Pascal">for var a:= 1 to 1000 do
 
−
  for var b:= 1 to a-1 do
 
−
  begin
 
−
    var c:= round( sqrt( a*a + b*b ) );
 
−
    if a*a + b*b = c*c then
 
−
    begin
 
−
      writeln(a, b, c);
 
−
      writeln(b, a, c);
 
−
    end;
 
−
  end;</source>
 
−
'''Вывод.''' При наличии нескольких вложенных циклов нужно оптимизировать ''самый внутренний''.
 
−
 
 
−
==Ссылки==
 
−
*[http://it.mmcs.sfedu.ru/wiki/index.php/%D0%9E%D1%81%D0%B5%D0%BD%D0%BD%D0%B8%D0%B9_%D1%81%D0%B5%D0%BC%D0%B5%D1%81%D1%82%D1%80%3B_%D0%9C%D0%B8%D1%85%D0%B0%D0%BB%D0%BA%D0%BE%D0%B2%D0%B8%D1%87_%D0%A1.%D0%A1.%3B_2008%3B_II Вторая часть конспекта]
 
−
*[[Конспекты|Другие конспекты]]
 

Текущая версия на 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»