Readinteger pascal что это
Базовые конструкции PascalABC.NET
Описания переменных внутри блока и автовывод типов
В большинстве случаев переменные описываются в блоке begin-end и описание совмещается с инициализацией:
Это решает сразу несколько проблем:
При таком способе возникает одна проблема: если надо накопить сумму вещественных, то такой код приведет к ошибке типов:
Для исправления этой ошибки всё равно придётся говорить о типах и инициализировать sum одним из двух способов:
Цикл for var
Это делает невозможным использование счётчика цикла вне цикла
Цикл loop
Если количество повторений цикла заранее известно, но неважен номер повторения, то используется цикл loop:
Множественное описание переменных с инициализацией
Можно инициализировать сразу несколько переменных в момент описания:
Вывод
Для вывода вместо процедуры Write предпочтительно использовать процедуру Print. В отличие от Write она разделяет элементы вывода пробелами. Например:
Для вывода нескольких значений с пояснениями рекомендуется использовать интерполированные строки:
вместо режущего глаз
Ввод принято осуществлять, используя функции вида ReadInteger, ReadReal и т.д.:
Это позволяет совмещать описание переменной с инициализацией и автовыводом типа. В качестве дополнительных бонусов: можно делать приглашение к вводу как параметр функции ввода и вводить сразу несколько переменных одного типа:
Для ввода с контролем ошибок используется функция TryRead. Она возвращает False если ввод осуществлён неверно (введено не число или число выходит за границы диапазона). Типичный пример её использования:
Тип BigInteger
Для работы с длинными целыми используется тип BigInteger. Например, чтобы вычислить 100!, достаточно написать следующий код:
Некоторые полезные стандартные процедуры, функции и операции
Для обмена значений двух переменных a и b используйте стандартную функцию Swap(a,b) :
Разумеется, первый раз необходимо показать, что обмен значений осуществляется через третью переменную:
Но далее следует использовать Swap.
Минимальное и максимальное среди множества значений можно вычислить, используя стандартные функции Min и Max:
Для возведения в степень используется операция ** :
Для проверки принадлежности диапазону используется конструкция x in a..b :
Эта операция эффективна и переводится в
Диапазоны также можно использовать для вещественных значений и для символов:
Для проверки принадлежности множеству значений используется либо множество:
Условная операция
Если переменной необходимо присвоить значение в зависимости от условия, то вместо условного оператора иногда нагляднее использовать условную операцию:
Методы в стандартных типах
Например, чтобы вывести значение переменной базового типа, можно использовать метод Print:
Из других интересных методов для начинающих для целых типов отметим:
Например, в следующей программе вычисляется количество четных двузначных из 10 введённых:
Для вещественных значений полезными являются методы
В частности, удобно использовать цепочечную точечную нотацию:
Для всех числовых типов также определены константы MinValue и MaxValue. Чтобы обратиться к ним, следует использовать имя типа:
Кортежи
Присваивание (a,b) := (b,a) позволяет поменять значения двух переменных.
Использование кортежей даже в начальных задачах крайне многообразно.
Пример 1. Нахождение наибольшего общего делителя
Занятие 1. Pascal abc.net: Основные особенности при работе с переменными и условный оператор
Принцип локальности
В обычном Паскале описание переменных обычно находится до тела программы:
Если программный код достаточно большой, то такой вариант инициализации переменных весьма неудобен. В Pascal abc.net переменные могут описываться внутри тела программы — между begin и end и инициализироваться при описании.
В этом состоит принцип локальности: переменная описывается непосредственно перед началом своего использования.
Внутриблочные переменные позволяют сильно уменьшить количество глобальных переменных в разделе описания.
Т.е. чем ближе к месту использования описывается некоторый программный объект, тем читабельней код и модифицируемей программа.
begin var n:integer; read(n);
begin var n:=ReadInteger(‘введите n: ‘);
Теперь этот фрагмент кода можно вырезать и перенести в функцию или в модуль. В этом и заключается модифицируемость.
var n:=ReadInteger(); var n:=ReadReal();
var a: integer; b: real; begin a := 1; writeln(‘a := 1; a = ‘,a); a += 2; // Увеличение на 2 writeln(‘a += 2; a = ‘,a); a *= 3; // Умножение на 3 writeln(‘a *= 3; a = ‘,a); writeln; b := 6; writeln(‘b := 6; b = ‘,b); r /= 2; writeln(‘b /= 2; b = ‘,b); end.
для нескольких заданных x.
begin writeln(‘Введите значение x’); var x:=ReadReal; var a:=(x-3)*(x-3)*(x-3); var y:= 5*sqr(a)-8*a+2; writeln(‘Значение функции для x = ‘, y); end.
Задача abc_net 1. Найдите расстояние между двумя точками с заданными координатами (x1,y1) и (x2,y2) на плоскости. Расстояние вычисляется по формуле:
Проверьте правильность вашей программы на следующих значениях:
[Название файла: L1abc1.pas ]
Базовые типы и методы внутри стандартных типов
Для обращения к методам используется точечная нотация:
Исключение — управляемая ошибка, которую можно перехватывать и погашать.
WritelnFormat(‘f(<0>, <1>) = <2>‘, a, b, c);
то нужно просто заменить a, b на , :
WritelnFormat(‘ <0>+ <1>= <1>+ <0>= <2>‘, a, b, x + y)
Стандартные функции
Обмен значениями переменных происходит без использования буферной переменной:
Поиск максимального и минимального значения:
Операции целочисленного деления и остатка
[Название файла: L1abc2.pas ]
Работа с отдельными цифрами числа
begin var a := abs(readinteger); // модуль числа println(a div 100 + (a div 10) mod 10 + a mod 10); end.
Приведите лог работы программы с одним из введенных чисел в форме комментария.
[Название файла: L1abc3.pas ]
[Название файла: L1abc4.pas ]
Логические выражения и условный оператор
Логические переменные и выражения
Логическое выражение после его вычисления возвращает значение True (истина) или False (ложь).
Логическое выражение может включать:
begin var (a, b) := readinteger2; println(a > b); end.
[Название файла: L1abc5.pas ]
[Название файла: L1abc6.pas ]
Чаще всего логические выражения используются внутри условного оператора, который выполненяет определённые действия в зависимости от истинности выражения:
Короткая форма условного оператора:
if then // выполнится, если возвращает True
При использовании нескольких операторов в одном условии необходимы операторные скобки begin..end :
[Название файла: L1abc7.pas ]
[Название файла: L1abc8.pas ]
Рассмотрим оператор на примере:
Вводится номер единицы длины (целое число в диапазоне 1–5) и длина отрезка в этих единицах (вещественное положительное число). Найти длину отрезка в метрах.
begin var n := readinteger(‘Введите номер единицы:’); var a := readreal(‘Введите длину в заданных единицах:’); case n of 1: a /= 10; // дециметр 2: a *= 1000; // километр 4: a /= 1000; // миллиметр 5: a /= 100; // сантиметр end; println(‘Длина в метрах:’, a); end.
Readinteger pascal что это
Что ты хочешь узнать?
Ответ
Проверено экспертом
function ReadInteger(prompt: string): integer;
Выводит приглашение к вводу и возвращает значение типа integer, введенное с клавиатуры
function ArrRandom(n: integer := 10; a: integer := 0; b: integer := 100): array of integer;
Возвращает массив размера n, заполненный случайными целыми значениями
function Println(delim: string := ‘ ‘): sequence of T;
Выводит последовательность на экран, используя delim в качестве разделителя, и переходит на новую строку.
procedure Assert(cond: boolean; sourceFile: string := »; line: integer := 0);
Выводит в специальном окне стек вызовов подпрограмм если условие не выполняется
лабораторные работы и задачи по программированию и информатике, егэ по информатике
Принцип локальности
В обычном Паскале описание переменных обычно находится до тела программы:
Если программный код достаточно большой, то такой вариант инициализации переменных весьма неудобен. В Pascal abc.net переменные могут описываться внутри тела программы — между begin и end и инициализироваться при описании.
В этом состоит принцип локальности: переменная описывается непосредственно перед началом своего использования.
Внутриблочные переменные позволяют сильно уменьшить количество глобальных переменных в разделе описания.
Т.е. чем ближе к месту использования описывается некоторый программный объект, тем читабельней код и модифицируемей программа.
begin var n:integer; read(n);
begin var n:=ReadInteger(‘введите n: ‘);
var p:=1; // канонический способ — тип определяется по правой части for var i:=1 to n do p:=p*i; // можно заменить на компактную форму p*=i; print (p); // write() заменяем на print() end.
Теперь этот фрагмент кода можно вырезать и перенести в функцию или в модуль. В этом и заключается модифицируемость.
var n:=ReadInteger(); var n:=ReadReal();
var a: integer; b: real; begin a := 1; writeln(‘a := 1; a = ‘,a); a += 2; // Увеличение на 2 writeln(‘a += 2; a = ‘,a); a *= 3; // Умножение на 3 writeln(‘a *= 3; a = ‘,a); writeln; b := 6; writeln(‘b := 6; b = ‘,b); r /= 2; writeln(‘b /= 2; b = ‘,b); end.
для нескольких заданных x.
begin writeln(‘Введите значение x’); var x:=ReadReal; var a:=(x-3)*(x-3)*(x-3); var y:= 5*sqr(a)-8*a+2; writeln(‘Значение функции для x = ‘, y); end.
Задача abc_net 1. Найдите расстояние между двумя точками с заданными координатами (x1,y1) и (x2,y2) на плоскости. Расстояние вычисляется по формуле:
Проверьте правильность вашей программы на следующих значениях:
Базовые типы и методы внутри стандартных типов
Для обращения к методам используется точечная нотация:
Исключение — управляемая ошибка, которую можно перехватывать и погашать.
то нужно просто заменить a, b на , :
WritelnFormat(‘ + = + = ’, a, b, x + y)
Стандартные функции
Обмен значениями переменных происходит без использования буферной переменной:
Поиск максимального и минимального значения:
Операции целочисленного деления и остатка
То есть, число N div K показывает, сколько полных раз K «помещается внутри» N.
Число N mod K показывает, что «остаётся от N» после того, как из него «убрали» максимальное число фрагментов размером K.
Работа с отдельными цифрами числа
begin var a := abs(readinteger); // модуль числа println(a div 100 + (a div 10) mod 10 + a mod 10); end.
Приведите лог работы программы с одним из введенных чисел в форме комментария.
Логические выражения и условный оператор
Логические переменные и выражения
Логическое выражение после его вычисления возвращает значение True (истина) или False (ложь).
Логическое выражение может включать:
begin var (a, b) := readinteger2; println(a > b); end.
Чаще всего логические выражения используются внутри условного оператора, который выполненяет определённые действия в зависимости от истинности выражения:
Короткая форма условного оператора:
if then // выполнится, если возвращает True
При использовании нескольких операторов в одном условии необходимы операторные скобки begin..end :
Важно: Не следует ставить точку с запятой перед else
begin var a := readinteger; if (a > 0) then a := a + 1 else a := a — 1; println(a); end.
Рассмотрим оператор на примере:
Вводится номер единицы длины (целое число в диапазоне 1–5) и длина отрезка в этих единицах (вещественное положительное число). Найти длину отрезка в метрах.
begin var n := readinteger(‘Введите номер единицы:’); var a := readreal(‘Введите длину в заданных единицах:’); case n of 1: a /= 10; // дециметр 2: a *= 1000; // километр 4: a /= 1000; // миллиметр 5: a /= 100; // сантиметр end; println(‘Длина в метрах:’, a); end.
Комбинация клавиш | Описание |
---|---|
Ctrl + S | Сохранение |
F1 | Справка |
Ctrl + Shift + F | Форматирование кода |
Перед чтением данной статьи Вы должны быть уверены в том, что у Вас есть какие-либо знания по программированию.
Содержание
Программы в данной IDE строятся так:
Константы [ править ]
В данной секции располагаются определенные пользователем константы. Синтаксис объявления констант выглядит так:
Секция «var» [ править ]
Данная секция предназначена для переменных и массивов. Переменные объявляются так:
Простейшие типы [ править ]
Тип строка [ править ]
Тип строка — это тип переменных, который позволяет хранить в переменной любой текст. Объявление строковой переменной:
Строки могут быть не более 255 символов. Изначальное значение строковых переменных — это «пустая строка» — ».
Операция | Описание |
---|---|
s1 + s2 | Объединение строк |
s1*n | Дублирование строки n раз |
Тип целое число integer [ править ]
Операция | Описание |
---|---|
a + b | Сложение чисел |
a — b | Разность чисел |
a * b | Произведение чисел |
a div b | Целочисленное деление |
a mod b | Остаток от деления |
Тип вещественное число real [ править ]
Декларация переменной типа real:
Пример присваивания переменной данного типа:
Операция | Описание |
---|---|
a + b | Сложение чисел |
a — b | Разность чисел |
a * b | Произведение чисел |
a / b | Частное чисел |
Тип символ [ править ]
Тип символ или «char» используется в основном для хранения одного любого символа вне зависимости от того, является ли данный символ буквой или цифрой. Объявление переменной символьного типа:
Секция «begin — end» [ править ]
Данный раздел программы содержит все команды, выполняемые при ее запуске. Данная секция программы выглядит так:
Комментарии [ править ]
Комментарий — это часть кода, которую игнорирует компилятор. Он создается следующим образом:
Массивы [ править ]
Массивы — это именованный список элементов одного типа.
P. S. Для работы с массивами существует учебный модуль Arrays.
Статические [ править ]
Статические массивы имеют фиксированный размер. Общий синтаксис объявления данных массивов выглядит так:
, где N — длина массива.
Матрицы [ править ]
Двумерные [ править ]
Матрица — это n-мерный список значений, имеющий свой тип и ограниченный некоторыми значениями. Пока будем рассматривать только статические двухмерные и трехмерные матрицы. Перед тем, как перейти к их изучению вспомни таблицы в Excel. Каждая таблица имеет свой размер — ширину и длину. Возьмем за правило ассоциировать двухмерные матрицы с таблицами. Объявление матрицы:
, где N, M количество строчек и столбцов соответственно.
Трехмерные [ править ]
Трехмерный матрицы обладают третьим измерением:
N-мерные матрицы [ править ]
Декларация N-мерной матрицы:
, где A..Z означают количество элементов в соответствующем измерении.
Статические и динамические массивы [ править ]
Динамические массивы позволяют управлять количеством элементом в каждом из их измерений во время выполнения программы.
Пример объявления массива: | Статический | Динамический | Вызов SetLength (для динамического массива) |
---|---|---|---|
Векторный |
Понятие индекса массива [ править ]
Индекс массива — это номер элемента массива. Индекс может принимать значения [0, N — 1], где N — количество элементов некоторой размерности. Обращение к элементу одномерного массива с некоторым индексом:
Составим таблицу, которую следует запомнить:
Где i, j, k — индексы.
Индекс в виде значения элемента массива [ править ]
Индексом может быть значение элемента массива:
Операторы, стандартные процедуры и функции [ править ]
Вывода на экран [ править ]
Вывод текста [ править ]
Вывести текст — это значит отобразить текст на экране. Общий синтаксис для вывода текста выглядит так:
Вывод значений переменных [ править ]
Вывод значений произвольного количества переменных:
Для перехода на новую строку после вывода последнего значения используйте Writeln вместо Write.
Ввод данных с клавиатуры [ править ]
Чтение с клавиатуры — это процесс ввода данных с клавиатуры и запись в соответствующий элемент программы этих данных. Элементами программы являются как переменные, так и элементы массивов. Тип данных, вводимых с клавиатуры, должен соответствовать типу элемента, в который записываются данные с клавиатуры. Использование Readln для чтения с клавиатуры и перехода на новую строку:
Условный оператор [ править ]
Общий синтаксис условного оператора if:
Команды . будут выполнены только при истинности условия.
Сравнение [ править ]
Условные обозначения в программировании операций сравнения приведены в таблице:
Общий синтаксис сравнения двух величин:
Оператор case [ править ]
Оператор case используется для сопоставления значения некоторого выражения с константными значениями:
Если некоторое i-тое константное выражение совпадает с значением выражения, то i-ая группа операторов будет выполнена. Группа операторов после else будет выполнена, если значение выражения не совпало ни с одной из констант. begin — end не нужны, если после двоеточия только один оператор.
Оператор цикла while [ править ]
Оператор цикла позволяет выполнять группу операторов (или один) циклически пока условие является истинным.
Счетчик [ править ]
«Счетчик» — это оператор цикла for, выполняющий группу операторов определенное количество раз. Общий синтаксис оператора цикла for:
Если второе значение меньше первого — используйте downto вместо to.
Оператор break [ править ]
Для выхода из цикла можно использовать break:
Новая итерация цикла [ править ]
Для завершения текущей итерации цикла и начала другой используйте оператор continue.
Функции [ править ]
Общий синтаксис описания функции:
Можно устанавливать значение переменной Result для указания возвращаемого значения.
Основы программирования — первый семестр 08-09
Содержание
Алгоритм
Алгоритм — набор команд, определяющих порядок действий для решения поставленной задачи.
В частности, процессор компьютера выступает исполнителем машинных команд.
Свойства алгоритма
Алгоритм 1. (словесное описание)
Алгоритм 2. (псевдокод)
Эквивалентными называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных. Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.
Спецификация задачи — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
Способы описания алгоритмов
Пример. А.2., представленный блок-схемой.
4. Язык программирования (ЯП)
Для языка программирования команды алгоритма называются операторами или инструкциями.
Основные характеристики алгоритма
Основные характеристики программы
Те же, что и у алгоритма, а также:
Обзор современных языков программирования
(самостоятельно на форуме)
Язык программирования PascalABC.NET
Правила записи программ на PascalABC.NET
Пример программы, вычисляющей длину и площадь круга
Структура программы на языке Паскаль
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
Система программирования PascalABC.NET
Общая характеристика PascalABC.NET.
Отличия языка PascalABC.NET от обычного языка Паскаль.
Компиляторы и интерпретаторы
Схема компиляции в машинный код
Схема компиляции в промежуточный код. JIT-компиляция
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
Синтаксис и семантика ЯП
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
Определения
Синтаксис — формальные правила описания конструкций ЯП.
Семантика — описывает смысл конструкций ЯП, а также задает ряд ограничений.
Способы описания синтаксиса
называют терминалами (лексемами) — это «конечные символы», т.е. по умолчанию известные в ЯП.
Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.
Замечание 1. Способы 1-3 эквивалентны.
Замечание 2. Синтаксис определяет лексемы языка.
Лексемы Паскаля
Переменные и их описание
Основные сведения
Переменная — это ячейка памяти компьютера, имеющая имя и тип.
Тип определяет размер переменной и множество принимаемых ею значений.
В языке Pascal любая переменная перед использованием должна быть описана.
Обычно переменные описываются в разделе описаний.
Синтаксис в виде РБНФ
Пример секции описания переменных.
Внутриблочные переменные
В PascalABC.NET возможно внутриблочное описание переменных:
В последнем случае происходит автоопределение типов.
Основные типы
Основные операторы
Оператор присваивания :=
Синтаксис
Пример использования оператора присваивания.
Семанитика
Вычисляется выражение в правой части, при этом, вместо имен переменных подставляются их значения.
Затем результат вычисления записывается в переменную в левой части.
Ограничение. Тип выражения должен быть совместим по присваиванию с переменной.
Например:
Операторы присваивания += и *=
Примеры использования :=
Пример 1. Перемена местами двух значений. Дано: x, y;
Это стандартное решение. В PascalABC.NET на основе этого алгоритма определена стандартная процедура Swap(x, y).
Однако, существуют и другие решения. Например:
Пример 2. Использование промежуточных переменных в вычислениях Дано: x: real; Найти: x 15 ;
Заметим, что в первом решении используется 6 операций умножения, в во 2м и 3м — 5. Возникает задача: найти x n за минимальное число умножений.
Об этом читай тему.
Оператор ввода
Синтаксис
Семантика
Имеются также стандартные функции ReadInteger, ReadReal, ReadlnInteger, ReadlnReal:
С процедурой ввода связан ряд ошибок времени выполнения (например, если переменная используется в качестве делителя, и вводится 0, или, если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.
Оператор try/except и обработка ошибок ввода
Синтаксис
Семантика
Если внутри блока try происходит ошибка выполнения, то все последующие операторы в блоке игнорируются, и выполнение программы переходит к блоку except. По выходе из except программа продолжает работу.
Если ошибки не происходит, то выполняются все операторы в блоке try, блок except не выполняется, и программа продолжает работу.
Оператор вывода
Синтаксис
Семантика
Выражения в списке вычисляются, и их значения выводятся на экран.
В случае writeln после вывода осуществляется переход на новую строку.
Форматы вывода
После каждого выражения в списке вывода можно использовать формат вывода в виде :a, где a — выражение целого типа.
После вещественного типа — :a:b (a задает ширину поля вывода (выравнивание по правому краю), b — количество знаков в дробной части).
Вывод с помощью write[ln]Format
Пример вывода с использованием форматной строки.
В форматной строке тоже можно использовать формат вывода.
: 10 — это ширина поля вывода
: 3 — это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).
— экспоненциальный формат.
Арифметические выражения
Основные сведения
Каждое выражение имеет тип. Выражение называется арифметическим, если его тип — числовой.
Выражение строится посредством операций (унарных или бинарных) и операндов.
В арифметических выражениях если a и b — одного типа, то и a op b принадлежит к тому же типу. Исключением является операция "/":
Если a и b принадлежат к различным типам, то выражение принадлежит к "старшему" типу.
Например:
Стандартные функции
В арифметические выражения могут входить стандартные функции:
Порядок выполнения операций в арифметических выражениях
Операции div и mod для целых
Пример использования
Целочисленные операции часто применяются для определения четности числа:
Логические выражения
Основные сведения
Выражение назывется логическим, если оно имеет тип boolean.
Пример.
Это простые логические выражения. Однако, с помщью логических операций можно составлять сложные.
Таблицы истинности логических операций
Сокращение вычислений логических выражений
Большинство современных компиляторов, в т.ч. PascalABC.NET производит сокращенное вычисление логических выражений.
Это означает, что в выражении
если a — ложно, то b не вычисляется, а в
если a — истинно, b не вычисляется.
Это очень полезно при вычислении таких выражений, как, например,
Логически здесь все верно, однако, если бы не использовалось сокращенное вычисление, в случае равенства нулю y'а возникала бы ошибка деления на ноль.
Логические переменные
Можно описывать логические переменные (тип boolean). Им можно присваивать логические выражения.
Эти переменные принимают одно из двух возможных значений:
Пример использования логических переменных
Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон (x1, x2) и ординатами горизонтальных (y1, y2); точка M( x, y );
Найти: находится ли точка внутри прямоугольника, снаружи, или лежит на границе;
Побитовые операции
Побитовые операции and, or, xor, not
Замечание. Работают только с целыми.
Соответствующая операция применяется к каждому биту двоичного представления числа.
Пример.
Операции shl и shr
Побитовый сдвиг влево и сдвиг вправо соответственно.
Сдвигает двоичное представление x на n позиций влево.
Сдвигает двоичное представление x на n позиций вправо.
Примеры
Таблица приоритетов операций языка Object Pascal
Условный оператор
Синтаксис
Семантика
Примеры использования для решения задач
Пример 1. Нахождение минимума
Дано: x, y
Найти: min
Пример 3. Вычисление функции по взаимоисключающим веткам
Замечание. Если по ветви else располагается другой оператор if, то говорят, что возникает цепочка вложенных операторов if.
Координаты средней точки
Достаточно рассмотреть случай, когда координаты точек равны 1,2 и 3
Рассмотрим все возможные ситуации распределения этих значений между a,b,c:
При a b возможны три варианта, в двух из которых a>c.
Решение представляется вложенными операторами if с уровнем вложенности 3.
То же решение, записанное с помощью функции min:
Данное решение менее эффективно по числу сравнений и присваиваний (посчитайте самостоятельно), но по понятности может восприниматься лучше предыдущего.
Самостоятельные задания
Оператор case выбора варианта
Синтакстис
Семантика
Ограничения
НО НЕ строковый или вещественный.
Примеры использования оператора выбора
Пример 1. День недели
Пример 2. Цифра или буква
Циклы
Циклы с предусловием (while) и постусловием (repeat)
Синтаксис цикла while
Семантика цикла while
Синтаксис цикла repeat
Семантика цикла repeat
Зацикливание
Зацикливание происходит, если:
Итерация — однократное повторение тела цикла.
Отличия между циклами while и repeat
тело может не выполниться ни разу
тело выполнится хотя бы один раз
Примеры
Пример 1. Сумма нечетных двузначных чисел
С использованием while
С использованием repeat
С использованием repeat
С использованием while
Моделирование repeat с помощью while
Моделирование while с помощью repeat
Оператор цикла с параметром (for)
Синтаксис
Семантика
Ограничения:
Дополнительные возможности PascalABC.NET
Возможно описание переменной цикла в его заголовке:
Возможно автоопределение типа при описании:
Переменная цикла, описанная в заголовке цикла, определена только внутри цикла.
Замечание. Значение переменной цикла после завершения цикла не определено. Именно поэтому рекомендуется описывать переменную цикла в заголовке цикла.
Примеры использования циклов
Выдать таблицу значений в точках разбиения.
Дальнейшее решение с помощью for:
Дальнейшее решение с помощью while:
Погрешность при работе с вещественными числами
Замечание. Вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при представлении вещественного числа в памяти, называется ошибкой округления Ошибка, которая возникает в результате вычислений с вещественными числами, называется вычислительной погрешностью.
Минимальное положительное вещественное число называется машинным эпсилон и задается константой real.Epsilon
Вывод. Вещественные числа нельзя сравнивать на равенство, можно только на больше/меньше.
Рекуррентные соотношения
Говорят, что последовательность данных
является рекуррентной, если
Вывод степеней двойки
Последовательность Фибоначчи
Вычисление НОД (алгоритм Евклида)
Суммирование рядов (конечных и бесконечных)
Найдем рекуррентную связь между ai:
Для вычисления суммы бесконечного ряда в простейшем случае используют следующий метод:
задается некоторый малый eps и сумма вычисляется, пока \ eps" src="http://it.mmcs.sfedu.ru/_wiki/images/math/e/7/2/e7227a331377c62ff63fcf2163cd66d5.png" />
Нахождение max в последовательности чисел
Разложение целого числа на простые множители
Будем делить x на p, начиная с p = 2. Если делится нацело, то p — множитель, если не делится, то увеличиваем p на 1, пока x <> 1.
Операторы break и continue
break — оператор досрочного завершения цикла.
continue — оператор досрочного завершения текущей итерации цикла.
Примеры использования циклов (продолжение)
Поиск заданного значения среди введенных
Решение 1. С использованием оператора break
Обработка последовательности, завершающейся нулем
Вводятся числа. Конец ввода — ноль.
Найти сумму и произведение положительных чисел.
Вычисление значения многочлена. Схема Горнера
Необходимо вычислить если
Это решение использует 2(n + 1) умножений.
Однако есть и другое решение — схема Горнера. Оно основана на том, что
Итого — всего n умножений.
Поиск нуля функции на отрезке
Требуется найти корень уравнения f( x ) = 0
Метод последовательной детализации
Задача. Вывести все простые числа Метод окаймления
Метод окаймления заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "размораживая" некоторый параметр.
Итак, пусть A — фиксировано( "заморожено" ).
Теперь размораживаем A:
Переборные задачи
Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
Вспомогательные алгоритмы
Вспомогательный алгоритм — это алгоритм, который используется для реализации другого алгоритма.
Вспомогательные алгоритмы имеют:
Если один из выходных параметров возвращается особым образом, так что алгоритм можно использовать в выражении, то такой алгоритм называется алгоритмом-функцией.
В программировании вспомогательные алгоритмы называются подпрограммами и делятся на:
Важно. Подпрограммы позволяют избежать дублирования кода при решении однотипных задач. Алгоритм один раз описывается, а затем может быть многократно вызван с различным набором параметров из другого алгоритма.
Процедуры
Пример.
Даны 3 пары положительных чисел.
Найти их среднее арифметическое и среднее геометрическое.
Очевидно, удобно сделать подпрограмму, которой бы на вход подавались два числа, а выходными параметрами являлись их среднее арифметическое и среднее геометрическое соответственно.
называется заголовком процедуры.
Теперь можем многократно использовать описанную процедуру в основной программе:
называется оператором вызова процедуры.
Синтаксис описания процедуры
Замечание. Pascal допускает внутренне описание подпрограмм (вложенность подпрограмм)
Синтаксис вызова процедуры
Семантика вызова процедуры
Входно-выходные параметры
Параметр x называется входно-выходным, если его значение необходимо в начале алгоритма, оно модифицируется алгоритмом и возвращается в вызывающую программу.
Входно-выходные параметры описываются с ключевым словом var, как и выходные.
Пример 1. Увеличение значения переменной на заданное число.
Пример 2. Перемена местами значений двух переменных.
Функции
Функции являются другой разновидностью подпрограмм. Это подпрограмма, возвращающая одно значение особым образом так, что ее вызов можно использовать в выражении.
Точнее, — вызов процедуры является оператором, а вызов функции — выражением.
Пример. Функция sgn(x) — знак числа
называется заголовком функции, а integer — это тип возвращаемого значения.
В каждой функции неявно определена переменная Result, хранящая возвращаемое значение функции и имеющая тот же тип. Присваивание значения Result в теле функции обязательно по всем ветвям алгоритма.
Выведется непредсказуемое значение, находящееся в этот момент в памяти, т.к. по ветке
переменная Result не инициализируется.
Пример. Считывание значения с клавиатуры.
Сравнение использования процедуры и функции
Пример. Сумма первых N натуральных чисел.
Синтаксис описания функции
Синтаксис вызова функции
Семантика
Замечание. Формальные параметры функции не рекомендуется делать параметрами-переменными.
Считается, что функция должна вычислять и возвращаеть результат, и более ничего не делать.
Если функция возвращает результат и выполняет дополнительное действие, которое сказывается вне функции, то такие действия называются побочным результатом вызова функции.
Правило. В подавляющем большинстве случаев функция не должна иметь побочный эффект.
Оператор exit
Оператор exit — оператор досрочного завершения подпрограммы.
Пример. Поиск числа k среди n введенных.
Замечание. Оператор exit, в отличие от break, позволяет завершить подпрограмму и выйти сразу из нескольких вложенных циклов. При вызове его в теле основной программы программа завершается.
Локальные и глобальные переменные
Замечание. Локальная переменная, описанная в процедуре или функции, может иметь то же имя, что и глобальная переменная.
Если глобальная описана ранее, то её имя внутри процедуры становится недоступным.
Глобальные переменные по умолчанию инициализируются 0, а локальные по умолчанию не инициализируются.
Локальная переменная Result в функции по умолчанию также не инициализируется.
writeln(n) выведет непредсказуемый результат; writeln(m) выведет 0;
Пространство имен
Область программы, в которой не может быть описано двух объектов с одинаковыми именем, называется пространством имен.
Формальные параметры подпрограммы являются локальными по отношению к этой подпрограмме.
Примеры допустимых и недопустимых описаний:
Область видимости и время жизни объекта
Время жизни переменной — время, в течение которого существует отведенная ей память.
Область видимости переменной — область в программе, в которой можно обратиться к переменной по имени.
Побочный эффект
Побочным эффектом подпрограммы называется также любое изменение глобальных переменных (или параметров для функции).
Замечание. Если подпрограмма желает изменить глобальную переменную, то в большинстве случаев эту переменную следует передать как параметр.
Принцип локальности
Принцип локальности — эмпирический принцип, по которому переменную следует описывать и впервые инициализировать в том месте алгоритма, где она начинает впервые использоваться.
Обычно входные и выходные данные описываются, как глобальные переменные, после всех подпрограмм (если эти подпрограммы их не используют). В начале текста программы обычно используются переменные и константы, инициализируемые каким-то значением, которое легко поменять при следующих запусках этой подпрограммы.
Пример. Вычислить произведениe целых чисел от a до b.
Решение 1.
Второе решение является более масштабируемым, чем первое, поскольку алгоритм вычисления произведения расположен непрерывно в тексте программы, и его можно легко превратить в подпрограмму.
Подпрограммы (продолжение)
Внутренний механизм передачи параметра-переменной
b, i: фактические параметры при вызове MyInc a, n: формальные параметры (a — параметр-переменная; n — параметр-значение)
При передаче параметра-значения i в соответствующий формальный параметр копируется значение i.
А вот механизм передачи параметра-переменной называется передачей по ссылке.
Ссылкой обычно называют другое имя некоторого объекта.
Для параметра-переменной имя соответствующего формального параметра выступает в роли ссылки на переменную-фактический параметр.
Все, что происходит со ссылкой внутри подпрограммы происходит и с самим объектом вне подпрограммы, поскольку это один и тот же объект.
При передаче параметра по ссылке в подпрограмму передается не сама переменная, а её адрес:
Замечание 1. В 32-битных ОС размер адреса — 4 байта, это позволяет адресовать примерно 4 Гб операционной памяти.
Замечание 2. Размер адреса не зависит от размера переменной, поэтому при передаче параметров большого размера их предпочитают передавать по ссылке.
Перегрузка имен подпрограмм
Предположим, у нас описана процедура:
Возможно ли описать процедуру с таким же именем, параметры которой были бы вещественными? Да, возможно:
Таким образом, в одном пространстве имен можно описать несколько подпрограмм с одним именем, но разными типами или количеством формальных параметров.
При вызове такой подпрограммы на этапе компиляции типы фактических параметров сравниваются с типами формальных для всех версий этой подпрограммы и выбирается наиболее подходящая.
Замечание 1. Тип возвращаемого значения функции не участвует в операции разрешения перегрузки.
Версии подпрограммы с одним именем называются перегруженными, а определение того, какую версию выбрать — разрешением перегрузки.
Замечание 2. Разрешить перегрузку можно не всегда.
Пример.
Замечание 3. В процессе разрешения перегрузки происходит неявное преобразование типов.
Параметры по умолчанию
Параметры по умолчанию обязательно должны находиться последними в списке параметров. Если при вызове не указывать этот параметр, будет использовано значение по умолчанию.
Замечание. Параметры по умолчанию корректно сочетаются с перегрузкой.
Предварительное объявление подпрограмм
Такое описание вызовет ошибку компиляции, т.к. в p используется еще не известная процедура. Чтобы таких ошибок не возникало, нужно использовать предварительное объявление подпрограммы:
forward-объявление делается для подпрограмм, которые обязательно будут описаны ниже. Если программа не будет описана в этом же файле, то, в конце компиляции этого файла, мы получим ошибку компилятора о forward, который был объявлен, но не описан.
Процедурные переменные
Процедурный тип и переменные
Переменная называется процедурной если ей можно присваивать процедуры или функции указанного типа.
После присваивания процедурной переменной имени процедуры, эта процедура может быть вызвана через переменную:
Такой способ вызова процедуры является чрезвычайно гибким, поскольку позволяет менять вызываемое действие в процессе работы программы.
Замечание. До первого присваивания процедурная переменная имеет тип nil. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.
Функции обратного вызова (callback)
Процедурные переменные могут являться параметрами других процедур.
При вызове этих процедур им на вход в качестве параметров передаются имена процедур, которые будут вызваны позже внутри основной процедуры. Другими словами, мы передаем в процедуру действие, которое должно быть вызвано (будет вызвано) в определенный момент в этой процедуре.
Такой вызов называется обратным вызовом (callback).
Примечание. Прямой вызов — это передача процедуры в качестве параметра.
Пример. Вычисление определённого интеграла методом прямоугольников.
Вызов нескольких процедур через процедурную переменную
Замечание 2. Подобный механизм не имеет смысла использовать для функций;
Методы разработки подпрограмм
Пример. Вывести таблицу простых чисел Метод разработки сверху вниз
После этого реализуем функцию IsPrime;
Этот метод используется, когда:
Замечание. В коде главной программы имеются вызовы других подпрограмм, которые реализуются позже (возможно, другими разработчиками);
На период, пока они не написаны, вместо них могут использоваться «заглушки» (подпрограммы с тривиальными телами).
Код каждой разрабатываемой подпрограммы также может разрабатываться методом сверху вниз.
Метод разработки снизу вверх
Метод используется, когда:
Замечание 1. Написание самых «нижних» подпрограмм позволяет лучше войти в предметную область;
Замечание 2. С какого-то момента разработка хотя бы упрощенного главного алгоритма становится необходимой;
Оператор goto
Синтаксис
Метка представляет собой идентификатор или целое положительное число.
Метка должна описываться в разделе описаний меток в виде:
Семантические ограничения
Пример плохого кода
Однако, бывают ситуации, когда удобно использовать оператор goto, например, чтобы выйти из нескольких циклов.
Введение
С каждой выполняющейся программой связан блок памяти, выделяющийся ей в начале работы и называемый программным стеком.
Программный стек используется для хранения значений всех переменных, констант, а также промежуточных значений в процессе выполнения.
Устройство ЗА подпрограммы
Штриховкой отмечены поля, заполняемые до запуска п/п.
Алгоритм входа в подпрограмму
Алгоритм выхода из подпрограммы
Пример
После запуска программы ОС записывает код этой программы в оперативную память и выделяет дополнительный участок памяти для данных, называемый программным стеком.
При перемещении top на программном стеке накапливается мусор, потом в этот мусор опять записывается ЗА.
Коды top и current хранятся в специальных регистрах.
Вывод 1. Если подпрограмма — маленькая, то накладные расходы на её вызов могут существенно превысить время работы самой подпрограммы.
Вывод 2. Если локальные переменные или формальные параметры, передаваемые по значению имеют большой размер, то ЗА соответствующей подпрограммы будет большой. В результате при нескольких вложенных вызовах таких подпрограмм может произойти переполнение программного стека (Stack overflow), т.к. программный стек не увеличивается в размерах, а память под него выделяется один раз.
Выход. Большие параметры по этой причине рекомендуется передавать не по значению, а по ссылке, при этом на стек копируется не содержимое параметра, а его адрес.
Замечание. Адреса глобальных переменных, используемых в подпрограммах вычисляются по некоторому алгоритму на этапе выполнения, следовательно, обращение к глобальным переменным происходит дольше, чем к локальным.
Дополнительные сведения о подпрограммах
Переменное число параметров подпрограмм
Шаблоны подпрограмм
Модули
Введение
Модуль — это совокупность взаимосвязанных процедур, функций, типов, переменных и констант, предназначенных для решения ряда однотипных задач, и помещенных в специальным образом оформленный файл.
Модули разбивают большой проект на относительно независимые части, при этом, каждая часть "живет своей жизнью": модуль, написанный для одного программного проекта, может быть использован в другом программном проекте.
Различают модули в виде исходных текстов и откомпилированные модули.
Откомпилированные модули уменьшают суммарное время компиляции и позволяют скрывать программный код от модификации.
Программа, подключающая модуль MyLib
Модуль в языке Object Pascal состоит из двух разделов:
В разделе интерфейса описываются все
которые можно будет использовать в других модулях, подключающих данный.
В разделе реализации содержится
которые нужны для реализации подпрограмм из раздела интерфейса и не видны из других модулей.
Данный принцип получил название принципа сокрытия информации.
Его преимущества:
Синтаксис модуля
Семантические ограничения
Разделы инициализации и финализации модуля
Операторы в разделе initialization модуля выполняются раньше тела основной программы,
а операторы в разделе finalization выполняются после основной программы.
Т.е. последовательность выполнения будет такой:
Примечание. В разделе инициализации обычно инициализируются глобальные переменные из раздела интерфейса.
Схема компиляции программы с модулями
1. Компилируется файл основной программы.
2. Если в нем встречена секция uses, то компилируются модули из этой секции слева направо.
3. Каждый модуль компилируется так же, как и основная программа по пунктам 1-2:
Если в модуле подключаются другие модули, то компилируются они, и так происходит до тех пор, пока компилятор не дойдет до модулей, не содержащих подключения других модулей.
4. По окончании компиляции модуля его откомпилированный вариант (.pcu в PascalABC.NET) записывается на диск.
5. После записи откомпилированного модуля на диск компилятор возвращается к основному модулю (вызывающему) или программе, и докомпилирует его до конца. Основная программа после компиляции хранится в оперативной памяти.
6. Первый этап компиляции закончен. Начинается заключительный этап компиляции — линковка (компоновка). Специальная программа — линковщик — собирает из откомпилированных модулей единый исполняемый файл (.exe в Windows).
Замечание 1. Ошибки могут происходить как на этапе компиляции, так и на этапе, собственно, линковки.
Замечание 2. Наличие откомпилированного файла модуля существенно ускоряет процесс компиляции (сводя его к процессу линковки).
Замечание 3. Если есть откомпилированные файлы модулей, то исходные тексты модулей можно удалить. При этом компилятор проанализирует, что данный модуль откомпилирован, и продолжит компиляцию дальше.
Замечание 4. Если файл модуля .pas создан после откомпилированного файла модуля (.pcu), то произойдет его перекомпиляция.
Замечание 5. При работе в интегрированной среде компилятор в первую очередь берет тексты модулей из открытых файлов и только затем смотрит файлы на диске.
Примечание 1. Файлы модулей могут храниться в другом каталоге относительно файла исходной программы. Тогда надо вместе с именем модуля указывать, в каком каталоге он хранится (тогда имя модуля и имя файла модуля могут не совпадать):
Примечание 2. Откомпилированные файлы модулей по умолчанию создаются:
Кроме этого, стандартные откомпилированные модули хранятся в специальной папке, например, в PascalABC.NET — в папке \LIB. Если модуль претендует на звание стандартного, его можно туда поместить.
Упрощенная структура модуля
В PascalABC.NET можно использовать упрощенную структуру модуля:
В описываются типы, константы, переменные и подпрограммы.
Раздел begin + соответствует разделу инициализации.
Алгоритм поиска имен в модулях
В разных модулях могут находиться объекты с одинаковыми именами, т.к. модуль является пространством имен.
Как же осуществляется поиск имен в модулях?
Правило 1. Имя вначале ищется в текущем модуле. Если не найдено, то в подключенных модулях секции uses справа налево.
Правило 2. Если нужно явно указать переменную из какого-то модуля, то перед ней ставится .
Стандартный системный модуль PABCSystem
В каждой среде программирования на Pascal имеется стандартный системный модуль, который неявно первым подключается к любой программе или модулю.
В Delphi — это System,
в PascalABC.NET — PABCSystem.
Библиотеки
Сходства с модулем
Библиотеки, как и модули:
В Windows получили распространение библиотеки .dll (dynamically linked libraries). Они находятся либо в текущем каталоге приложения (локальные), либо в системном каталоге (глобальные библиотеки).
Глобальными библиотеками могут пользоваться одновременно несколько приложений.
Отличия библиотек от модулей
Библиотеки в PascalABC.NET
Замечание. В библиотеках отсутствуют секции инициализации и финализации.
Для подключения библиотеки используются конструкции:
Примечание. reference — директива компилятора. Указывает компилятору, что программа использует внешние библиотеки, расположенные в файле MyLib.dll.
Документирующие комментарии ///
Документирующие комментарии предназначены для пояснения задач, решаемых подпрограммами.
Документирующие комментарии в PascalABC.NET
Отображаются в виде всплывающего окна при наведении указателя на имя подпрограммы.
Синтаксис
Чтобы воспользоваться документирующими комментариями, необходимо перед заголовком подпрограммы использовать следующую конструкцию:
Для того, чтобы активизировать документирующие комментарии в библиотеках, нужно использовать директиву
Перечислимый тип
Определение и примеры
Переменные перечислимого типа хранятся в памяти, как целые числа. Первому значению соответствует 0, второму — 1, и т.д.
Замечание. Все имена из определения перечислимого типа помещаются в текущее пространство имен.
Переменная перечислимого типа может служить параметром цикла for, а также переключателем в операторе case.
Стандартные подпрограммы для работы с перечислимым типом
Замечание. Тип boolean = (False, True)
Если не инициализировать глобальную переменную перечислимого типа, то по умолчанию она получает значение первой константы типа.
Диапазонный тип
Диапазонный тип строится на базе
Массивы
Введение
Как и диапазонный тип, индексы могут иметь типы:
Кроме того, в качестве индекса может выступать порядковый тип, например:
Обращение к элементам массивов
Чтобы обратиться к элементу массива, нужно использовать конструкцию
В некоторых компиляторах можно специальными директивами отключить проверку выхода за границы диапазона, это увеличивает скорость выполнения.
В PascalABC.NET проверка выполняется всегда. А вот в Delphi и Free Pascal существует соответствующая директива
Динамические массивы
Динамическим называется массив, память под который выделяется в процессе работы программы. В pascalABC.NET имеются встроенные динамические массивы, которые описываются следующим образом:
Выделение памяти
Для выделения памяти динамическому массиву имеется два варианта. Объектный стиль:
Здесь n может быть не только константой, но и переменной.
В обоих случаях элементы массивов заполняются нулями.
До выделения памяти в переменной-динамическом массиве хранится специальное значение nil. Присваивание nil переменной-массиву приводит к освобождению памяти, им занимаемой:
При попытке использования неинициализированного динамического массива выдается исключение времени выполнения "System.NullReferenceException: Ссылка на объект не указывает на экземпляр объекта."
Перевыделение памяти
В процессе работы можно изменить память, занимаемую динамическим массивом. Для этого следует повторно вызвать SetLength:
При этом старое содержимое массива будет сохранено.
Длина массива
Чтобы узнать количество элементов в динамическом массиве, следует воспользоваться функцией Length:
или свойством Length:
Таким образом, элементы динамического массива:
Циклы по массиву
или с помощью цикла foreach (для каждого)
В цикле foreach доступ к элементам массива осуществляется только на чтение.
Инициализация массивов
Элементы массива можно инициализировать при описании:
При этом под массив автоматически выделится память: в данном случае под 3 элемента.
Хранение массивов в памяти
Присваивание и сравнение массивов
Именная и структурная эквивалентность типов
Передача массивов в качестве параметров подпрограмм
При передаче статического массива должна соблюдаться именная эквивалентность
Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово const, которое также запрещает изменять данные внутри п/п.
Динамический массив можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива. Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
Массив как возвращаемое значение функции
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
Переменное число параметров подпрограмм
П/п можно создавать с переменным количеством параметров. Для этого исп. ключевое слово params. При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним. Пар-р params может быть только один и должен находиться последним в списке пар-ов.
Обобщенные подпрограммы
Часто требуется выполнять одно и то же действие для разных типов данных. В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
В момент вызова п/п происходит:
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
Массивы (продолжение)
Задачи на одномерные массивы
можно с for и break,
Задачи на одномерные массивы
pas-файл с задачами
используется тип IArr = array [1..size] of integer
[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]
Задачи с процедурными переменными в качестве параметров
Определяется тип IUnPred = function (x: integer): boolean
Примечание. Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
Сортировки массивов
Сортировка выбором
Пузырьковая сортировка
Сортировка вставками
Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.
Замечание. Рассмотренные виды сортировки не являются самыми эффективными.
Асимптотическая оценка количества шагов алгоритма
Определение. Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1 2 ).
Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
Бинарный поиск в отсортированном массиве
Задачи на двумерные массивы (матрицы)
Замечание. Решать такие задачи можно и реализуя алгоритм полностью, и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.
если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,
иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА К основной странице курса
Записи
Введение
Инициализация записей при описании (на примере Student)
Доступ к полям записей. Точечная нотация.
Замечание. Для записей имеет место именная эквивалентность типов.
Передача записей в подпрограммы. Записи как возвращаемые значения функции
Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).
Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)
Методы в записях
На примере Student.Print.
Запись как пространство имен
Запись выступает для своих полей и методов в качестве модуля (поскольку является набором данных и связанных с ними процедур и функций, оформленных как единое целое).
Методы работают в некотором окружении, в роли которого выступают поля записи и другие методы.
Т.о. возникает понятие инкапсуляции:
Инкапсуляция — хранение в записи одновременно данных и методов (запись представляет собой «капсулу»).
Инкапсуляция тесно связана с защитой данных: лишь некоторые члены в этой «капсуле» являются открытыми.
Создается окружение при описании переменной типа запись.
Создание простейших графических объектов
Для каждого типа определяются методы Print, Draw, MoveOn
Записи как средство упаковки параметров
Пример. Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:
Переменная типа запись как объект
Поля записи как состояние объекта.
Методы записи как действия, воздействующие на состояние объекта.
Методы делятся на две категории
Сортировка массива записей.
Индексная сортировка
Часто физически переставлять элементы массива или вообще невозможно, или долго (в силу достаточно большого размера, например). В этом случае удобно использовать перестановку индексов вместо перестановки самих элементов.
Идея заключается в том, чтобы описать индексный массив index, который взаимооднозначно сопоставляет реальным индексам элемента виртуальные таким образом, чтобы относительно виртуальных массив оказался упорядоченным.
Дан массив целых (с реальными индексами):
А так выглядит отсортированный массив по виртуальным индексам:
Соответственно, алгоритм сортировки меняется таким образом, что вместо перемены местами самих элементов упорядочиваемого массива меняется содержимое элементов index.
Вначале удобно положить элементы index соответствующими тождественной подстановке (т.е. a[i] = i).