Програма записується в окремому exe-файлі. Таким чином, програма це алгоритм, який призначається для виконання комп'ютером. Двійкове подання команд комп'ютера називається
| Вид материала | Урок |
- Комплекс програм, які використовуються для роботи з комп'ютером, називається програмним, 156.82kb.
- Програма курсу «Сходинки до інформатики» 2 клас, 66.29kb.
- Програма, яка призначена для відображення вмісту web-сторінок називається а сервер, 18.35kb.
- 5 операційні системи, 496.26kb.
- Програма курсу за вибором "основи комп’ютерної безпеки " для основної школи, 119.72kb.
- 1. Назва модуля, 79.93kb.
- 1. Назва модуля, 92.33kb.
- Робоча навчальна програма предмет Комп’ютери у фізичних дослідженнях, 98.31kb.
- Тема уроку, 27kb.
- Текст програми це набір інструкцій (команд), які можуть бути виконані комп'ютером., 221.57kb.
Підпрограми. Функції
Функція в мові програмування Паскаль зав* жди оформлюється стандартно і має такий вигляд:
function <ім'я функції>(<списокпарамварів>г «тип результату>; ... <розділ описів>
Begin
... <серія операторів>
End;
У перекладі з англійської function означає «функція». Після слова end, яке завершує функцію, ставиться крапка з комою.
За принципами роботи зі змінними та пара* метрами функції повністю ідентичні процедурам (див. вище).
Функція як результат повертає одне значення простого типу даних, в тілі функції обов'язково має міститись оператор присвоєння:
<ім'я функції> := <вираз>;
Значення, яке здобувається в результаті обчислення виразу, повертається як результат роботи функції в головну програму,
У головній програш функції використовуються всередині виразів, так само як інші величини.
Приклад використання функції:
Знайти периметр трикутника•,. який заданий координатами своїх вершин.
Для визначення периметра трикутника можна використати функцію знаходження довжина
відрізка.
Program triangle;
var Xl,yl,x2,y2,x3,y3:real;
function dist(xxl,yyl ,xx2 ,yy2: real): real; begin
dist:=sqrt(sqr(xx2-xxl)+sqr(yy2-yyl)); end; .
Begin ' write СВведіть координати першої вершини:');
readln(xl,yl);
writeCBBeniTb координати другої вершини:'); readln(x2,y2);
тагіЬеСВведіть координати третьої вершини:'); readln(x3,y3);
writelnCnepHMerp трикутника дорівнює',
dist(xl,yl,x2,y2) + dist(x2,y2,x3,y3)+ dist(xl,yl,x3,y3));
End
Робота з масивами
Для збереження та обробки великої кількості даних (сотень, тисяч тощо) у мовах програмування звичайно вводять спеціальний тип даних масив.
Масив у мові програмування — це сукупність даних одного типу.
Змінні типу масив на мові програмування Паскаль описуються у вигляді: <ім'я масиву> : array[ПЗ.,КЗ] of <тип даних>; де <тип даних> — це тип змінних, які складають масив; тип даних — це будь-який тип даних, у тому числі і масив; <ім'я масиву> — це ідентифікатор, він створюється за тими самими правилами, що й імена змінних; ПЗ — це номер першого елемента масиву, КЗ — номер останнього елемента (тобто загалом масив матиме КЗ-ПЗ+1 елемент); значення ПЗ та КЗ повинні бути константами одного типу даних, тип даних має бути таким, щоб його значення можна було перелічити (наприклад, цілий або символьний, але не дійсний).
Масиви часто називають ще лінійними таблицями.
Наприклад: .
Atarrayfl.. 100] of integer;
- масив із сотні цілих чисел;
B:array[*a'..'d'] of real;
- масив із 4 дійсних чисел;
С:аггау[-5. .5] of array[0..3] of char;
— масив із 44 змінних символьного типу
(11 масивів-по 4 елементи в кожному).
Масиви масивів називають ще двомірними масивами, або матрицями. Якщо представити
двомірний масив у вигляді прямокутної таблиці, то перший номер буде номером рядка масиву, а другий— номером стовпчика.
Вкладену структуру масивів можна продовжувати довше, тоді з'являться тримірні, чоти-римірні масиви і так далі.
Для звертання до конкретного елемента масиву (для надання йому значення або для його і зчитування) після назви масиву в квадратних., дужках зазначається номер елемента, наприклад:
А[3] :=8;
А[Х+6] := А[Х+7] - б;
В['с'] := А[4] / 65.89;
С[4][3] :='?';
Двомірні масиви часто трапляються в прак-1 тичних задачах (тримірні та вище — майже ні-| коли), тому для них у.мові програмування Паскаль дозволений скорочений опис: <ім'я масиву>:array[П31..К31,П32..К32] of
<тип даних>;
П31..К31 — це діапазон зміни номера pядка масиву, а П32..К32 — діапазон номера стовпця.
(тобто загалом масив матиме
(К31-П31+1) • (К32-П32+1) елемент).
Наприклад:
М:аггау{5..10,1..5] of integer;
- двомірний масив із ЗО змінних цілої* типу (6 рядків по 5 елементів у кожному).
М[6,3]:=8;
M[g+l,gdiv4]:=g-7;
Стандартні алгоритми робот з настами
Існує багато алгоритмів обробки масивів Нижче наведені деякі найпоширеніші з них? Обробка буде проводитися на прикладах маси-| вів:
А:array[1..100] of integer;
M:array[l..20,1..10] of integer;
1. Введення масиву з клавіатури.
for(i:=l to 100 do
begin
write{'Введіть ',і,'-ий елемент:');
readln(A[i]); end;
for i:=l to 20 do for j:=l to 10 do
begin
write ('Введіть ',i/ ', j,' елемент:');
readln(M[i,j]);
end;
2, Виведення масиву на екран,
for і:=1 to 100 do
write(A[i'] :4);
for i:=l to 20 do
begin
for j:=l to 10 do
write(M[i, j]:4);
writeln;
end;
- Обчислення суми елементів масиву.
s:=0;
for i:=l to 100 do s:=s+A[i];
s:=0;
for i:=l.to 20 do
for j:=l to 10 do
s:=s+M[i,j];
Для підрахунку добутку чисел до тексту фрагмента необхідно внести такі зміни: значення змін-.вої s спочатку повинно дорівнювати 1; наступне значення змінної s можна дістати через попереднє - шляхом помноження s:=s*A[i] (або M[i,j]).
4. Обчислення кількості елементів масиву за ознакою (наприклад, кількості парних елементів).
• k:=0;
' for i:=l to 100 do
if A[i] mod 2 = 0 then
k::=k+l;
k::=0;
for i:=l to 20 do
for j:=l to 10 do
if M(i,j] mod 2 = 0 then
k::=k+l;
Для обчислення кількості елементів за іншою ознакою змінюється тільки умова.
5. Знаходження найбільшого елемента масиву.мах:=А[1];
for i:=2 to 100 do
if A[i]>max then
max:=A[i];
мах:=М[1,1];
for i:=l to 20 do
for j:=l to 10 do
if M[i,jJ>max then
max:=M[i,j];
Для знаходження найменшого з елементів " > масиву в умові треба замінити знак більше «>» на менше «<».
6. Пошук заданого елемента в масиві (лінійний пошук).
Метод лінійного пошуку полягає в тому, ще перевіряються всі елементи масиву з початку де кінця по черзі. Якщо при перевірці зщрсодняьед-елемент, перевірка зупиняється, інакше доходить до кінця масиву. Лінійний пошу»-не дуже ефективний спосіб пошуку елемента масиві, але для довільного масиву цей спосіб єдиний.
Приклад фрагмента програми:
і:=0;
repeat
і:=і+1;
until (і-ЮО) ог (А[і]=х);
if A[i]<>x then
write ('Елемент не знайдено.')
else
write('Елемент має номер:',і);
Пошук у двомірному масиві зручно реалізовувати за допомогою однієї змінної, яка буде пробігати значення від 1 до N*M, де N та М —це розміри двомірного масиву. Номер рядка можна обчислити через і за формулою:
(і - 1) div 10 .+ 1,...
номер стовпця:
(і - 1) mod 10 + 1.
Приклад фрагмента програми:
і:=0;
repeat
і:=і+1;
until (i=200.) or: (M[ (i-1) div 10+1,
(і-1) mod 10+1 ]=х); ,
if (Mf(i-l) div ІО+І; (i-1) mod 10+1] o=xj
then
write {'Елемент не знайдено.')
else
write ('Елемент знаходиться за номером:',
(i-1) div 10+1,", (i-1) mod 10+1);
Існує три можливих види пошуку:
• знаходження номера першого входження заданого елемента в масив (приклад фрагмента програми наведено вище);
• знаходження номера останнього входження за-с даного елемента в масив (пошук треба виконувати, починаючи з кінця масиву до його початку);
• знаходження номерів всіх входжень; го елемента в масив.
Алгоритм пошуку всіх елементів у масиві ілюструє метод прапорця.
«Прапорець»— це Змінна, яка може набувати одне з двох значень, звичайно це true та false. Таку змінну доцільно застосовувати в циклічних алгоритмах як сигнал виконання певної умови. До початку роботи циклу «прапорцю» надається значення false. У тілі циклу розміщується умовний оператор, в якому при виконанні умови, що перевіряється, значення змінної.— «прапорця» змінюється на true («Прапорець» піднято). Якщо після закінчення роботи циклу значення «прапорця» дорівнює false, то умова в тілі циклу не виконалася жодного разу.
Приклад фрагмента програми:
flag:=false;
for i:=l to 100 do
if x=A[i] then
begin
Writeln ( 'Елемент має номером:' ,i);
flag:=true;
end;
if not flag then
write('Елемент не знайдено.');
7. Пошук заданого елемента у впорядкованому масиві (двійковий пошук).
Суттєво скоротити кількість операцій, які необхідні для знаходження заданого числа у впорядкованому (наприклад, за зростанням) масиві, дозволяє алгоритм так званого двійкового пошуку (його називають також алгоритмом бінарного пошуку, або алгоритмом ділення навпіл). За цим алгоритмом задане число порівнюється із середнім за номером елементом. Якщо серединне число виявляється більшим за задане, то задане число має знаходитися у першій половині масиву, якщо менше — у другій. Tаким чином, за одне порівняння діапазон пошуку зменшується удвічі. Зазначена процедура повторюється далі для зменшеного діапазону пошуку і так далі до тих пір, поки довжина діапазону не зменшиться до 1.
Двійковий пошук дозволяє значною мірою скоротити кількість необхідних для пошуку перевірок, наприклад для масиву з 1000 чисел задане число буде знайдене щонайбільше за 10 порівнянь.
Приклад фрагмента програми:
1:=1; {ліва межа діапазону пошуку}
г:=п;
{права межа діапазону пошуку}
fl:=false;
{ознака того, що число знайдене}
repeat
m:=(l+r)div 2; {обчислення середини діапазону}
if x=A[m] then fl:=true;
{число знайдене}
if x
{менше, зміна правої межі}
else 1:=ггН-1;
{більше, зміна лівої межі}
until (1>г) or fl;
{число знайдене або ліва границя більша за праву}
if fl then
writeln('Число знаходиться на місці ', м)
else writelh('Такого числа немає.');
З використанням двійкового пошуку можна швидко знайти номер одного із входжень заданого елемента в масив. Якщо в упорядковане масиві таких елементів декілька, то вони ять поспіль. Тож знайти всі входження заданого елемента — це означає знайти діапазон. знайшовши одне входження елемента двійкові пошуком, можна від нього зміщуватися ліворуч, доки не буде знайдений початок діапазону, потім праворуч до кінця діапазону.
8. Сортування (упорядкування) масиву.
Сортування — дуже розповсюджений процес обробки даних.
Сортування (упорядкування) — це розміщення елементів за певним порядком. Дані масиві можна упорядковувати за незростанням (кожний наступний елемент менше або дорі попередньому), за неспаданням (кожний нася ний елемент більший або дорівнює поперередньому), за іншим принципом (наприклад, спочатку парні, потім непарні, або за; кількість дільників тощо). Тут будуть розглянуті тільк методи сортування за незростанням та неспаданням.
На сьогодні створено десятки методів сортування, які розрізняються за швидкістю, простотою тощо. Тут будуть розглянуті три прості (і малоефективні) методи.
Розглянемо сортування методом обміну (а методом «бульбашки»), наприклад, за неспаданням.
Опис методу:
Зліва направо послідовно порівнюються І сусідніх елементів: якщо лівий більший за І вий, то вони міняються позиціями і на другу позицію (як бульбашка), переміщується ший з двох елементів; Спочатку порівнюються перший та другий, потім другий та третій і далі до передостаннього та останнього. Після такого проходу на останню позицію переміщується найбільший елемент масиву. Перший перегляд масиву завершено. Далі здійснюється
- перегляд масиву від першого елемента до передостаннього, в результаті другий за величиною, елемент стає на передостаннє місце. Далі здійснюється перегляд масиву до перед перед останнього елемента і так далі. Останній перегляд буде ,від першого до другого елемента. Масив упорядковано.
Приклад фрагмента програми:
for і:=1 to 99 do
{і - номер перегляду масиву,перегляд здійснюється від позиції 1 до п-і+1}
for j:=l to 100-i do
if A[j]>A[j+l] then {обмін}
begin
t:=A[j+l];A[j+l]:=A[j];A[j]:=t;
end;
Для упорядкування масиву за незростанням треба замінити в умові знак більше «>» на менше «<» (на останню позицію буде переміщуватися найменший елемент).
Сортування обміном має ефективність приблизно удвічі нижчу, ніж наведений нижче метод вставляння. Алгоритм обміну можна поліпшити, якщо на кожному перегляді масиву .перевіряти, чи не є весь масив вже відсортованим. Це можна реалізувати за допомогою «прапорця» (див. вище «Лінійний пошук»).
Приклад фрагмента програми:
і:=1; flag:=true;
while flag do .
begin
flag:=false;
forj:=lto100-ido if A[j]>A[j+l] then
begin
t:=A[j+l];A[j+l]:=A[j];A[j]:=t; flag:=true;
end; i:=i+l;
end;
Розглянемо сортування методом вибору, наприклад за незростанням.
Опис методу:
Серед усіх елементів масиву знаходиться найбільший елемент, який потім міняється позиціями з першим. Далі від другого елемента до остан-Інього знаходиться найбільший елемент та міняється позиціями з другим. Третій за розміром елемент перемішується на третє місце і так далі. Приклад фрагмента програми:
for i:=l. to 99 do
{і - номер перегляду масиву}
begin
mi: =і; {в mi зберігається номер найбільшого елемента}
forj:=i+l to 100 do
if A[ j]>A[mi] then mi:=j;-t:=A[i];A[i]:=A[mi];A[mi]:=t;
end;
Для упорядкування масиву за неспаданиям треба замінити в умові знак менше «<» на більше «>» (на першу позицію буде переміщуватися найменший елемент).
Метод вибору дещо менш ефективний, віяк метод вставляння, але значно ефективніший* ніж метод обміну.
Розглянемо сортування методом вставляя? ня, наприклад за незростанням.
Опис методу:
Порівнюються перші два елементи масиву АРІ і А2: якщо А[1]<А[2], то елементи міняються позиціями. Таким чином, отримаємо перші два елементи масиву упорядкованими. Далі береться А[3] та вставляється в упорядковану послідовність попередніх елементів так, щоб упорядку= вання не порушилось. Цей процес продовжується до останнього елемента масиву.
Приклад фрагмента програми (для коректне! роботи фрагмента в масиві має бути додатковий елемент з номером 0):
for i:=l to 99 do
begin
j:=i; t=A[j+l];
whj.le(A[ j]>t)
and( j>=l> do
begin
A[j+l]:=A[j];
j:=j-l
end;
A[j+l]:=t;
end;
Для упорядкування масиву за неспаданням треба замінити в умові знак більше «>» на менше «<».
Стандартні алгоритми роботи з рядками
Існує багато алгоритмів обробки текстової інформації. Нижче наведені деякі найпоширеніші з них. Обробка буде проводитися для рядка:
s:string;
1. Заміна всіх входжень заданого слова. , * Наприклад, треба замінити в рядку всі слеші; «Паскаль» на «Бейсік».
repeat
t: =pos(ТІаскапь',s); {знаходження слова 'Паскаль'}
if t>0 then {якщо слово знайдене}
begin
delete(s,t,7); {видалення 7 літер}
insert('BeftciK'fSjt); {вставляння слова 'Бейсік'}
end;
until t=0;
2. Видалення зайвих символів. Наприклад, треба в рядку видалити всі зайві проміжки між словами, залишивши їх по одному.
і:=І;
repeat
while fs[i]o' ') and (i
{знаходження проміжку}
i:=i+l;
ifs{i]="then
while (s[i+l]=' ') and (i+l
delete(s,i+1,1);
{видалення проміжку}
until i>=length (s);
3, Розділення рядка на окремі слова.
В рядку необхідно виділити окремо всі слова та записати їх у масив рядків:
Words:array{l..100] of string;
При розв'язанні задачі будемо вважати, що слів у рядку не більше 100, що всі слова відділені одне від одного одним проміжком (якщо проміжків більше, то їх можна видалити як у-попередньому прикладі) і що рядок починається з літери та закінчується літерою.
і:=1; {номер символу в рядку}
prt=0; {номер попереднього проміжку}.
w:=l; {номер слова}
repeat while (s [ і ] о") and (i
i:=i+l; {пошук проміжку}
if s[i]=" then
begin
Words[w] :=copy(s,pr+1,i-pr);
pr:=i;
w:=w+l; i:=i+l;
end;
else
Words[w]:=copy(s,pr+l,i-pr+l);
until i>=length(s); Після виконання цього фрагмента програми w слів рядка s будуть записані в рядки масиву; Words.
ВІТАЄМО З ЗАКІНЧЕННЯМ КУРСУ ІНФОРМАТИКИ.
