В операторе цикла for вместо to может использоваться ключевое слово downto. В этом случае счетчику присваивается убывающая последовательность от начального до конечного значения.
Пример: напечатать на экране 10 восклицательных знаков
for i:=10 downto 1 do write(‘!’);
Основным недостатком цикла for является то, что он позволяет увеличивать или уменьшать счетчик лишь на 1. К его основным преимуществам относятся краткость и возможность использования символьного и перечислимого типов в диапазоне значений.
Пример: напечатать все символы латинского алфавита.
var c: char;
…
for c:=’a’ to ‘z’ do writela(c);
Пример: вычислить сумму чисел от 1 до 100.
var i, sum: integer;
…
sum:=0;
for i:=1 to 100 do sum:=sum+i;
Пример: вычислить факториал 5.
var i, f: integer;
…
f:=1;
for i:=1 to 5 do f:=f*i;
Циклы с предусловием
Оператор цикла с предусловием while вызывает повторяющееся выполнение оператора до тех пор, пока некоторое условие принимает истинное значение.
Записывается цикл while следующим образом:
WHILE <логическое выражение> DO <оператор>;
Пример: возводить x в квадрат, пока он не станет больше 1000.
while x<=1000 do x:=sqr(x);
Логическое выражение вычисляется до того, как Оператор будет выполнен. Если оно возвращает значение Истина, то выполняется Оператор и вновь вычисляется значение Логического выражения.
Если Логическое выражение возвращает Ложь, то выполнение оператора while прекращается.
Оператор выполняется повторно до тех пор, пока выражение принимает значение Тruе. Если выражение с самого начала принимает значение False, то оператор, содержащийся внутри оператора цикла с предусловием, не выполняется ни разу.
Пример: что будет напечатано на экране после выполнения следующих операторов:
s:=0;
i:=1;
while i<3 do
begin
s:=s+i;
i:=i+1
end;
writeln(s);
Рассмотрим значения переменных на каждом шаге.
Шаг | s | i | Описание |
1 | 0 | Присвоили в s ноль | |
2 | 0 | 1 | Присвоили в i единицу |
3 | 1 | 2 | Т. к. 1 (значение i) меньше 3, то выполняется тело цикла: в s записывается сумма текущих значений s и i (0+1=1), а значение переменной i увеличивается на 1 (1+1=2) |
4 | 3 | 3 | Т. к. 2 меньше, чем 3, то вновь выполняется тело цикла: записываем новые значения в s и i |
Далее результатом выражения цикла будет False, поэтому тело цикла более не выполняется, а управление передается следующему оператору – процедуре вывода на экран. Значение переменной s равно 3, следовательно, на экран выведется 3.
Пример: вычислить сумму чисел от 1 до 100.
i:=1;
sum:=0;
while i<=100 do
begin
sum:=sum+i;
i:=i+1; { или inc(i); }
end;
Циклы с постусловием
Оператор цикла с постусловием repeat вызывает повторяющееся выполнение оператора до тех пор, пока некоторое условие не примет истинное значение.
Записывается цикл repeat следующим образом:
REPEAT <операторы> UNTIL <логическое выражение>;
Пример: возводить x в квадрат, пока он не станет больше 1000.
repeat x:=sqr(x) until x>1000;
Между ключевыми словами repeat и until могут быть записаны сразу несколько операторов. Операторы выполняются последовательно до тех пор, пока Логическое выражение не примет значение Истина. Последовательность операторов выполняется, по крайней мере, один раз, т. к. логическое выражение вычисляется после выполнения операторов.
Пример: что будет напечатано на экране после выполнения следующих операторов:
s:=0;
i:=1;
repeat
s:=s+i;
i:=i+1
until i>=3;
writeln(s);
Рассмотрим значения переменных на каждом шаге.
Шаг | s | i | Описание |
1 | 0 | Присвоили в s ноль | |
2 | 0 | 1 | Присвоили в i единицу |
3 | 1 | 2 | В s записывается сумма текущих значений s и i (0+1=1), а значение переменной i увеличивается на 1 (1+1=2). После этого вычисляется результат выражения: при i=2 результат равен False, следовательно, тело цикла выполнится еще раз |
4 | 3 | 3 | Вновь выполняется тело цикла: записываем новые значения в s и i. Затем происходит проверка: на этот раз выражение принимает значение Истина, а это значит, что тело цикла Repeat более выполняться не будет. |
После цикла управление передается следующему оператору – процедуре вывода на экран. Значение переменной s равно 3, следовательно, на экран выведется 3.
Пример: вычислить сумму чисел от 1 до 100.
i:=0;
sum:=0;
repeat
inc(i);
sum:=sum+i;
until i=100;
Имеется три основных различия между циклом while и циклом repeat.
Во-первых, операторы в цикле repeat всегда выполняются хотя бы один раз, поскольку проверка выражения осуществляется не сразу после ключевого слова repeat. Наоборот, в цикл while, если выражение изначально имеет значение False, то пропускается все тело цикла.
Во-вторых, цикл repeat выполняется до тех пор, пока выражение не примет значение Тrue; в отличие от него цикл while выполняется, пока выражение имеет значение Тrue. Это означает, что следует внимательно заменять один тип цикла на другой.
В третьих, цикл repeat может содержать несколько операторов, не образующих составной оператор. Заметьте, что в последней программе не используется begin..end, в то время как в варианте с циклом while это имело место.
Вопросы для самопроверки
1. Опишите принцип работы оператора For.
2. В каких случаях в цикле for используется ключевое слово Downto?
3. Может ли в цикле For использоваться счетчик типа Real? Byte? Char?
4. Назовите 3 основных отличия оператора цикла Repeat от оператора цикла While.
5. Сколько раз выполнится тело следующего цикла: x:=3; while x<5 do inc(x); ?
§9. Пример использования циклов
В данном параграфе рассмотрим несколько типовых задач, которые можно решить с использованием рассмотренных ранее операторов циклов.
Для лучшего усвоения материала рекомендуется самостоятельно «прорешать» представленные примеры (возьмите лист бумаги и карандаш, посмотрите, на каком шаге какие значения в какие переменные будут попадать и что программа напечатает на экране).
Вычисление факториала
Пользователь вводит целое положительное число N. Вычислить факториал от N.
Факториал целого числа N (обозначается N!) – это произведение всех целых чисел в диапазоне от 1 до N включительно. Исключение: факториал 0 равен 1.
Пример: 4! = 1*2*3*4 = 24
Другими словами, задачу можно перефразировать следующим образом: пользователь вводит целое положительное число N. Вычислить произведение целых чисел от 1 до N.
Для решения такой задачи наиболее подходящим будет цикл for, т. к. нам заранее известно количество повторений: от 1 до N, т. е. N раз.
Исходный текст программы в нашем случае будет выглядеть следующим образом.
Пример:
var
N: integer; {число, которое вводит пользователь}
F: integer; {сюда будем вычислять факториал}
i: integer; {счетчик для цикла}
begin
writeln(‘Вычисление факториала N!’);
writeln(‘Введите число N:’);
readln(N);
F:=1; {задаем стартовое значение – инициализируем}
for i:=1 to N do F:=F*i; {в этом цикле и вычисляется факториал}
writeln(N, ‘!=’, F); {печатаем на экране результат}
end.
Суть алгоритма следующая: сначала в переменную F записываем единицу, а затем на каждом шаге домножаем его на новый элемент: на 2, на 3, и т. д., пока не дойдем до N. Для этого используем счетчик i, который внутри цикла for будет как раз принимать значения 1, 2, 3 и т. д. до N (см. начальное и конечное значение). В конце программы не забываем вывести результат на экран.
Вычисление суммы по заданной формуле
Пользователь вводит целое положительное число N. Вычислить сумму 
.
Данная задача аналогична предыдущей. Заводим дополнительную переменную Sum и на каждом шаге цикла добавляем в нее новый элемент – 1/i. Основное отличие – при инициализации в Sum запишем 0, т. к. в данном случае мы имеем дело с суммой, а не с произведением.
Пример:
var
N: integer; {число, которое вводит пользователь}
Sum: integer; {сюда будем считать сумму}
i: integer; {счетчик для цикла}
begin
writeln(‘Введите число N:’);
readln(N);
Sum:=0; {задаем стартовое значение – инициализируем}
for i:=1 to N do Sum:=Sum+1/i;
writeln(‘Sum=’, Sum); {печатаем на экране результат}
end.
Вычисление суммы по формуле с заданной точностью
Пользователь вводит вещественное число x (модуль меньше 1) и точность вычислений eps (от 0 до 1). Вычислить сумму 
с заданной точностью.
В этой задаче уже не удастся использовать цикл for, т. к. мы не знаем, на каком именно шаге будет достигнута заданная точность. Поэтому здесь воспользуемся циклом repeat. Будем считать, что точность достигнута, если очередной элемент будет меньше по модулю, чем заданная точность eps.
Пример:
var
x: real; {число, которое вводит пользователь}
xx: real; {в этой переменной будем хранить x в нужной степени}
eps: real; {точность, которую вводит пользователь}
Sum: integer; {сюда будем считать сумму}
i: integer; {счетчик}
begin
writeln(‘Введите число x (<1):’);
readln(x);
writeln(‘Введите точность вычислений (<1):’);
readln(eps);
Sum:=0; {задаем стартовое значение – инициализируем}
xx:=1; {задаем стартовое значение – инициализируем}
repeat
xx:=xx*x; {т. к. степень у x отличается от предыдущего шага
всего на 1, то можно сделать и так}
Sum:=Sum+xx/(i+1); {добавляем новый элемент к сумме}
until abs(xx/(i+1))<eps; {повторяем цикл, пока не получим точность}
writeln(‘Sum=’, Sum); {печатаем на экране результат}
end.
Обратите внимание на переменную xx: чтобы на каждом шаге заново не возводить x в степень, мы просто запоминаем это значение с предыдущего шага и домножаем его еще раз на x (т. е., x5 = x4 * x).
Вычисление максимального элемента последовательности
Пользователь вводит 100 чисел. Найти максимальный элемент последовательности.
Первое, что может прийти в голову, – описать 100 переменных. Это неправильно.
Нам не нужно запоминать все 100 чисел. Достаточно помнить только наибольшее среди них. Последовательность действий будет примерно такой: считываем новое число, проверяем его на максимум и далее переходим к следующему числу. Следовательно, достаточно завести две переменные: в одной из них будем хранить текущее значение, в другой – максимальное. Для реализации воспользуемся циклом for.
Пример:
var
x: integer; {текущее число, которое вводит пользователь}
Max: integer; {максимальное число в последовательности}
i: integer; {счетчик для цикла}
begin
for i:=1 to 100 do
begin
writeln(‘Введите очередное число:’);
readln(x); {считываем очередное число последовательности}
if (i=1) or (x>Max) then Max:=x;
{если это первое число, или если оно больше, чем текущий
максимум, то это – максимальное число}
end;
writeln(‘Максимальное число – ’, Max); {печатаем результат}
end.
Как видно из кода, все 100 чисел хранятся поочередно в одной переменной x. Текущее число будет максимальным, если оно больше, чем текущий максимум или если оно вообще первое (единственное) в последовательности.
Основное отличие данной программы от приведенных ранее – здесь ввод данных организуется внутри цикла.
Вычисление длины последовательности элементов
Пользователь вводит последовательность чисел, заканчивающуюся нулем. Найти максимальную длину последовательности одинаковых чисел (например, в последовательности – три семерки).
Как и в предыдущем примере, ввод здесь организуется внутри цикла. Только на этот раз нам заранее неизвестно, сколько элементов будет содержать последовательность – нам лишь известно, что она заканчивается цифрой 0. Поэтому воспользуемся циклом while с условием «пока очередной элемент не равен 0».
Чтобы определить максимальную длину последовательности, нам потребуется знать не только текущее число, вводимое пользователем, но и предыдущее, а также текущую максимальную длину последовательности и длину текущей последовательности.
Пример:
var
x: integer; {текущее число, которое вводит пользователь}
xpred: integer; {предыдущее число }
MaxCount: integer; {максимальная длина последовательности}
Count: integer; {текущая длина последовательности}
begin
writeln(‘Введите первое число:’);
readln(x); {считываем первое число }
Count:=1 {инициализируем текущую длину – пока 1 элемент};
MaxCount:=1; { инициализируем максимальную длину – пока 1}
while x<>0 do {пока не ввели 0}
begin
xpred:=x; {последнее число становится предпоследним}
writeln(‘Введите очередное число:’);
readln(x); {считываем очередное число }
if x=xpred then {если последнее число равно предпоследнему}
begin
inc(count); {увеличиваем на единицу длину
текущей последовательности}
if Count>MaxCount then MaxCount:=Count;
{сравниваем длину текущей последовательности с
максимальной длиной}
end
else Count:=1; {если последнее число не совпадает с
предпоследним, то это 1-ый элемент в новой
последовательности}
end;
writeln(‘Максимальное число – ’, Max); {печатаем результат}
end.
Представленный выше исходный текст позволит найти нам решение поставленной задачи. Обратите внимание: здесь нам не потребовался счетчик.
Вопросы для самопроверки
1. С помощью какого цикла лучше всего вычислить факториал числа?
2. С помощью какого цикла лучше всего вычислить сумму по заданной формуле?
3. С помощью какого цикла лучше всего вычислить сумму ряда с заданной точностью?
4. Какой цикл лучше использовать, если известно, что пользователь вводит последовательность чисел, заканчивающуюся цифрой 0?
§10. Массивы
Как упоминалось ранее, в Паскале существуют скалярные и структурированные типы. К скалярным относятся стандартные типы (целые, вещественные, символьный, логический и адресный) и типы, определяемые пользователем (перечисляемый и интервальный).
Структурированные же типы имеют четыре разновидности: массивы, а также множества, записи и файлы.
В отличие от обычных переменных, массивы позволяют хранить сразу несколько однотипных величин. Подробнее о них будет рассказано далее.
Описание массива
Массив – это непрерывный блок данных одного типа.
Каждая отдельная величина называется компонентой массива (или элементом массива). Массивы содержат фиксированное число компонентов одного типа, так называемого типа компонент. Тип компонент может быть любым, принятым в языке Паскаль, кроме файлового.
Таким образом, массив может состоять, например, из 100 элементов типа integer, или из 25 элементов типа real, или из 5 элементов типа char и т. п.
 |
Для описания массива используется следующая конструкция (задает размер массива и тип его компонент):
Пример:
type
TVector = array [ byte ] of char;
var
MyVector: TVector;
Values: array [ 1..10 ] of real;
Индексный тип определяет число элементов массива, а также индекс первой и последней компоненты. Допустимыми индексными типами являются все порядковые типы, за исключением длинного целого (longint) и его поддиапазонов. Индексы интервального типа, для которого базовым является целый тип, могут принимать отрицательные, нулевое и положительные значения.
Пример:
type
MyArray1 = array[byte] of integer; {массив из 256 целых чисел}
MyArray2 = array[-20..17] of integer; {массив из 38 целых чисел}
Массив может быть проиндексирован всеми значениями соответствующего индексного типа. Нумерация компонент массива не обязана начинаться с 1 или с 0 – можно описывать массив, пронумерованный любыми целыми числами. Необходимо лишь, чтобы номер последней компоненты был больше первой.
Описать массив можно следующим образом:
1) в разделе описания переменных в качестве типа данных записать представленную выше конструкцию;
Пример:
var
Values: array [ 1..10 ] of real;
2) создать новый тип в разделе описания типов и использовать его при описании переменных.
Пример:
type
TVector = array [ 1..10 ] of real;
var
Values: TVector;
В обоих случаях переменная Values будет представлять из себя «контейнер», в котором можно хранить 10 вещественных чисел с индексами от 1 до 10. Однако второй способ является более предпочтительным, т. к. он позволит описать еще несколько переменных типа TVector.
Обращение к элементам массива
Массивы относятся к структурам прямого доступа. Это означает, что возможно напрямую (не перебирая предварительно все предшествующие компоненты) обратиться к любой интересующей компоненте массива.
Доступ к компонентам линейного массива осуществляется с помощью конструкции, называемой переменной с индексом:
<имя_массива> [ <индекс_компоненты> ]
Пример:
type
TVector = array [ 1..10 ] of real;
var
Values: TVector;
…
Values[1] := 10.5;
Values[2] := Values[1] + 5;
readln (Values[3]);
Values[4]:= Values[2] + Values[3];
writeln (Values[4]);
Индекс компоненты может быть константой, переменной или выражением, куда входят операции и вызовы функций. Тип индекса должен быть совместим с типом, объявленным в описании массива.
Пример:
Values[i+3-abs(x)] := 10.5;
Многомерные массивы
Массивы, у которых указан один индексный тип и типом компонент которых не является массив, являются одномерными. Иногда одномерные массивы называют векторами.
Пример: одномерный массив (вектор)
type
TVector = array [ 1..10 ] of real;
Если типом компонент также является массив, то результат можно рассматривать как массив массивов или как один многомерный массив. Другой способ описать многомерный массив – указать через запятую несколько индексных типов.
Пример: многомерные массивы
type
TArray1 = array [ 1..10 ] of real; {одномерный массив}
TArray2 = array [ -3..3 ] of TArray1;
{массив массивов – двухмерный массив}
TArray2b = array [ -3..3 ] of array [ 1..10 ] of real;
{массив массивов – двухмерный массив}
TArray3 = array [ 1..10, boolean, ‘A’..’Z’ ] of integer;
{трехмерный массив}
Частным случаем многомерных массивов является двумерный массив – матрица, таблица. В этом случае обычно первый индекс определяет номер строки, второй – номер столбца.
Массив может быть проиндексирован по каждой размерности всеми значениями соответствующего индексного типа, поэтому число элементов равно произведению числа значений в каждом индексном типе. Число размерностей не ограничено.
Пример: число элементов в массивах
type
TArray1 = array [ 1..10 ] of real; {10 элементов}
TArray2 = array [ -3..3 ] of TArray1; {7*10 = 70 элементов}
TArray2b = array [ -3..3 ] of array [ 1..10 ] of real; {7*10 = 70 элементов }
TArray3 = array [ 1..10, boolean, ‘A’..’Z’ ] of integer;
{10*2*26 = 520 элементов}
Доступ к компонентам многомерного массива также осуществляется с помощью конструкции, называемой переменной с индексом. В случае многомерного массива можно использовать несколько индексов в отдельных квадратных скобках или несколько индексов в одних скобках через запятую.
Пример: обращение к элементам многомерных массивов
type
TMatrix = array [ -3..3 ] of array [ 1..10 ] of real;
var
M: TMatrix;
…
M[1][2] := 3;
M[-2, 9] := 6;
M[i-2, i+6] := M[i][i];
Допустимые операции с массивами
В программе на языке Паскаль один массив может быть присвоен другому, если их типы идентичны.
Пример:
A:=B;
X:=Y;
В случае массивов типы переменных являются идентичными, если:
· тип описан в разделе описания типов;
Пример:
type
Cube = array[0..1,0..1,0..1] of integer;
var
A, B: Cube;
· переменные записаны в разделе var через запятую.
Пример:
var
X, Y: array[0..1,0..1,0..1] of integer;
Пример: типы переменных A и X не идентичны.
Пример: неидентичные типы:
type
MyArray1 = array[1..5] of byte;
MyArray2 = array[1..5] of byte;
Пример: неидентичные типы переменных:
var
K: array[1..5] of byte;
N: array[1..5] of byte;
Вводятся и выводятся массивы покомпонентно. Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле.
Пример: вывод вектора на экран
const
N=10;
type
TVector = array[1..N] of integer;
var
X: TVector;
i: integer;
…
for i:=1 to N do writeln(X[i]);
Массивы нельзя сравнивать (можно покомпонентно).
Инициализация массива
Инициализацию массивов можно осуществить либо программно, либо с помощью типизированных констант.
Программная инициализация обычно осуществляется с помощью циклов, т. к. обращение возможно только к отдельным компонентам массива.
Пример: заполнения массива данными
const
N=10;
M=5;
type
TMatrix = array[1..N, 1..M] of real;
var
X: TMatrix;
i, j: integer;
…
for i:=1 to N do
for j:=1 to M do writeln(X[i, j]);
При инициализации с помощью типизированных констант значения элементов заключаются в скобки и разделяются запятыми.
Пример: пример инициализации одномерного массива с помощью типизированных констант
type
TStatus = array[1..3] of string[7];
const
Status: TStatus = ('Active','Passive','Waiting');
В случае многомерных массивов значения каждой размерности заключаются в отдельные скобки и разделяются запятыми.
Пример: пример инициализации многомерного массива с помощью типизированных констант
type Cube = array[0..1,0..1,0..1] of integer;
const Maze: Cube = ( ( (0,1), (2,3) ), ( (4,5), (6,7) ) );
Вопросы для самопроверки
1. Что такое массив?
2. Как описываются массивы на языке Паскаль?
3. Что такое элемент массива? Индексный тип?
4. Какие операции допустимы над массивами?
5. Как можно на языке Паскаль описать многомерный массив?
6. Как можно просуммировать значения элементов массива?
§11. Алгоритмы сортировки
Нередко в программировании возникает задача отсортировать какие-либо величины. Иногда предварительная сортировка данных позволяет существенно сократить содержательную часть алгоритма программы. В этой ситуации могут помощь существующие алгоритмы сортировки.
В данном параграфе будут рассмотрены так называемые простые сортировки. К ним относятся методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С – некоторая константа.
Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно же, зависит не только от длины этой последовательности, но и от ее структуры. Например, если на вход подается уже упорядоченная последовательность, то количество действий будет значительно меньше, чем в случае перемешанных входных данных.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
