CASEвыражение OF 3 страница

Рассмотрим следующий пример:

var counter: Integer;

procedure DisplayCounter;

begin

writeln (counter);

end; {DisplayCounter}

procedure SetTo1;

var

counter: Integer;

begin

counter:= 1;

write (Rus('В процедуре'), ' counter=');

DisplayCounter;

end; {SetTo1}

begin

counter:= 0; SetTo1;

ReadLn;

end.

Как вы думаете, что пользователь увидит в результате работы этой программы? Сообщение будет следующим: “В процедуре counter=0”. Попробуем разобраться, почему это так. Сначала переменная counter получает значение 0. Затем происходит обращение к процедуре SetTo1, в которой объявлена локальная переменная с таким же именем counter, область ее видимости – до конца процедуры SetTo1. В процедурелокальная переменная counter получает значение 1. Выполняется вывод сообщения и далее происходит обращение к процедуре DisplayCounter, которая выведет значение глобальной переменной counter, т.е. 0, так как процедура DisplayCounter является независимой по отношению к процедуре SetTo1.

В принципе, это дает возможность передавать информацию в процедуры и функции, минуя параметры, то есть пользоваться во внутренней подпрограмме переменными, описанными во внешней процедуре, но такой стиль программирования считается ненадежным. Старайтесь, если это возможно, все переменные, используемые в процедуре, описывать в этой подпрограмме.

Для чего нужны процедуры и функции, когда и как их следует применять? Многие начинающие программисты избегают процедур и функций, утверждая, что "без них проще". На самом деле обойтись без функций и процедур легко только в самых тривиальных программах. Сколько-нибудь сложная программа, записанная "одним куском", требует при отладке от программиста огромных усилий, которые зачастую все равно пропадают даром. Обязательно используйте в своих программах процедуры и функции! Хорошая программа должна содержать главным образом обращения к процедурам и функциям. Конечно, не существует никаких жестких правил, определяющих, когда использовать функции, а когда нет, но авторы могут предложить несколько нестрогих, но полезных рецептов:

- выделяйте в процедуру (функцию) небольшой логически завершенный фрагмент алгоритма;

- не смешивайте в одной процедуре (функции) ввод-вывод данных и вычислительные алгоритмы;

- называйте свои процедуры (функции) мнемоническими именами;

- если алгоритм, который вы решили выделить в процедуру (функцию), все еще слишком сложен, оформите фрагмент этого алгоритма в другой процедуре (функции);

- если алгоритм должен вычислить одно скалярное значение, пусть это будет функция, а не процедура;

- если в вашей программе встречаются многократно вложенные циклы или "многоэтажные" условные операторы, это верный признак, что вам нужны процедуры (функции).

16. Множества

Понятие множества в Паскале очень близко к математическому определению: множество - это совокупность однотипных неиндексированных объектов. Множества описываются в виде:

SET OF тип,

где тип - базовый для этого множества тип, т.е. тип элементов множества. Базовый тип должен быть порядковым типом мощностью не более 256 (т.е. допускающий не более 256 различных значений), причем порядковые номера (вспомним функцию ORD) наименьшего и наибольшего значений должны лежать на отрезке [0,255]. Таким образом, базовым типом для множества могут быть: типы Char, Boolean, Byte и все производные от Byte интервальные типы. Размер объекта типа “множество” можно определить по формуле: размер = (мощность -1) DIV 8 + 1, т.е. множества - довольно компактные объекты, самое большое множество имеет размер 32 байта. Неименованные константы типа множество записываются в виде:

[ подмножество, подмножество,... ],

где подмножество - это либо отдельное значение, либо диапазон. Диапазон записывается как начальное значение .. конечное значение. Любое из значений может быть как константой, так и выражением соответствующего типа. Запишем, например, константу-множество, содержащую числа 0, 1, 2, 3, 4, 8, 12, 13, 14, 15, 16, 22:

[0,1,2,3,4,6,12,13,14,15,16,22]

или

[0..4,6,12..16,22]

или

[0..2,3..4,6..6,12,13..16,22]

или

[22,13..15,1..6,0,12,16]

Все эти константы полностью эквивалентны, порядок записи элементов совершенно произволен. Допускаются пустые множества, они записываются так: [ ]. Опишем несколько переменных и типизированных констант: type myset = set of 0..111;

var a: set of char;b: myset;

const c: myset = [];

d: set of char = ['a'..'z']; e: set of boolean = [false];

К множествам применимы следующие операции:

- множеству можно присвоить множество того же типа;

- операция объединение +

- операция дополнение -

- операция пересечение *

- операция эквивалентность =

- операция не эквивалентность <>

- операция включение <= и >=

Последние три операции дают значения логического типа - TRUE или FALSE. Пусть множество A = [1..20], B = [2..9,15..20], C = [3..22], тогда A+B = [1..20], A+C = [1..22], A-C = [1,2], C-A = [21,22], A*B = [1..20], A*C = [3..20], B*C = [3..9,15..20], A=B = FALSE, A<>C = FALSE, B<=A = TRUE, A>=C = FALSE.

Существует еще одна операция, связанная с множествами, - операция IN, она применяется к скалярной величине и множеству:

выражение IN множество

Здесь выражение - любое выражение базового для данного множества типа, результат операции - TRUE, если такой элемент есть в множестве, и FALSE - в противном случае.

Для множеств определены две стандартные процедуры:

Include (множество, выражение);

Exclude (множество, выражение);

Процедура Include добавляет элемент, равный значению выражения в множество, а процедура Exclude удаляет такой элемент из множества.

Теперь, когда мы знаем все возможности множеств, запишем программу, находящую все простые числа на отрезке [1,255]. Используем алгоритм под названием "решето Эратосфена": выпишем подряд все целые числа от 2 до 255. Первое простое число 2; подчеркнем его, а все числа, кратные 2, зачеркнем. Следующее из оставшихся незачеркнутых чисел 3.. Подчеркнем его как простое, а все большие числа, кратные 3, зачеркнем. Первое число из оставшихся теперь 5, так как 4 уже зачеркнуто. Подчеркнем его как простое, а все большие числа, кратные 5, зачеркнем и т.д.:

type NumSet = set of 1..255;

var

N: NumSet;

MaxDim,d,k: longint;

begin

MaxDim:=255;

d:=2;

n:=[2..255];

while d<=MaxDim do

begin

k:=2*d;

while k<=255 do

begin

Exclude(N,k);

inc(k,d);

end;

inc(d);

end;

writeln(Rus('Простые числа:'));

for k:=1 to 255 do

if k in n

then write(k:4);

readln;

end.

Рассмотрим еще один пример: ввести массив символов и подсчитать, сколько в нем латинских букв.

type Letters = set of Char;

const Lat = ['a'..'z','A'..'Z'];

var c: Char;

LSum: Word;

begin

writeln(Rus('Введите строку символов, затем нажмите Enter '));

LSum:=0;

repeat

read(c);

if c in lat

then inc(LSum)

until c=#10;

writeln(Rus(' Латинских букв '),LSum);

readln;

end.

Обратите внимание, что в этой задаче нет необходимости заранее знать, сколько символов содержится в массиве (более того, в программе никакого массива и нет!), достаточно лишь помнить, что клавиша Enter генерирует символ #10. Из-за несоответствия кодировок кириллицы в DOS и Windows в консольных приложениях подобный пример для множества из символов русских букв не сработает.

17. Тип STRING

Тип STRING - это строковый тип в Паскале. Строкой называется последовательность символов. Строковыми константами вы уже неоднократно пользовались - это последовательность любых символов, заключенная в апострофы; допускаются и пустые строки, они записываются так: '' – это не двойная кавычка, а два идущих подряд апострофа. Строковые переменные и типизированные константы описываются в виде

STRING

или

STRING [ максимальная длина ]

Если максимальная длина не задана, то по умолчанию она берется равной 255. Максимальная длина при описании строковых данных задается целочисленным константным выражением и никогда не может превышать 255. Это ограничение обусловлено самой структурой типа STRING: фактически строка - это массив ARRAY [Byte] OF Char, причем в 0-м символе закодирована текущая длина строки. Строковые переменные могут иметь любую длину от 0 до максимальной. В программе строки можно использовать и как единый структурированный объект (чуть позже мы познакомимся с разнообразными возможностями обработки строк), и как массив символов, т.е. обращаться к элементам строк следует так же, как к элементам массивов. Для строк определены следующие операции:

- строке можно присвоить строку;

- строки можно вводить процедурой READLN;

- строки можно выводить процедурой WRITE [ LN ];

- для строк определена операция конкатенации +, при этом вторая строка дописывается справа к первой и длина результата становится равной сумме длин операндов (если она не превосходит 255).

Запишем программу, выполняющую простейшие операции со строками:

type ShortString = string[80];

var s1,s2: ShortString;

s,s3: string;

begin

writeln(Rus('Введите 1-ю строку ')); readln(s1);

writeln(Rus(' Введите 2- ю строку ')); readln(s2);

writeln(Rus('Вы ввели '),s1,' & ',s2);

writeln(Rus('s1+s2='),s1+s2);

s3:=s1+s1+s1;

writeln(Rus('Строка s1,повторенная 3 раза '),s3); readln

end.

Обратите внимание, что при вводе строк всегда используется READLN, но не READ. Процедура READ в отличие от READLN считывает лишь символы до символа конца строки (клавиша Enter), который остается в буфере клавиатуры. Таким образом, пользуясь процедурой READ можно ввести только одну строку; все строки, вводимые вслед за первой, станут пустыми. Запишем теперь программу, которая вводит некоторую строку, заменяет в ней все цифры на пробелы и дописывает в конец строки символы "???":

var s: string;

l,i: byte;

begin write('введите строку '); readln(s);

l:=ord(s[0]);

for i:=1 to l do if s[i] in ['0'..'9'] then s[i]:=' ';

for i:=l+1 to l+3 do s[i]:='?';

writeln(Rus('вот что получилось: '),s); readln

end.

Наша программа заменила цифры, но никаких трех знаков вопроса не добавила. Дело в том, что, обращаясь к элементам строки, невозможно изменить текущую длину строки. Второй цикл нашей программы сработал правильно, записав символы "?" в соответствующие элементы строки, но длина строки осталась прежней, и процедура WRITELN вывела только символы с 1-го по L-й. Чтобы решить задачу корректно, мы могли бы добавить в программу один оператор INC(s[0],3); но, конечно, лучше всего просто записать: s:=s+'???';

Для обработки строк в Паскале существует несколько стандартных функций и процедур:

1. FUNCTION Length (S: String): Integer; - возвращает длину строки.

2. FUNCTION Concat (S1 [, S2,..., Sn ]: String): String; - возвращает строку, полученную сцеплением аргументов S1 [, S2,..., Sn ], может использоваться вместо операции "+".

3. FUNCTION Pos (Substr: String; S: String): Byte; - возвращает номер первого слева символа строки S, начиная с которого строка Substr входит в S, если Substr не входит в S, то значение функции равно 0.

4. FUNCTION Copy (S: String; Index: Integer; Count: Integer): String; - возвращает подстроку строки S, которая начинается с символа с номером Index и имеет длину Count.

5. PROCEDURE Delete (VAR S: String; Index: Integer; Count: Integer); - удаляет из строки S подстроку, начинающуюся с символа с номером Index и имеющую длину Count.

6. PROCEDURE Insert (Substr: String; VAR S: String; Index: Integer); -вставляет в строку S подстроку Substr начиная с символа с номером Index.

Еще две стандартные процедуры предназначены для перевода строки в число и числа в строку:

7. PROCEDURE Val (S: STRING; VAR V; VAR Code: Intege r); - преобразует строку S в число V (если это возможно); V - любая переменная арифметического типа, переменная Code возвращает 0, если преобразование прошло успешно, или номер первого неправильного символа строки.

8. PROCEDURE Str (X [: Width [: Decimals ]]; VAR S: STRING); - преобразует произвольное арифметическое выражение X в строку S, параметры Width и Decimals позволяют форматировать строку и имеют такой же смысл, как и в процедуре WRITE [ LN ].

Теперь, зная процедуру Val, вы можете организовать надежный ввод числовых данных в любой своей программе. Предположим, что программа должна вводить вещественное значение F. Мы можем записать это так:

var f: single;...

begin write('введите f '); read(f); …

Если пользователь правильно введет число, то все будет в порядке, но если он ошибочно или преднамеренно нажмет не ту клавишу (например, запятую вместо точки и т.п.), то произойдет аварийное прерывание программы. Программы, таким образом, реагирующие на неверный ввод, нельзя назвать хорошими. Хорошая программа обязана обрабатывать нажатие практически любых клавиш в любых комбинациях. Мы можем предложить следующий вариант:

var f: single;

s: string;

code: integer;...

begin repeat

write('введите f '); readln(s);

val(s,f,code);

if code=0 then break;

writeln('ошибка ввода!');

until false;

Решим часто встречающуюся задачу о распаковке текста: дана строка, содержащая текст на английском языке; нужно выделить слова, содержащиеся в этом тексте. Хотя эта задача и элементарна, ее решение не столь тривиально и требует предварительной разработки алгоритма. Сначала уясним, что такое текст. Текстом будем называть последовательность слов, разделенных любым количеством " разделителей ". Слова - это последовательности букв языка (в нашем случае - английских букв), " разделители " - любые символы, не являющиеся буквами. Итак, наш текст в общем случае имеет вид: *X*X...*X*, где X - слово, * - " разделитель ". Можно предложить следующий алгоритм распаковки:

1) удалим завершающие пробелы, после чего текст примет регулярный вид *X*X...*X*;

2) удалим лидирующие пробелы;

3) выделим первое слово и удалим его из текста.

После выполнения пунктов 2 и 3 мы получили одно слово и текст стал короче на одно слово, сохранив при этом свою структуру. Очевидно, что пункты 2 и 3 следует выполнять до тех пор, пока текст не пуст. Запишем программу, реализующую этот алгоритм.

var s: string;

i: byte;

const letters: set of char = ['a'..'z','A'..'Z'];

begin writeln(Rus('введите текст ')); readln(s);

{ удалим завершающие пробелы, здесь есть 1 ошибка! }

while not(s[length(s)] in letters) do

delete(s,length(s),1);

writeln(Rus('слова текста:'));

{ организуем цикл по словам }

while s<>'' do

begin

{ удалим лидирующие пробелы }

while not(s[1] in letters) do delete(s,1,1);

{ найдем границу первого слова, здесь есть 1 ошибка! } i:=1;

while s[i] in letters do inc(i); { i - номер первого пробела } dec(i);

writeln(copy(s,1,i)); { выведем слово }

delete(s,1,i); { удалим слово из текста }

end;

readln

end.

На первый взгляд наша программа работает правильно (мы ввели текст латиницей и получили все слова из него), но тестирование программы обязательно должно включать все предельные, или особенные, случаи. Введем, например, строку, не содержащую никаких слов, и программа сработает неправильно: она либо зациклится, либо пользователь не получит никакого сообщения - все завершится просто сворачиванием окна вывода. Это результат ошибки в первом цикле: если в тексте нет букв, все символы из него будут удалены, длина строки станет равной нулю, и в дальнейшем станет проверяться символ с номером 0, который равен #0 и, естественно, не является буквой. Еще одна ошибка подобного рода может произойти при выделении последнего слова: мы увеличиваем индекс i, пока i -й символ - буква, и, в конце концов, дойдем до конца строки. Но переменная s всегда содержит 255 символов, символы с номерами Length(s)+1, Length(s)+2 и т.д. существуют, и нет никаких гарантий, что они не являются английскими буквами. В этом случае мы можем получить последнее слово с "хвостом". Исправим нашу программу:

var s: string; i: Byte;

const Letters: set of Char = ['a'..'z','A'..'Z'];

begin

writeln(Rus('Введите текст латиницей')); readln(s);

while not(s[Length(s)] in Letters)and(s<>'') do

Delete(s,Length(s),1);

if s=''

then

begin

writeln(Rus('текст не введен'));

Halt;

end;

writeln(Rus('Слова текста:'));

while s<>'' do {цикл выделения отдельных слов}

begin

while not(s[1] in Letters) do

Delete(s,1,1);

i:=1;

while (s[i] in Letters) and (i<=Length(s)) do

inc(i);

Dec(i);

writeln(Copy(s,1,i));

Delete(s,1,i);

end;

readln;

end.

Теперь запишем то же самое, используя функции и процедуры:

var s: string;

i: byte;

const letters: set of char = ['a'..'z','A'..'Z'];

{процедура удаления завершающих пробелов}

procedure del_tail(var s:string);

begin

while not(s[length(s)] in letters)and(s<>'') do

delete(s,length(s),1);

end; {del_tail}

{процедура удаления лидирующих пробелов}

procedure del_head(var s:string);

begin

while not(s[1] in letters) do

delete(s,1,1);

end; {del_head}

{функция выделения отдельного слова}

function makeword(s:string; var bound:byte):string;

begin bound:=1;

while (s[bound] in letters)and(bound<=length(s)) do

inc(bound);

dec(bound);

makeword:=copy(s,1,i);

end; {makeword}

begin writeln(Rus('введите текст ')); readln(s);

del_tail(s);

if s='' then

begin writeln(Rus('текст не введен'));

halt;

end;

writeln(Rus('слова текста:'));

while s<>'' do { организуем цикл по словам }

begin

del_head(s);

writeln(makeword(s,i));

delete(s,1,i);{ удаление слова из текста }

end; readln

end.

18. Погрешности при вычислениях

В отличие от целочисленных выражений, которые всегда вычисляются точно, вещественные выражения дают приближенный результат, и вещественные переменные содержат приближенные значения. Например, выполним программу

var x: single;

begin x:=1/3;

writeln(x*3-1:15:10); readln

end.

Мы получим не 0 (точное значение выводимого выражения), а, например, 0.0000000298, а может быть, какое-нибудь другое маленькое число. Это обусловлено тем, что переменные типа Single хранят конечное число десятичных цифр (11-12 цифр), кроме того, эти цифры хранятся в двоичном коде, поэтому мы и не получили 1E-12 или 1E-13. Таким образом, x/a*a далеко не всегда равно x. И наоборот, a+x может быть равно a, даже если x не равно нулю. Найдем такое положительное число, которое удовлетворяет уравнению x+1=1:

const x:single;

begin x:=1;

while x+1<>1 do

x:=x/2;

writeln(x); readln

end.

Мы получим, например, 5.42E-20 (результат зависит от типа компьютера).

Решим реальную задачу, в которой используются приближенные вычисления: вычислить сумму ряда . Несмотря на то, что необходимо просуммировать бесконечное число слагаемых, эта задача легко решается за конечное время, так как общий член ряда быстро убывает и, начиная с некоторого n, прибавление очередного слагаемого уже не будет изменять сумму. Сначала напишем плохую программу:

function factorial(n:word):single;

var i:word; f:single;

begin f:=1;

for i:=1 to n do f:=f*i;

factorial:=f;

end; { factorial }

function power(x:single; n:word):single;

var i:word; f:single;

begin if n=0

then power:=1

else begin f:=x;

for i:=2 to n do f:=f*x;

power:=f;

end;

end;{ power}

var x,s1,s2: single;

i: word;

begin writeln('введите x '); readln(x);

s2:=0; i:=0;

repeat

s1:=s2;

s2:=s1+power(x,i)/factorial(i);

inc(i);

until s1=s2;

writeln('сумма ряда = ',s1); readln

end.

Запустим эту программу, задав x= 1; мы получим верный результат 2.71828... (его легко проверить, поскольку сумма нашего ряда равна exp(x)). А теперь попытаемся поочередно запускать программу для x= 10, 11, 12, 13 … И для какого-то х результат получен не будет. В данном случае это переполнение, оно происходит всякий раз, когда вещественная величина превышает максимально допустимое значение 1.7E38. Следовательно, для некоторого i мы уже не можем вычислить i!.

Означает ли это, что решить задачу невозможно? Вовсе нет; конечно, мы не можем задать нашей программе очень большое значение x, но значение 10 вполне приемлемо, дело здесь в качестве нашей программы. Действительно, посмотрим, как работает программа: для вычисляется x⁰ и 0!, затем для i=1 заново вычисляется x¹ и 1! и т.д. до получения результата; но xⁱ⁺¹=x xⁱ и (i+1)!=(i+1) i!, так что, зная предыдущие значения, достаточно выполнить всего одну операцию, чтобы получить последующие. Более того, нам вовсе не нужен факториал сам по себе, а только общий член ряда (в котором этот факториал находится в знаменателе). Нетрудно записать рекуррентную формулу для общего члена ряда: , , откуда .Кроме того, что таким образом мы избавимся от переполнения, пользуясь этой формулой, мы еще и увеличим скорость нашей программы.

var x,s1,s2,a: single;

i: word;

begin i:=0;

writeln(Rus('введите x)'); readln(x);

a:=1; s2:=0;

repeat s1:=s2;

s2:=s1+a;

inc(i);

a:=a*x/i;

until s1=s2;

writeln(Rus('сумма ряда = '),s1); readln

end.

Программа сработала для x=10 и x=20 и x=50, но для x=100 снова произошло переполнение. Но здесь уже ничего сделать нельзя, exp(100) >10⁴³ и никак не может быть представлена вещественным значением типа Single.

Решим еще одну задачу: найти корень уравнения f(x)=0 методом бисекции или половинного деления. Метод бисекции заключается в следующем: пусть уравнение имеет единственный корень на отрезке [a,b] - это значит, что график функции один раз пересекает ось абсциссна этом отрезке. Определим знак функции в точке a и в точке x=(a+b)/2. Если эти знаки одинаковы, то корень лежит на отрезке [x,b], в противном случае - на отрезке [a,x]. Таким образом, за один шаг метода мы ровно вдвое уменьшили наш отрезок; будем повторять эти операции до тех пор, пока отрезок не станет очень маленьким, и в качестве корня возьмем середину этого маленького отрезка. Попробуем реализовать этот метод:

var a, b, epsilon, x, fa, fx: single;

function f(x:single):single;

begin f:=exp(x)-2;

end; {f}

begin epsilon:=1e-10; a:=0; b:=10;

fa:=f(a);

while b-a>epsilon do

begin x:=(a+b)/2;

fx:=f(x);

if fx=0

then begin writeln(x);

halt;

end;

if fa*fx<0

then b:=x

else a:=x;

end;