Основные математические функции

Оглавление

1. Целочисленная арифметика.................................................. 8

1.1. Операции с целыми числами......................................... 9

1.1.1. Задача «Рубли и копейки».......................................... 9

1.1.2. Задача «Часы»........................................................... 10

1.1.3. Задача «Сумма цифр».............................................. 10

1.1.4. Задача «Количество цифр»...................................... 11

1.1.5. Задача «Високосный год»........................................ 11

1.1.6. Задача «Дом»............................................................ 12

1.1.7. Наибольший общий делитель (алгоритм Евклида). 13

1.1.8. Задача «Банки»......................................................... 13

2. Вещественные числа............................................................ 14

2.1. Основные математические функции........................... 15

2.2. Возведение в степень................................................... 16

3. Условный оператор............................................................. 16

3.1. Максимальное из двух чисел....................................... 16

3.2. Максимальное из трех чисел....................................... 16

4. Вычисление площадей сложных фигур.............................. 17

5. Текстовые файлы................................................................. 18

6. Одномерные массивы.......................................................... 19

6.1. Описание в программе................................................. 19

6.2. Ввод и вывод массивов................................................ 19

6.3. Популярные алгоритмы работы с массивами............. 20

6.3.1. Сумма элементов массива........................................ 20

6.3.2. Количество положительных элементов в массиве.. 21

6.3.3. Поиск максимального (минимального) элемента массива   21

6.3.4. Сортировка простым обменом (метод “пузырька”) 23

6.3.5. Быстрая сортировка.................................................. 25

6.4. Поиск данных............................................................... 27

6.4.1. Линейный поиск........................................................ 27

6.4.2. Бинарный поиск........................................................ 29

7. Символьные строки............................................................. 31

7.1. Общие сведения............................................................ 31

7.2. Стандартные функции для работы со строками:........ 32

7.3. Сравнение строк........................................................... 33

7.4. Несколько полезных приемов обработки строк......... 34

7.4.1. Убрать из строки пробелы в начале строки............ 34

7.4.2. Убрать из строки пробелы в конце строки.............. 35

7.4.3. Убрать из строки все пробелы................................. 35

7.4.4. Убрать из строки «лишние» пробелы...................... 35

7.4.5. Подсчитать количество цифр в натуральном числе. 36

7.4.6. Заменить фрагмент R в строке S на фрагмент T..... 36

7.4.7. Строка палиндром.................................................... 37

7.4.8. Выделение слов из строки........................................ 38

8. Множества............................................................................ 40

8.1. Множество символов в строке..................................... 41

8.2. Вывод элементов множества на экран......................... 41

8.3. Ввод множества символов........................................... 41

8.4. Количество различных символов в строке................. 42

9. Двухмерные массивы (матрицы)......................................... 43

9.1. Описание матрицы....................................................... 43

9.2. Ввод элементов матрицы............................................. 43

9.3. Вывод элементов матрицы........................................... 44

9.4. Основные алгоритмы работы с матрицами................ 44

9.4.1. Сумма элементов матрицы....................................... 44

9.4.2. Сумма главной диагонали квадратной матрицы..... 44

9.4.3. Сумма побочной диагонали квадратной матрицы.. 45

9.4.4. Транспонирование матриц....................................... 45

9.4.5. Транспонирование матрицы в том же массиве (транспонирование квадратной матрицы). 45

9.4.6. Умножение матриц................................................... 45

9.4.7. Работа с фрагментами матриц................................. 46

10. Динамическое программирование.................................. 47

11. Цифровая геометрия........................................................ 49

11.1. Основные отношения................................................... 49

11.2. Взамное расположение точки и прямой...................... 50

11.3. Площадь многоугольника............................................ 51

11.4. Выпуклая оболочка...................................................... 53

12. Алгоритмы на графах...................................................... 55

12.1. Алгоритм Флойда......................................................... 55

13. Задачи олимпиад.............................................................. 58

13.1. Задачи с сайта contest.samara.ru.................................. 59

13.1.1. Тортики – 1............................................................ 59

13.1.2. Высокие горы........................................................ 60

13.1.3. Задача «На болоте» (алгоритм Дейкстры).......... 62

13.1.4. Задача «На болоте» (алгоритм Флойда).............. 67

13.2. Задачи с сайта ACM.TIMUS.RU.................................. 68

13.2.1. Задача «Ниточка» (номер на сайте 1020)............ 69

13.2.2. Демократия в опасности (номер на сайте 1025).. 71

13.2.3. Один в поле воин (номер на сайте 1197)............. 73

13.2.4. Задача «Выборы» (номер на сайте 1263)............ 75

13.2.5. Белый тезис (номер на сайте 1335)...................... 76

13.2.6. Проблема Бен Бецалеля (номер на сайте 1336).. 78

13.2.7. Ферма (номер на сайте 1349)............................... 80

13.2.8. Развод семи гномов (номер на сайте 1243)......... 81

13.2.9. Освещение в Хогвартсе (номер на сайте 1448)... 82

13.2.10. Гиперпереход (номер на сайте 1296).................. 83

13.2.11. Драгоценные камни (Stone pile 1005)................... 85

14. Процедуры и функции..................................................... 87

14.1. Как написать хорошую программу............................. 87

14.2. Рекурсивные процедуры.............................................. 88

14.2.1. n- ая степень числа................................................ 88

14.2.2. Перевод десятичного числа в двоичную систему 88

14.2.3. n-ое число Фибоначчи.......................................... 88

14.2.4. Алгоритм Евклида (наибольший общий делитель) 89

Список рекомендуемой литературы.......................................... 90

 

Предисловие

Книга содержит материалы, которые предлагались студентам на занятиях в Самарском государственном аэрокосмическом университете. Предполагается, что информацию о конструкциях языка можно получить на лекциях и в книгах из списка рекомендованной литературы[1-3]. Авторы надеются, что эта книга поможет глубже понять и полюбить программирование, принять участие в соревнованиях различных уровней. Множество соревнований проводится на сайтах contest.samara.ru (Самарский государственный университет), acm.sgu.ru (Саратовский государственный университет), acm.timus.ru (Екатеринбург), www.olympiads.ru (Москва).

Интересные материалы публикует Михаил Густокашин на сайте g6prog.narod.ru, там же вы найдете ссылки и на другие сайты. На форумах вы сможете получить консультации. В соревнованиях на acm.timus.ru проводятся открытые соревнования с участием программистов со всего мира, практически чемпионаты мира.

Обычно на сайтах имеется информация о числе участников, решивших задачу. Выбирайте для начала задачи, у которых процент успешных решений выше 50. Не огорчайтесь, если успехи придут не сразу, они обязательно придут. Каждый год в Самаре проводятся личные и командные первенства студентов и школьников на сайте contest.samara.ru.

Учтите, что на соревнованиях по правилам ACM задача считается решенной только при прохождении всех тестов. Тестов может быть много, и вы можете получить, например, сообщение, что «неверный ответ на 51 тесте». Практически всегда присутствуют ограничения по времени и по памяти, а, значит, «плохая» программа тоже не будет принята, хотя она «правильная». Для школьников обычно условия приема задач более «мягкие».

Лучше языка Паскаль для начального обучения программированию пока нет. Этот язык и был создан Н.Виртом для целей обучения.

Зная программирование, легко ответить на значительную часть вопросов частей А и В и успешно выполнить часть "С", наиболее сложную часть ЕГЭ по информатике.

И, наверное, самое главное, решение задач по программированию потребует от вас дополнительных знаний в комбинаторике, теории графов, цифровой геометрии и во многих других разделах математики. Знание операторов языка, конечно, необходимо, но не это главное. Читайте нашу книгу, участвуйте в соревнованиях и скоро сами поймете, что главное в программировании.

Успехов! И до встречи на чемпионате области, а возможно и мира!

Если вы обнаружите ошибки в программах или сможете, предложите более эффективные решения, или просто захотите поделиться радостью побед, пишите нам по адресу: [e-mail].

Целочисленная арифметика

Целые числа представляются в компьютере в виде двоичного целого числа, возможно со знаком. Из всего разнообразия целых чисел выберем тип Integer (целый) и тип Longint (длинный целый). Рекомендуем именно их использовать в своих программах. Тип Integer имеет диапазон от –32768 до +32767. Тип Longint от –2147483648 до [phone]. Об остальных целых типах можно узнать из книги Фаронова[1].

Часто (особенно на различных соревнованиях) предлагаются задачи с целыми числами с очень большим числом знаков (до нескольких сотен). В этих случаях говорят о длинных числах и соответственно о длинной арифметике. Об этом можно прочитать в книге С.М.Окулова[2], в которой описаны формы представления длинных чисел, предложены алгоритмы и приведены программы длинной арифметики.

В некоторых случаях может пригодиться тип Comp [1], который дает нам 19-20 цифр в целом числе.

Операции с целыми числами

Для целых чисел определены, кроме известных любому ученику операций сложения (+), умножения (*) и деления (/), еще две очень полезные операции – это целочисленное деление (div) и остаток целочисленного деления (mod).

7 div 2=3                  6 div 2=3

7 mod 3=1                6 mod 2=0

Очевидно, что операция mod пригодится нам при проверке четности целого числа. Например,

If K mod 2 = 0 Then Write('Yes') Else Write(No');

Для преобразования вещественного числа в целое можно использовать два правила и соответственно две разные функции:

Round(X) – округляет до ближайшего целого

Trunc(X) – отбрасывает дробную часть

Обратите внимание, что операция деления «/» дает всегда вещественный результат и программа

Var L:Integer;

Begin

L:=4/2;

End.

выдаст сообщение об ошибке: «Type mismatch (несоответствие типов)».

Задача «Рубли и копейки»

Дана сумма в копейках. Получить сумму в рублях и копейках. Решите эту задачу на бумаге и полу́чите правильный алгоритм. Вы еще не забыли, что mod – остаток, а div –результат целочисленного деления?

Var s, r: Longint;

k: Integer;

Begin

Write('сумма в коп='); readln(s);

r:=s div 100;

k:=s mod 100;

Write(r,'руб. ',k,'коп ');

Readln

End.

Задача «Часы»

Дано время в секундах, получить время в часах, минутах и секундах.

var t, h: Longint;

m, s: integer;

Begin

Write('время в сек='); readln(t);

h:=t div 3600;

m:=(t mod 3600) div 60;

{(t mod 3600) сколько секунд}

{ не вошло в целые часы}

{ и div 60 - сколько в них целых минут}

s:=t mod 60;{секунды не вошли в час и мин}

Write (h,'час ', m, 'мин ', s, 'сек ');

Readln

End.

Задача «Сумма цифр»

Найти сумму цифр натурального числа.

Var x:longint;

s, k:integer;

Begin

Write('Введи целое число');

Readln(x);

s:=0;

Repeat

k:=x mod 10;{выделяем последнюю цифру}

s:=s+k;

x:=x div 10; {“убираем” последнюю цифру}

Until x=0; {больше цифр нет}

Write(s);

Readln

End.

Задача «Количество цифр»

Найти количество цифр натурального числа.

var x:longint;

k:integer;

Begin

Write('Введи целое число');

Readln(x);

k:=0;

Repeat

k:=k+1;

x:=x div 10;

Until x=0;

Write(k);

Readln

End.

Задача «Високосный год»

Очень часто нужно подсчитать, сколько дней между двумя датами за пределами одного года. Ничего особо сложного, если знаешь правила для определения високосного года. На одной из олимпиад выяснилось, что многие участники наивно считали, что достаточно выполнения условия делимости на 4. Этого условия недостаточно.

Год считается високосным (366 дней), если он не последний год столетия и делится без остатка на 4. Последний год столетия считается високосным только в том случае, если его номер делится на 400[2].

Правильная проверка будет иметь вид:

Var Y:Integer;

Begin

Readln(Y);

If (Y mod 400=0) Or ((Y mod 100<>0) And (Y mod 4=0))

Then Write ('ДА') Else Write ('НЕТ');

Readln

End.

Задача «Дом»

Перед вами многоквартирный и многоэтажный дом. Вы знаете номер квартиры K, число этажей N и количество квартир на каждом этаже M. Программа должна вычислить в каком подъезде, и на каком этаже находится нужная квартира.

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

Подъезд 1					Подъезд 2					Подъезд 3
9	10	11	12		21	22	23	24		33	34	35	36
5	6	7	8		17	18	19	20		29	30	31	32
1	2	3	4		13	14	15	16		25	26	27	28

Попробуйте решить задачу самостоятельно! В качестве тестовых примеров возьмите номер квартиры 1, затем 12, 13, 36. Измените структуру дома, и вновь протестируйте программу. Сравните свою программу с нашей, проверяя их одинаковыми тестами.

Наша программа приведена ниже. В формулах некоторые скобки не являются синтаксически необходимыми, но делают их более понятными.

Var k, m, n, np, ne: integer;

Begin

Readln(n, m, k);

np:=(k-1) div (m*n) +1;

ne:=((k-1) mod (m*n)) div m +1;

Write (np,'подъезд ', ne, 'этаж');

Readln

End.

Если Вы не сумели написать программу самостоятельно, разберитесь с формулами из нашей программы. Спустя некоторое время попробуйте решить ее повторно, но полностью самостоятельно.

1.1.7. Наибольший общий делитель (алгоритм Евклида)

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

Var a,b:integer;

Begin

Readln(a,b);

Repeat

If a>b then a:=a-b

else If b>a then b:=b-a;

until a=b;

Write(a);

Readln

End.

Задача «Банки»

Имеется N банок с целочисленными объемами V1,..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды?

Рассмотрим две банки. Пусть V₁=3, а V2=5. Можно ли помощью этих двух банок налить в сосуд 1 литр, а если можно, то как? Нальем полную банку V₁ (3 литра) и перельем ее в банку V₂ (5 литров). Затем снова нальем в V₁ 3 литра, перельем, сколько можно, в банку V₂. В банке V₁ останется ровно 1 литр. Означает ли это, такими банками можно налить в сосуд любое количество литров? Да!

А если V₁ =2 V₂=4, то один литр уже точно не нальешь, но любое число литров кратное 2 налить можно.

В первом случае НОД=1, а во втором НОД=2.

Вывод: если НОД(V₁ V₂) является делителем V, то задача решается, в противном случае нет.

НОД находите по алгоритму Евклида (см. выш 1.1.7). Распространите выводы на задачу с N банками, и напишите программу самостоятельно.

Вещественные числа

Вещественные числа представляются в компьютере в виде мантиссы и порядка. В программе вы можете использовать форму с фиксированной точкой (например, 2.56, -45.345) или с плавающей точкой (например, 3.23Е23 – это соответствует числу 3.23*10²³). Форма с плавающей точкой обычно используется для записи очень больших или очень маленьких чисел. Эти же формы используются при вводе чисел с клавиатуры или из текстовых файлов.

Хотя язык предоставляет несколько вещественных типов, в подавляющем числе задач достаточно использовать тип Real, который обеспечивает 11-12 значащих цифр и порядок от –39 до +38.

В программах использующих вещественные числа есть свои особенности. При проведении с операций с такими числами необходимо учитывать погрешность вычислений, вызванную накоплением ошибок в последних разрядах. Это приводит к тому, что вещественные числа, как правило, нельзя сравнивать обычным образом - их нужно сравнивать с какой-то заданной точностью eps. Например, для выяснения, равно ли вещественное число нулю вместо условия a=0 следует записать abs(a)<eps.

Для сравнения двух вещественных чисел в программе следует писать:

при a=b abs(a-b)<=eps

при a<>b abs(a-b)>eps

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

При выдаче вещественных результатов с заданным числом знаков в дробной части используйте следующий формат:

Write(X:0:число знаков в дробной части);

При этом проводится округление до заданного числа знаков.

Например, после выполнения программы

Var X: Real;

Begin

X:=23.347;

Write(X:0:2);

Readln

End.

на экране появится число 23.35.

Возведение в степень

Специальной операции в языке нет. Воспользуемся известным математическим отношением A^b=e^bLnA.

Или на языке программирования Exp(b*Ln(A)).

Условный оператор

Максимальное из двух чисел

Readln (a, b);

If a>b Then max:=a Else max:=b;

Write (max);

Если нужна проверка на равенство чисел, то возможен такой вариант

If a>b Then Write('max:= ', a)

Else If b>a Then ('max= ', b)

   Else Write('a=b');

Настоятельно рекомендуем в сложном условном операторе писать Else под соответствующим If. Это позволит избежать ошибок и сделает программу более «читабельной».

Максимальное из трех чисел

В этом примере в сложном логическом выражении каждое простое выражение взято в скобки, так как у операции «and» более высокий приоритет, чем у операций отношения[1]. Подумайте, какой результат будет в случае равенства чисел и как нужно изменить программу для проверки такого случая.

If (a>b) and (a>c) Then max:=a

Else {очевидно, что «а» уже можно не рассматривать}

If b>c Then max:= b

Else max:=c;

Write(max);

Текстовые файлы

Текстовые файлы хранят информацию в виде последовательности символов. Символы образуют строки произвольной длины. В конце каждой строки находятся два особых символа: #13 #10, которые отделяют строку от следующей. Текстовый файл можно создать в редакторе среды программирования или в блокноте.

Текстовые файлы описываются в программе.

Например, Var F: text;

Файловой переменной назначается конкретный физический файл с помощью оператора

Assign (файловая переменная, имя файла);

Например, Assign (F, 'Inp.txt');

Файл необходимо открыть для чтения (Reset(F)), для записи (Rewrite(F)) или для пополнения (Append(F)).

Создаваемый или пополняемый файл следует обязательно закрыть (Close(F)). Только после закрытия можно быть уверенным в том, что выходной файл окончательно сформирован. Для чтения и записи используются операторы ввода и вывода с указанием имени файла

Read (F,) Readln (F,) Write(F,) Writeln (F,).

Есть два стандартных текстовых файла: Input (для ввода) и Output (для вывода). Они стандартно назначены на клавиатуру и экран. Описывать их в программе не нужно, а нужно просто переназначить на нужные физические файлы операторами Assign.

Например, Assign (Input, 'Inp.txt') и Assign (Output, 'Out.txt').

В операторах ввода и вывода имена файлов теперь можно не указывать.

Имена файлов для ввода исходных данных и вывода результатов (здесь 'Inp.txt' и 'Out.txt') обычно приведены в условиях задачи.

Одномерные массивы

Описание в программе

Читайте внимательно условие задачи. Описывайте массив по максимально возможному размеру, указанному в условиях задач.

Фактический размер вводится в диалоге с клавиатуры или из текстового файла.

Const nmax= 100; { описываем массив с «запасом»}

{в задаче обычно указывается возможный размер}

Type vector= array[1..nmax] of Integer;

Var a: vector;

Ввод и вывод массивов

Так как массив обычно описан «с запасом», сначала вводят конкретный размер массива, а потом поэлементно сам массив.

Const nmax=100; { описываем массив с «запасом»}

Type vector=array [1..nmax] of Integer;

Var a: vector;

i, n, max: Integer;

Begin

  Write ('введите размер массива');

Readln(n); {вводим конкретный размер массива}

Write ('введите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

{можно работать с массивом}

End.

Сумма элементов массива

Очень простой алгоритм. Сумма накапливается в переменной «s», которую нужно предварительно обнулить.

Const nmax=100; { описываем массив с «запасом»}

Type vector=array[1..nmax] of Integer;

Var a: vector;

i, n: Integer;

    s: Longint; {возможно и Real}

Begin

Write ('введите размер массива');

Readln(n);

Write ('введите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

s:=0;

For i:=1 to n do s:=s+a[i];

Writeln(s);

Readln

End.

Быстрая сортировка

Метод предложен Ч. Э. Р. Хоаром в 1962 году. Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй - и - властвуй". Общая схема такова:

из массива выбирается некоторый опорный элемент P, например средний элемент, запускается процедура разделения массива, которая перемещает все числа, меньшие, либо равные P, влево от него, а все числа, большие, либо равные P – вправо. Теперь массив состоит из двух подмассивов, причем в левом числа меньшие P (или равные), в правом большие. Для обоих подмассивов, если в подмассиве более двух элементов, рекурсивно запускаем ту же процедуру. В конце получится полностью отсортированная последовательность.

 

Procedure QuickSort(m, t: Integer);

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) Div 2];

Repeat

While A[i]<x Do Inc(i);

While A[j]>x Do Dec(j);

If i<=j Then Begin

w:=A[i]; A[i]:=A[j]; A[j]:=w;

Inc(i); Dec(j);

End

Until i>j;

If m<j Then QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

Ниже написана программа, которую вы можете запустить на своем компьютере (сделайте это обязательно!)

 

Const n=10;{размер массива}

Type

list = array[1..n] of integer;

Const

a: list=(9,2,3,7,1,8,5,4,6,10);{заполняем массив числами}

Var   i: integer;

{процедура сортировки}

Procedure QuickSort (m, t: Integer);

{ m и t границы сортируемой части массива }

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) Div 2];

Repeat

While A[i]<x Do Inc(i);

While A[j]>x Do Dec(j);

If i<=j Then Begin

   w:=A[i]; A[i]:=A[j]; A[j]:=w;

Inc(i); Dec(j);

End

Until i>j;

If m<j Then QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

{Основная программа}

Begin

  QuickSort (1,n); {указываем весь массив}

for i:=1 to n do Write(a[i],' '); {вывод массива на экран}

Readln;

end.

Поиск данных

Линейный поиск

Задача: поиск в массиве элемента с заданным значением. Последовательно просматриваем элементы массива и сравниваем их значения с искомым значением X.

Например.

For i:=1 To N Do If A[i]=X Then k:=i;

Находится номер (индекс) последнего элемента равного X (последнее вхождение), при этом массив просматривается полностью.

Первое вхождение ищем обратным циклом.

For i:=N DownTo 1 Do If A[i]=X Then k:=i;

Просто, но не эффективно! Возможно, вхождение уже найдено, а цикл просмотра продолжается до конца. Изменим программу.

{первое вхождение}

i:=1;

While (i<=N) And (A[i]<>X) Do Inc(i);{i:=i+1}

If i=N+1 Then Write('X нет в А')

Else Write('номер=', i); 

Обратите внимание на заголовок цикла. Как только элемент будет найден, второе условие станет ложным и цикл завершится. При этом i будет равно или меньше N. Если нужный элемент не будет найден, то, в конце концов, станет ложным первое условие и цикл завершится при i большим N.

В программе предполагается, что если первое условие будет ложным, то второе условие не будет проверяться (уже ясно, что все сложное условие ложно). Поэтому условие (i<=N) стоит первым, в противном случае при i=N+1 возникает ошибка «нарушение границ массива» (при включенном контроле {$R+}). Вообще, при отладке (и только при отладке!) программы настоятельно рекомендуем включать такой контроль. При нарушениях границ массивов можно «испортить» значения других переменных, что сделает работу программы не предсказуемой.

Последнее вхождение будем искать аналогично.

i:=N;

While (i>0) And (A[i]<>X) Do Dec(i);{i:=i-1}

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i); 

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

{не забудьте увеличить размер массива в описании}

{первое вхождение}

i:=1; A[N+1]:=X;

While A[i]<>X Do Inc(i);

If i=N+1 Then Then Write('X нет в А')

Else Write('номер=', i); 

{последнее вхождение - первое с конца}

i:=N; A[0]:=X;

While A[i]<>X Do Dec(i);

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i); 

Очевидно, что число сравнений зависит от места нахождения искомого элемента. В среднем количество сравнений равно (N+1) Div 2, в худшем случае - элемента нет в массиве, N сравнений

Бинарный поиск

Если массив данных отсортирован, то удается сократить время поиска, используя бинарный (метод деления пополам) поиск.

Отсортированность А позволяет, по результату сравнения со средним элементом массива, исключить из рассмотрения одну из половин. Далее применяем тот же прием по отношение к выбранной половине. Очевидно, не следует начинать поиск, если X>A[n] или X<A[1].

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

 

Const nmax=100;

Type vector=array[1..nmax] of Integer; 

Var a:vector;

i, n: Integer;

X: Integer; {номер максимального элемента}

Function bin(Var A: vector; n, X: integer): integer;

{двоичный поиск X в массиве A, n – размер массива}

Var i, j, m: Integer;

     f: Boolean;

Begin

i:=1; j:=N;

{Ha первом шаге рассматривается весь массив}

f:=False; {Признак того, что X не найден}

While (i<=j) And Not f Do Begin

m:=(i+j) Div 2;

If A[m]=X Then f:=True {Элемент найден}

Else

  If A[m]<X Then i:=m+1 {*Исключаем левую часть}

  Else j:=m-1; {*Правую часть.*}

End;

if f then bin:=m else bin:=0;

End;

Begin{основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

Write(bin(a, n, X));

Readln

End.

Предложим еще одну, рекурсивную, реализацию изучаемого поиска[2]. Значением переменной t является индекс искомого элемента или ноль, если элемент не найден.

Const nmax=100;

Type vector=array[1..nmax] of Integer;

Var a: vector;

i, n, t: Integer;

     X: Integer;

Procedure bin(i, j:Integer; Var t: Integer);

{i и j – диапазон поиска, t результат }

{A и X глобальные переменные}

Var m: Integer;

Begin

If i>j Then t:=0

Else Begin

        m:=(i+j) Div 2;

        If A[m]<X Then bin(m+1, j, t)

        Else

          If A[m]>X Then bin(i, m-1, t)

          Else t:=m;

      End;

End;

Begin {основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

bin(1, n, t); {при первом обращении – весь массив}

Write(t);

Readln

End.

Символьные строки

Общие сведения

В TP существуют ограничения на длину строки (не более 255 символов). Если вы используете компиляторы Free Pascal или Delphi (именно они используются в тестирующих системах популярных сайтов), то там таких жестких ограничений нет.

Описание в программе:

Var S: String;

  R: String[10];

Принципиальным отличием первого описания от второго является то, что при первом случае описания максимальная длина строки составляет 255 символов, а во втором – 10.

Строка в памяти размещается последовательно символ за символом, нулевой байт строки содержит текущую длину строки в символьном типе.

7.2. Стандартные функции для работы со строками:

1. Функция Length (S) – возвращает текущую длину строки.

S:='дом на траве'; L:=Length(S); - L=12

2. Функция Copy (S, k, n) копирует часть S строки из n  символов, начиная k–го символа. Длина строки S не изменяется.

После выполнения операторов

S:='дом на траве'; S1:=Copy(S, 5, 8);

S1 получит значение S1='на траве'

3. Функция Pos (s1, S) – возвращает первое вхождение подстроки в строку.

После выполнения операторов

S:='гиппопотам'; p:=Pos('по', S);

p получит значение p=4. С четвертой позиции начинается первый слог 'по'.

4. Процедура Delete (S, k, n) – удаляет n символов из строки S, начиная с k-го.

После выполнения операторов

S:='на дворе трава, на траве дрова'; Delete(S, 10,16);

S изменится и будет S='на дворе дрова'

5. Процедура Insert (r, S, n) – вставляет r в S с позиции n.

После выполнения операторов

S1:='ике'; S:='на дворе дрова'; Insert(S1, 8);

S изменится и будет S='на дворике дрова'

6. Процедура Str (x[:6:2],S) – преобразует число x в строку S с указанным форматом. Пример ниже поясняет работу функции.

Var k: integer;

  x: real;

Begin

x:=37.289; Str(x:6:2, S); {результат S=' 37.29'}

k:=37; Str(x, S); {результат S='37'}

End.

7. Процедура Val (S, x, Error) – преобразует строку S в число x, если строка S не содержит недопустимых для числа символов, то Error = 0.

Var k: integer;

  x: real;

Begin

S:= '37.289'; Val (S, x, Err); { Err=0}

S:= '37.289';

Val (S, k, Err);

{Err≠0, строка содержит «точку», а k целое}

S:= '37'; Val(S, k, Err); { Err=0}

End.

Сравнение строк

Символы упорядочены по своим кодам так, что 'a' < 'z', 'A' < 'Z', ‘А’ < ‘Я’, ‘а’<’я’. Операции сравнения символов =,<>,<,>,<=,>= - действуют в соответствии со значениями кодов.

Сравнение строк – «лексикографическое», строки сортируются по алфавиту также как фамилии в вашем школьном журнале.

Пример. В исходном файле список учеников. Упорядочить список и записать в другой файл в виде пронумерованного списка. Не используем стандартные файлы ввода и вывода, поэтому в программе появилось описание текстовых файлов.

 

Const n=100; { максимальное число строк в списке}

Var a: array [1..n] of string[20];

     Fi, Fo: text;

   i, k, j: integer;

          R: string[20];

Begin

{файл Sp.txt должен быть заранее создан}

Assign (Fi, 'Sp.txt'); Reset (Fi);

Assign (Fo, 'NewSp.txt'); Rewrite (Fo);

i:=0; {число строк}

While not Eof(Fi) do Begin {читаем до конца файла}

Inc (i);

Readln(Fi,a[i]);

End;

{получили массив из i строк}

{сортируем массив}

For k:= 1 to (i-1) do

For j:= 1 to (i-k) do

If a[j]>a[j+1] then Begin

   R:=a[j];

   a[j]:= a[j+1];

   a[j+1]:= R;

end;

{пишем строки в файл, пронумеровывая}

For k:=1 to i do Writeln(Fo, k, '. ', a[k]);

Close(Fo); {обязательно закрываем файл}

End.

Исходный файл sp.txt	Файл результатов Newsp.txt
Яковлев В.В Абрамов П.П. Петров Н.Н. Сидоров С.С. Михалов М.М.	1. Абрамов П.П. 2. Михалов М.М. 3. Петров Н.Н. 4. Сидоров С.С. 5. Яковлев В.В

Строка палиндром

Строка, которая читается одинаково в обоих направлениях, называется строкой палиндромом (строка «перевертыш»).

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

В качестве тестовых примеров введите строки с четным и нечетным числом букв.

Var s: String;

Function palindro (s: String): Boolean;

{алгоритм реализован в виде функции}

Var n, i: Byte;

Begin

i:=1;

n:=length (s);

While (i<=n div 2) and(s[i]=s[n-i+1]) Do inc(i);

If i>n div 2 Then palindro:=true Else palindro:=false;

End;

Begin{основная программа}

Readln(s);

If palindro(s) Then write('yes') Else write('no');

Readln

End.

Выделение слов из строки

Под словами будем понимать последовательности символов разделенных пробелами (кроме, соответственно, первого и последнего слов).

Пусть s='мама мыла раму'. Признаком конца слова можно считать пробел, кроме последнего слова. Чтобы не обрабатывать последнее слово специальным образом, добавим в конец строки оператором S:=s+' ' символ «пробел».

Просмотрим все элементы строки и если символ не пробел, то добавляем его к строке t. Если пробел, то в t уже целое слово. Выдаем его на экран, и начинаем формировать в t новое слово. Перед формированием «очищаем» слово t (t:=''- пустая строка).

 

Var s, r, t: string;

         i: integer;

Begin

Readln(s);

s:=s+' '; t:=''; {t пустая строка}

For i:=1 to length(s) do

If s[i]<>' ' then t:=t+s[i]

else Begin

        Writeln(t);

         t:='';

     End;

readln

End.

Используем эту идею для решения более сложной задачи: найти в строке самое длинное слово – палиндром. Для этого формируем как прямое слово t:=t+s[i], так и обратное r:=s[i]+r. Кроме того, последовательно проверяем длины слов и ищем самое длинное.

Var s, r, t, wmax: string;

        i, lmax, l: integer;

Begin

Readln(s); s:=s+' ';

r:='';{"обратное" слово-пустая строка}

t:='';{"прямое" слово-пустая строка }

wmax:='';{искомое слово – пустая строка}

For i:=1 to length(s) do

If s[i]<>' ' then {символ не равен пробелу}

  Begin

       r:=s[i] + r; t:=t + s[i]

  End

else Begin

      If r = t then

        If length(r)>length (wmax)

        then wmax:=r;

      r:=''; t:=''; {готовимся формировать новые слова}

      End;

Write(wmax);

Readln

End.

Теперь представим, что «очень много» символов последовательно записано в текстовом файле (на олимпиадах обычно бывает именно так). Тогда последним символом окажется код #26 (признак конца файла). Но, если при создании файла в конце строки будет нажата клавиша «Enter», то в конце файла могут появиться и символы #13 (CR) или (и) #10 (LF). Не забудьте об этом при участии в соревнованиях, именно из этого символа команда СГАУ на четвертьфинале чемпионата мира сдала программу только с третьей попытки, заработав 40 минут штрафного времени. Обязательно закрывайте выходной файл, иначе результат в нем может не появиться.

Используем стандартные файлы ввода и вывода. Тогда их можно не описывать и не указывать их имена в операторах ввода и вывода

Будем считывать символы из файла последовательно и по алгоритму, изложенному выше, решим задачу.

Var r, t, wmax: string;

                  ch: char;

Begin

Assign (input, 'input.txt'); Reset(input);

Assign (output, 'output.txt'); Rewrite(output);

r:=''; t:=''; wmax:='';

Repeat

Read (ch);

If (ch<>' ')and(ch<>#26)and(ch<>#10)and(ch<>#13) then

  Begin r:=ch+r; t:=t+ch End

else Begin

      If r=t then

        If length (r)>length (wmax) then wmax:=r;

       r:=''; t:='';

      End;

Until (ch=#26) or (ch=#10) or (ch=#13);

Write (wmax);

Close (output);

End.

Множества

Предлагаем изучить множества самостоятельно по [1, 2]. При изучении обратите внимание на типы данных в множествах и организации ввода и вывода множеств. Дадим лишь краткие пояснения и рекомендации. Практика программирования показывает, что наиболее полезным видом множеств является множество символов.

Появляется новая для вас операция In (проверка принадлежности элемента множеству), операции объединения множеств (+), пересечения множеств (*) и вычитания (-).

Все остальные пояснения в примерах.

Множество символов в строке

Множество символов, принадлежащих строке легко получить по следующей программе:

Var M:set of char;

S:string;

i: integer;

Begin

S:='мама мыла раму';

For i:=1 to Length(S) do M:=M+[s[i]];

{просто символ нельзя добавит к множеству М}

{нужно построить из него множество []}

{и объединить его с множеством М}

End.

Ввод множества символов

Множество можно задать в разделе констант.

Например, так

Const M: set of char = ['A'..'Z'];

R: set of char = ['0'..'9'];

Можно получить в результате присваивания, описав в разделе переменных (Var M:set of char;) и присвоив в программе

              M:= ['0'..'9', '+', '-'];

При вводе с клавиатуры или из текстового файла, заданное множество лучше вводить в виде строки, из символов которой потом легко получить множество или каждый символ сразу добавлять к множеству.

Описание матрицы.

Const n=4; m=5;

Type matrix=array[1..n, 1..n] of Real;

{или другой тип}

Var A:matrix;

На рис.2. показан вид описанной матрицы. Обратите внимание, что первый индекс – номер строки, второй - -номер столбца.

 

A11	A12	A13	A14	A15
A21	A22	A23	A24	A25
A31	A32	A33	A34	A35
A41	A42	A43	A44	A45

                      Рис. 2. Вид матрицы.

Ввод элементов матрицы.

Элементы вводятся последовательно по строкам, i – номер строки, j – номер столбца.

For i:=1 to n do

For j:=1 to m do Read(A[i, j]);