|
|
(не показано 110 промежуточных версий 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''' <имя>;] |
| <раздел описаний> | | <раздел описаний> |
Строка 146: |
Строка 195: |
| <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>... | | <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>... |
| | | |
− | '''Пример секции описания переменных''' | + | ''<u>Пример</u> секции описания переменных.'' |
− | <source lang="Pascal">var
| + | <source lang="Pascal"> |
− | a,b: real;
| + | var |
− | i: integer;</source>
| + | a,b: real; |
| + | i: integer; |
| + | </source> |
| | | |
| <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>} | | <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>} |
Строка 155: |
Строка 206: |
| <список имен> ::= <имя>{,<имя>} | | <список имен> ::= <имя>{,<имя>} |
| <тип> ::= <имя> | | <тип> ::= <имя> |
− | ===Внутриблочные переменные===
| |
| | | |
− | В 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 r: real := 5.2; |
− | var Pi := 3.14;</source> | + | 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>
| |
− | <переменная> ''':=''' <выражение>
| |
− | | |
− | '''Пример использования оператора присваивания'''
| |
− | a ''':=''' (3 + 5) * 8;
| |
− | b := a + 2;
| |
− | | |
− | <h3>Семанитика</h3>
| |
− | Вычисляется выражение в правой части, при этом вместо имен переменных подставляются их значения.
| |
− | Затем результат вычисления записывается в переменную в левой части.
| |
− | | |
− | '''Ограничение.''' Тип выражения должен быть ''совместим по присваиванию'' с переменной.
| |
− | Например:
| |
− | *одинаковые типы совместимы.
| |
− | *выражение типа integer можно присвоить переменной типа real, обратное неверно.
| |
− | | |
− | <h3>Операторы присваивания += и *=</h3>
| |
− | | |
− | '''Пример.'''
| |
− | d += 1; //прибавить 1 к d
| |
− | d *= 2; //умножить d на 2
| |
− | | |
− | <small>'''Лекция 3'''</small>
| |
− | <h3>Примеры использования :=</h3>
| |
− | | |
− | '''Пример 1.''' Перемена местами двух значений.
| |
− | :Дано: x,y;
| |
− | <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>
| |
− | | |
− | | |
− | '''Пример 2.''' Использование промежуточных переменных в вычислениях
| |
− | :Дано: x: real;
| |
− | :Найти: x<sup>15</sup>;
| |
− | | |
− | '''Решение 1.'''
| |
− | <source lang="Pascal">
| |
− | y := x * x;
| |
− | z := y * y;
| |
− | t := z * z;
| |
− | p := t * z;
| |
− | q := p * x * y;
| |
− | </source>
| |
− | '''Решение 2.'''
| |
− | <source lang="Pascal">
| |
− | y := x * x;
| |
− | z := y * x;
| |
− | t := z * y;
| |
− | p := t * t * t;
| |
− | </source>
| |
− | '''Решение 3.'''
| |
− | <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>
| |
− | '''read''' (<список переменных>) | '''readln''' (<список переменных>)
| |
− | | |
− | <h3>Семантика</h3>
| |
− | Происходит считывание данных с клавиатуры и запись их в переменные из <списка переменных>. Вводить данные нужно либо через пробел, либо по нажатию <Enter>, при этом программа не перейдет к выполнению следующего оператора, пока не будут считаны все данные.
| |
− | | |
− | С процедурой ввода связан ряд ''ошибок'' (например, если переменная используется в качестве делителя и вводится 0, или если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.
| |
− | | |
− | ==Оператор try/except и обработка ошибок ввода==
| |
− | | |
− | Операторы, которые могут получать ошибку, заключаются специальный охранный блок - оператор <tt>'''try'''</tt>.
| |
− | | |
− | <h3>Синтаксис</h3>
| |
− | <source lang="Pascal">
| |
− | try
| |
− | ...
| |
− | readln(a);
| |
− | ...
| |
− | except
| |
− | <обработка ошибки>
| |
− | end;
| |
− | <продолжение работы>
| |
− | </source>
| |
− | | |
− | <h3>Семантика</h3>
| |
− | | |
− | Если внутри блока '''try''' происходит ошибка выполнения, то все последующие операторы в блоке игнорируются и выполнение программы переходит к блоку '''except'''. По выходе из '''except''' программа продолжает работу.
| |
− | | |
− | Если ошибки не происходит, то выполняются все операторы в блоке '''try''', блок '''except''' не выполняется и программа продолжает работу.
| |
− | | |
− | ==Оператор вывода==
| |
− | <h3>Синтаксис</h3>
| |
− | '''write'''( <список выражений> ) | '''writeln'''( <список выражений> )
| |
− | | |
− | <h3>Семантика</h3>
| |
− | Выражения в списке вычисляются и тих значения выводятся на экран.
| |
− | В случае <tt>writeln</tt> после выводао существляется переход на новую строку.
| |
− | | |
− | <h3>Форматы вывода</h3>
| |
− | После каждого выражения в списке вывода можно использовать формат вывода в виде <tt>''':a'''</tt>, где a — выражение целого типа.
| |
− | После вещественного типа — <tt>''':a:b'''</tt>
| |
− | | |
− | <tt>'''a'''</tt> задает ширину поля вывода ( выравнивание по правому краю ).
| |
− | <br><tt>'''b'''</tt> — количество знаков в дробной части.
| |
− | | |
− | <h3>Вывод с помощью write[ln]Format</h3>
| |
− | '''writelnFormat'''( '<форматная строка>', <список выражений> )
| |
− | | |
− | '''Пример''' вывода с использованием форматной строки
| |
− | <source lang="Pascal">writelnFormat('{0} * {1} = {2}', a, b, a * b);</source>
| |
− | Будет выведено:
| |
− | a * b = '''a * b'''
| |
− | | |
− | В форматной строке тоже можно использовать формат вывода.
| |
− | <br><tt>{0, 10}</tt> — 10 это ширина поля вывода
| |
− | <br><tt>{0, 10:f3}</tt> — 3 это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).
| |
− | | |
− | ==Условный оператор==
| |
− | <h3>Синтаксис</h3>
| |
− | '''if''' <условие> '''then''' <оператор<sub>1</sub>>
| |
− | '''else''' <оператор<sub>2</sub>>
| |
− | | |
− | <h3>Семантика</h3>
| |
− | [[Изображение: If.jpg]]
| |
− | <h3>Примеры использования для решения задач</h3>
| |
− | | |
− | '''Пример 1.''' Нахождение минимума
| |
− | <br>Дано: x,y; <br> Найти: min;
| |
− | <source lang="Pascal">if x > y then
| |
− | min := y
| |
− | else
| |
− | min := x;</source>
| |
− | '''Пример 2.''' Упорядочение a, b по возрастанию
| |
− | <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>
| |
− | | |
− | '''Пример 3.''' Вычисление функции по взаимоисключающим веткам
| |
− | <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>'''.
| |
− | | |
− | '''Пример 4.''' Найти среднее среди a,b,c (a,b,c попарно не равны)
| |
− | Эта задача имеет несколько вариантов решения.
| |
− | <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>
| |
− | | |
− | ''Самостоятельно.''
| |
− | | |
− | *Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику.
| |
− | *Является ли 4-угольник ABCD корректно заданным.
| |
− | | |
− | <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>Например:
| |
− | 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> Это '''''остаток''''' от ''целочисленного деления''.
| |
− | | |
− | '''Пример использования'''
| |
− | <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> ( ложь )
| |
− | | |
− | '''Пример''' использования логических переменных
| |
− | :Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон ( x1, x2 ) и ординатами горизонтальных ( y1, y2 ); точка M( x, y );
| |
− | :Найти: находится точка внутри прямоугольника, снаружи, или лежит на границе;
| |
− | | |
− | <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>'''Пример'''
| |
− | 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>
| |
− | 1.'''День недели'''
| |
− | <source lang="Pascal">
| |
− | case DayOfWeek of
| |
− | 1..5: writeln( 'Будний' );
| |
− | 6, 7: writeln( 'Выходный' );
| |
− | else writeln( 'Ошибка' );
| |
− | end;</source>
| |
− | 1.'''Цифра или буква'''
| |
− | <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>
| |
− | '''''Зацикливание''''' происходит, если:
| |
− | *условие цикла с '''предусловием''' всегда ''истинно''
| |
− | Пример
| |
− | <source lang="Pascal">while true do
| |
− | <оператор></source>
| |
− | *условие цикла с '''постусловием''' всегда ''ложно''
| |
− | Пример
| |
− | <source lang="Pascal">repeat
| |
− | <операторы>
| |
− | until false</source>
| |
− | '''''Итерация''''' — однократное повторение тела цикла
| |
− | <h4>Отличия между циклами while и repeat</h4>
| |
− | '''while'''
| |
− | :тело может не выполниться ни разу
| |
− | '''repeat'''
| |
− | :тело выполнится хотя бы один раз
| |
− | <h4>Примеры</h4>
| |
− | *'''Сумма нечетных двузначных чисел'''
| |
− | | |
− | ''С использованием 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>
| |
− | | |
− | *'''Факториал'''
| |
− | | |
− | ''С использованием 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>
| |
− | :Дана f(x) на [a; b], разбитая на N частей.
| |
− | :Выдать таблицу значений в точках разбиения.
| |
− | '''Решение'''
| |
− | <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>
| |
− | | |
− | '''Решение'''
| |
− | <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..
| |
− | '''Решение'''
| |
− | <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>
| |
− | | |
− | '''Решение''' | |
− | <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>
| |
− | '''Решение'''
| |
− | <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''.
| |
− | | |
− | '''Решение'''
| |
− | <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>
| |
− | '''Решение1'''. С использованием оператора ''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>
| |
− | '''Решение2'''
| |
− | <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>
| |
− | :Вводятся числа. Конец ввода — ноль.
| |
− | :Найти сумму и произвведение положительных чисел.
| |
− | '''Решение'''
| |
− | <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 дано
| |
− | | |
− | '''Решение1'''
| |
− | <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>
| |
− | | |
− | '''Решение2'''
| |
− | <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>
| |
− | ''Задача''. Вывести все простые числа <= n
| |
− | <source lang="Pascal">writeln(2);
| |
− | x := 3;
| |
− | while x <= n do
| |
− | begin
| |
− | Если число x — простое, то
| |
− | writeln(x);
| |
− | x += 2;
| |
− | end;</source>
| |
− | <h4>Метод окаймления</h4>
| |
− | ''Задача''. Вывести A<sup>k</sup>, A = 2..10
| |
− | | |
− | '''Метод окаймления''' заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "''размораживая''" некоторый параметр.
| |
− | | |
− | Итак, пусть 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>
| |
− | Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
| |
− | | |
− | ''Задача''
| |
− | :Дано равенство: a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>, a,b,c — целые
| |
− | :Вывести все такие тройки (a, b, c), что: a<=100, b<=1000, c<=1000;
| |
− | '''Решение'''
| |
− | <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>
| |
− | '''Оптимизация'''
| |
− | <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 Вторая часть конспекта]
| |
− | *[[Конспекты|Другие конспекты]]
| |
В частности, процессор компьютера выступает исполнителем машинных команд.
Алгоритм 1. (словесное описание)
Алгоритм 2. (псевдокод)
1. Словесный
2. Псевдокод
3. Блок-схемы
4. Язык программирования (ЯП)
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы.
Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
Общая характеристика PascalABC.NET.
Отличия языка PascalABC.NET от обычного языка Паскаль.
Схема компиляции в промежуточный код. JIT-компиляция
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.