Посібник "Основи спортивного програмування. FPC"

 

 

 

 

 

 

 

 

 

 

 

Є.В. Шибецький

 

 

 

 

 

 

 

 

Основи спортивного програмування. FPC

 

 

 

 

посібник

для учнів

загальноосвітніх навчальних закладів

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

• латинські символи (великі та малі);
• символи кирилиці (великі та малі);
• цифри від 0 до 9;
• математичні символи (+,-,*,/,=,<, >);
• розділові знаки (кома, крапка, двокрапка, крапка з комою, пропуск, лапки, квадратні, круглі, фігурні дужки) та ін.

and — і

begin — початок

do — виконати

file — файл

goto — перейти до

label — позначка

or— або

repeat — повторювати

case — вибір

downto — униз до

mod — остача

procedure — процедура

for — для

array — масив

const — сталі

else — інакше

then— то

not — не

program — програма

function — функція

if — якщо

div — ділення без остачі

end — кінець

of — з

record — запис

while — доки.

• ім'я може складатися лише з латинських літер, цифр і символа «_» (риска знизу);
• ім'я не може бути службовим словом;
• цифра не може бути першим символом в імені;
• літери можуть бути малими або великими;
• бажано, щоб імена були короткими (до 60 символів) і відповідали суті об'єкта;
• пропуски в іменах не допускаються;
• два різні об'єкти не можна позначати одним іменем.

• назви стандартних типів даних: integer (цілий), real (дійсний), boolean (логічний), char (символьний), text (текстовий файл) тощо;
• назви стандартних сталих: false (хибність), true (істинність), maxint (максимальне ціле число), рі (число π ) тощо;
• назви стандартних функцій: abs(x) - модуль числа х, arctan(x), cos(x), exp(x), ln(x), sin(x), sqr(x) – піднесення числа х до квадрату, sqrt(x) - квадратний корінь з х (інші функції розглядатимемо далі);
• назви команд для введення і виведення даних: read, readln, write, writeln тощо.

program First;

var a: integer;

begin

a:=12;

writeln (‘Хочу мати з програмування ', a)

end.

program Назва програми;

Розділи описів та оголошень

begin

Розділ команд

end.

program Zadachal;

var a, b, s, r, d : integer;

begin

a := 24;

b:= 5;

s := a + b;

r :=a-b;

d := a * b;

writeln (s, r, d)

end.

 

 

АРИФМЕТИКА МОВИ PASCAL

 

Типи даних. Поняття типу даних є одним з основних у мові Паскаль. Тип даних характеризує множину допустимих значень сталих та змінних величин та сукупність операцій над ними. Ми будемо розглядати наступні типи даних: цілі числа, дійсні числа, логічний тип, рядок, масив. Встановлення, до якого типу належить величина, відбувається на етапі моделювання задачі. У програмі у розділі описів та оголошень після службового слова var потрібно обов’язково вказувати, до якого типу належить величина.

Цілі числа. У мові Паскаль виділяють такі типи для цілих чисел:

№	Службове слово	Діапазон	Пам’ять
1	shortint	-128..127	1 байт
2	integer	-32767..32768	2 байти
3	longint	-2147483648..2147483647	4 байти
4	byte	0..255	1 байт
5	word	0..65535	2 байти

Для цілих чисел визначені операції: порівняння(<,>,<>), додавання(+), віднімання(-), множення(*), отримання частки від ділення(div) та остачі(mod). Результатом виконання даних операцій є знову ціле число.

Дійсні числа. Для дійсних чисел визначені такі типи:

№	Службове слово	Діапазон	Пам’ять
1	Real	2.9E-39..1.7E+38	6 байт
2	Single	1.5E-45..3.4E+38	4 байти
3	Double	5.0E-324..1.7E+308	8 байт
4	Extended	3.4E-4932..1.1E+4932	10 байт
5	Comp	-9.2E-18..9.2E+18	8 байт

Над дійсними числами визначені такі операції: додавання, віднімання, множення, ділення(/) та порівняння.

Дійсні числа зберігаються не точно. Кожен з дійсних типів забезпечує правильне зберігання тільки певної кількості значущих цифр, їх називають правильними цифрами. З математичної точки зору, із-за особливостей внутрішньої побудови мова йде про відносну похибку. З цієї причини варто уникати точне порівняння дійсних чисел.

Прийнято вважати, що два дійсні числа a і b рівні(a=b), якщо abs(a-b)<eps. Число eps можна визначити наступним чином: min(abs(a),abs(b))*10^(-m), де m - необхідна кількість розрядів, що співпадають.

Арифметичні вирази. Арифметичні вирази будуються з імен змінних, сталих, знаків операцій,  круглих дужок та позначень функцій. Стандартними для мови Паскаль є такі функції:

№	Позначення	Дія
1	SQR(X)	Х в квадраті
2	ABS(X)	Абсолютне значення Х (модуль)
3	SIN(X)	Синус Х (аргумент в радіанах)
4	COS(X)	Косинус Х
5	EXP(X)	е в степені Х
6	LN(X)	Натуральний логарифм Х
7	LOG(X)	Десятковий логарифм Х
8	SQRT(X)	Корінь квадратний з Х
9	ARCTAN(X)	Арктангенс Х
10	TRUNC(X)	Ціла частина Х
11	ROUND(X)	Округлення Х до найближчого цілого

 

 

 

 

ВВЕДЕННЯ ТА ВИВЕДЕННЯ ДАНИХ

 

Введення даних з клавіатури виконується оператором read або readln. Наприклад, read(a) – команда введення з клавіатури значення змінної а.

 Для виведення даних на екран використовують оператор writeln. Наприклад, writeln(a) – надрукує на екрані значення змінної а.

Для зручностей введення та виведення даних у мові Паскаль часто використовують текстові файли, в яких можуть зберігатися дані. В такому файлі можуть міститися дані для роботи програми або результати її роботи. Робота з файлом складається з трьох етапів:

1. відкриття файлу;
2. читання або запис даних;
3. закриття файлу.

В програмі текстовий файл має бути представлений файловою змінною типу TEXT. У розділі описів та оголошень файлова змінна описується так:

var назва: TEXT

Ім’я файлу пов’язують з файловою змінною зо допомогою оператора:

assign(файлова змінна, ім’я файла)

В програмі більше ім’я цього файлу не з’явиться, скрізь його замінить файлова змінна.

Відкрити текстовий файл можна в залежності від мети:

• для читання – reset(файлова змінна);
• для запису – rewrite(файлова змінна);
• для доповнення – append(файлова змінна).

Закрити файл можна оператором close(файлова змінна).

Читання та запис даних у текстовий файл виконується вже знайомими операторами read та writeln, у списку яких першою має бути зазначена файлова змінна.

При здачі програм на сайт e-olimp.com.ua використовуються такі назви файлів:

• файл з вхідними даними: input.txt
• файл-результат: output.txt

Приклад. Задача про обмін змінних значеннями. Зчитати з файлу input.txt значення змінних a i b. Обміняти їх значеннями. Результат записати у файл output.txt.

program change;

var a,b:integer;

f:text;

begin

assign(f,’input.txt’);

reset(f);

readln(f,a,b);

close(f);

a:=a+b;

b:=a-b;

a:=a-b;

assign(f,’output.txt’);

rewrite(f);

writeln(f,a,’ ‘,b);

close(f)

end.

 

 

ЛОГІКА МОВИ PASCAL

 

Умовний оператор. Умовний оператор дозволяє виконувати або пропускати оператори програми в залежності від деякої умови. Схема оператора така:

if умова then оператор_1 else оператор_2

Якщо умова виконується (правильна), то виконується оператор_1, інакше – оператор_2. Коли замість оператора_1 або оператора_2 потрібно виконати декілька операторів, то їх беруть у операторні дужки

begin оператори end

Такий блок операторів називають складеним оператором.

Для побудови умови використовують порівняння: =, <>, <=, >=, <, >. Зліва та справа від знака порівняння записують арифметичні вирази.

Умовний оператор можна використовувати у скороченому вигляді:

if умова then оператор

Приклад. Розв’язати квадратне рівняння. Ввести з файлу input.txt значення коефіцієнтів, у файл output.txt вивести значення коренів рівняння з точністю 4 десяткові знаки або повідомлення про їх відсутність.

program square;

var a,b,c,d,x1,x2:real;

       f:text;

begin

assign(f,’input.txt’);

reset(f);

readln(f,a,b,c);

close(f);

assign(f,’output.txt’);

rewrite(f);

d:=b*b-4*a*c;

if d>=0 then

begin

d:=sqrt(d);

x1:=(-b-d)/2/a;

x2:=(-b+d)/2/a;

writeln(f,x1:1:4,x2:1:4)

end

else writeln(f,’Рівняння коренів не має’);

close(f)

end.

Складні умови створюють з простих за допомогою логічних операцій and(і), or(або), not(заперечення). Істиність складної умови можна з’ясувати за допомогою таблиці:

false and false=false	false or false=false
false and true=false	false or true = true
true and false=false	true or false= true
true and true = true	true or true = true
not false= true	not true=false

Логічні змінні повинні бути описані у розділі описів конструкцією:

VAR змінна: BOOLEAN

Над логічними змінними можна виконувати логічні операції and(і), or(або), not(заперечення), присвоювати, виводити їх на екран або файл, але не можна вводити.

Приклад. Ввести ціле число. Вивести відповідний йому символ ASCII-таблиці або повідомити, що такого символа немає (0-31 – коди управління, потім до 256 – друковані символи).

program symbols;

var i:word;

    q:boolean;

begin

    readln(i);

    q:=(i>31) and (i<256);

    if q then

        writeln('CHR(',i,')=',chr(i))

    else

        writeln('symbol is not exist');

end.

Якщо в програмі потрібно реалізувати розгалуження на більше, ніж дві вітки, доцільно використовувати оператор множинного вибору, який має таку структуру:

CASE змінна OF

значення_1: оператор_1;

значення_2: оператор_2;

значення_3: оператор_4;

……………………………….

значення_N: оператор_N;

ELSE оператор;

END;

Вітки ELSE, як і в умовному операторі, може не бути.

Приклад. Ввести ціле число. Якщо число менше або рівне 100, вивести повідомлення про його парність, якщо ні – про те, що воно більше 100.

program numbers;

var i:integer;

begin

    readln(i);

    if i<=100 then i:=i mod 2;

    case i of

        0:writeln('Число парне');

        1:writeln('Число не парне');

        else writeln('Число більше 100');

    end

end.

 

 

ЦИКЛИ

 

Цикл – повторювана послідовність операторів. Для їх організації у Паскалі використовують три структури:

• з параметром,
• з передумовою,
• з постумовою.

Схема оператора з параметром така:

FOR змінна:=поч_значення TO кін_значення DO оператор

На першому кроці змінна приймає початкове значення і виконується оператор. Потім значення змінної збільшується на одиницю і знову виконується оператор, після чого значення змінної знову збільшується на одиницю і т.д. Виконання циклу закінчується тоді, коли змінна набуває кінцевого значення (після цього оператор виконується останній раз).

Приклад. Задача Фібоначчі. Природа кроликів така, що пара кроликів дає перший приплід (нову пару кроликів) на третій місяць, а потім – щомісяця одну пару. Скільки пар кроликів буде через N місяців, якщо спочатку була одна пара кроликів?

program fibo;

var a,b,c,i,n:integer;

begin

    readln(n);

    a:=1;

    b:=1;

    if n>2 then begin

        for i:=3 to n do begin

                c:=a+b;

                a:=b;

                b:=c

                end;

        writeln(b)

        end

        else writeln(1)

end.

Якщо значення змінної в циклі потрібно зменшувати, а не збільшувати, то оператор циклу з параметром записують у вигляді

FOR змінна:=поч_значення DOWNTO кін_значення DO оператор,

де кінцеве значення менше за початкове.

Якщо кількості повторень в циклі наперед не відомо, то використовують цикл з передумовою або цикл з постумовою. Цикл з передумовою має таку структуру:

WHILE умова DO оператор

Даний цикл організовує виконання оператора до тих пір, поки умова є істинною. Оскільки істинність умови перевіряється на початку кожної ітерації, то тіло циклу (оператор) може і не виконатись жодного разу (при якій умові?)

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

program sum_while;

var a,b,s:integer;

begin

    readln(a,b);

    s:=0;

    while a<=b do

        begin

        s:=s+a;

        a:=a+1

        end;

    writeln(s);

end.

Цикл з постумовою має структуру

REPEAT оператори UNTIL умова

Даний цикл повторює оператори до тих пір, поки не стане істинною умова. Тіло циклу (оператори) виконується хоча б один раз.

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

program sum_until;

var a,b,s:integer;

begin

    readln(a,b);

    s:=0;

    repeat

        s:=s+a;

        a:=a+1

    until a>b;

    writeln(s);

end.

Оператор, що повторюється в циклі, сам може бути циклом. Така структура називається вкладеними циклами.

Приклад. Вивести на екран невід’ємні цілі числа, менші за 100.

program number_100;

var i,j:integer;

begin

    i:=0;

    while i<10 do

        begin

        j:=0;

        while j<10 do

                begin

                write(i*10+j:4);

                j:=j+1

                end;

        writeln;

        i:=i+1

        end;

    readln

end.

 

 

МАСИВИ

 

Масив – це впорядкована структура однотипних даних, які зберігаються послідовно. Доступ до елемента масиву здійснюється через його індекс. Масив оголошується у розділі описів за допомогою структури:

var назва:ARRAY[діапазон_індексів] OF тип_елементів

Елементами масивів можуть бути дані будь-якого типу крім файла.

Масиви поділяються на одновимірні (кожен елемент має один індекс) та двовимірні(кожен елемент має два або більше індексів). Над елементами масиву визначені всі операції, які можливі над даними відповідного типу. Наприклад, якщо елементами масиву є дійсні числа, то над ними можна виконувати всі операції, визначені для дійсних чисел.

Приклад. Ввести одновимірний масив з елементів. Вивести його найбільший елемент.

program max_of_array;

var i,n,max:integer;

          a:array[1..100] of integer;

begin

    readln(n);

    for i:=1 to n do

        readln(a[i]);

    max:=a[1];

    for i:=2 to n do

        if a[i]>max then max:=a[i];

    writeln(max)

end.

У багатьох випадках з одновимірним масивом легше працювати, якщо його елементи розміщені у порядку зростання (спадання). Такий масив називається впорядкованим, а процес розміщення елементів масиву у порядку зростання (спадання) називається упорядкуванням або сортуванням.

Є багато алгоритмів, за допомогою яких можна упорядкувати масив:

• сортування вибором (ідея метода полягає в тому, що знаходиться максимальний елемент і обмінюється місцями з останнім, потім шукається максимальний елемент без вираховування останнього і ставиться на передостаннє місце і т.д.)
• упорядкування обміном, «метод бульбашки» (послідовно порівнюються пари сусідніх елементів масива, якщо вони стоять не в потрібному порядку, то виконується їх перестановка; в результаті елемент вспливає, як бульбашка; дія повторюється до повного впорядкування)
• шейкерне сортування (модифікація методу бульбашки, при якому масив впорядковується одночасно в двох напрямках)
• сортування Хоара (значення центрального елемента масиву порівнюється з елементами справа і зліва, у випадку невпорядкованості виконується обмін місцями).

program booble;

var i,j,n:integer;

        a:array[1..100] of integer;

begin

    readln(n);

    for i:=1 to n do

        readln(a[i]);

    for i:=1 to n-1 do

        for j:=i+1 to n do

                if a[i]>a[j] then

                        begin

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

                        a[j]:=a[i]-a[j];

                        a[i]:=a[i]-a[j]

                        end;

    for i:=1 to n do

        writeln(a[i]);

end.

5

0  3  5  2  7

3  0  3  7  5

5  3  0  10  4

2  7  10  0  4

7  5  4  4  0

program prime_crascal;

var d: array[1..50,1..50] of real;

 f: text;

 x, y: array[1..50] of real;

 col: array[1..50] of integer;

 res: array[1..50,1..2] of integer;

 dmin, l: real;

 n, k, m, i, j, i1,j1:integer;

begin

 assign(f, 'data.in');

 reset(f);

 readln(fn);

 for i:=l to n do

  for j:=l to n do

   read(f, d[i,j]);

 close(f);

 for i:=l to n do

  col[i]:=i;

 k:=0;

 l:=0;

 while k<n-l do

  begin

   dmin:=maxint;

   for i1:=l to n-1 do

    for j1:=i1+1 to n do

     if (d[i1, j1]<dmin) and (col[i1]ocol[j1]) then

      begin

       dmin:=d[i1,jl];

       i:=i1;

      end;

   k:=k+1;

   l:=l+dmin;

   res[k,1]:=i;

   res[k,2]:=j;

   j1:=col[j];

   for m:=l to n do

    if col[m]=j1 then col[m]:=col[i];

  end;

 assign(f, 'data.out');

 rewrite(f);

 writeln(f,l:4:2);

 for i:=l to n-1 do

  writeln(f,res[i,1],res[i,2]:5);

 close(f)

end.

12.00

1 4

1 2

2 3

3 5

 

 

 

АЛГОРИТМ ФЛОЙДА-УОРШЕЛА

 

WARSHELL.DAT

5

0  3  5  2  1

3  0  3  7  5

5  3  0  10  4

2  7  10  0  4

1  5  4  4  0

5  2

 

FLOYD.PAS

program floyd_warshell;

var f:text;

      d:array[1..50,1..50] of real;

      n, k, і, j, n,1, n2 : integer;

begin

assign(f, ‘warshell.dat’);

reset(f);

readln(f,n);

for i:=l to n do

for j:=l to n do

read(f,d[i,j]);

readln(f,nl,n2);

close(f);

for k:=l to n do

for i:=l to n do

for j:=l to n do

if d[i,j]>d[i,k]+d[k,j] then d[i,j]:=d[i,k]+d[k,j];

assign(f, ‘warshell.sol’);

rewrite(f);

writeln(f,d[nl,n2]:7:4);

close(f)

end.

 

WARSHELL.SOL

4.0000

 

 

РЯДКИ

• concat(s1,s2,…,sn) – сполучити рядки s1,s2,…,sn в один рядок;
• copy(s,index,count) – скопіювати з рядка s підрядок довжиною count символів, починаючи з позиції index;
• length(s) – довжина рядка s;
• pos(substr,s) – номер символа, з якого перший раз у рядку s зустрічається підрядок substr.

program str_length;

var a:string;

begin

 readln(a);

 writeln(length(a))

end.

• delete(s,index,count) – видалити з рядка s count символів, починаючи з позиції index;
• insert(source,s,index) – вставити підрядок source в рядок s, починаючи з позиції index;
• str(x,s) – перетворює число х в рядок s;
• val(s,v,code) – перетворює рядок s в значення числової змінної v; у випадку успішного перетворення code=0.

 

ПІДПРОГРАМИ

 

PROCEDURE назва (список параметрів)

var опис змінних та їх типів

begin

оператори

end;

Приклад. Ввести одновимірний масив з елементів. Вивести його найбільший елемент. Використовувати підпрограму-процедуру.

program max_of_array_proc;

var i,n,max:integer;

          a:array[1..100] of integer;

procedure maximum;

begin

    max:=a[1];

    for i:=2 to n do

        if a[i]>max then max:=a[i];

end;

begin

    readln(n);

    for i:=1 to n do

        readln(a[i]);

    maximum;

    writeln(max);

    readln

end.

FUNCTION назва (список параметрів):тип результату;

var опис змінних та їх типів

begin

оператори

end;

Приклад. Ввести одновимірний масив з елементів. Вивести його найбільший елемент. Використовувати підпрограму-функцію.

program max_of_array_fun;

var i,n,m:integer;

        a:array[1..100] of integer;

function maximum:integer;

begin

    maximum:=a[1];

    for i:=2 to n do

        if a[i]>maximum then maximum:=a[i];

end;

begin

    readln(n);

    for i:=1 to n do

        readln(a[i]);

    m:=maximum;

    writeln(m);

    readln

end.

РЕКУРСІЯ

program fib;

var n:integer;

function F(k:integer):integer;

begin

if k<3 then F:=1 else F:=F(k-2)+F(k-1)

end;

begin

 readln(n);

 writeln(F(n))

end.

 

 

 

program sorting;

var f :text;

a: array[1..255] of integer;

n, i, j : integer;

begin

assign(f,'input.dat');

reset(f);

readln (f,n);

for i:=1 to n do read(f,a[i]);

close(f);

end;

procedure output;

begin

assign(f,'output.dat');

rewrite(f);

write(f,'Sorting:');

for i:=1 to n do write(f,a[i],'');

close(f);

end;

procedure swap(left,right::integer);

var temp:integer;

begin

temp:=a[left];

a[left]:=a[right];

a[right]:=temp

end;

procedure Hoare(i, r : integer);

var left, right, x : integer;

begin

x:=a[(l+r) div 2];

left:=l;

 while a[left]<x do inc(left);

 while a[right]>x do dec(right);

 if left<=right then begin    

swap(left, right);

  inc(left);

  dec(right);

 end;

 until left>right;

 Hoare(l,right);

 Hoare(left,r)

 end

end;

begin

 input;

 Hoare(1,n);

 output

end.

 

 

 

 

 

 

 

 

 

ЗМІСТ

 

 

 

 

ОСНОВНІ ПОНЯТТЯ МОВИ PASCAL     3

 

АРИФМЕТИКА МОВИ PASCAL      6

 

ВВЕДЕННЯ ТА ВИВЕДЕННЯ ДАНИХ     8

 

ЛОГІКА МОВИ PASCAL        9

 

ЦИКЛИ            11

 

МАСИВИ           13

 

ЕЛЕМЕНТИ ТЕОРІЇ ГРАФІВ

АЛГОРИТМ ПРИМА-КРАСКАЛА      15

 

АЛГОРИТМ ФЛОЙДА-УОРШЕЛА      17

 

РЯДКИ            18

 

ПІДПРОГРАМИ          19

 

РЕКУРСІЯ           20

 

СОРТУВАННЯ МЕТОДОМ ХОАРА      21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Гарнітура Arial, Arial Narrow, Book Antiqua