Робота з величинами. Введення-виведення виразів. Лінійні алгоритми



Сторінка4/8
Дата конвертації04.12.2016
Розмір1,28 Mb.
1   2   3   4   5   6   7   8

Завдання 6. Дана цілочисленна квадратна матриця. Знайти в кожному рядку найбільший елемент і поміняти його місцями з елементом головної діагоналі.

Program Obmen;

Var N, I, J, Max,Ind, Vsp : Integer;A : Array [1..15, 1..15] Of Integer;

Begin


WRITE('Уведіть кількість елементів у масиві: '); READLN(N);

FOR I := 1 TO N DO

FOR J := 1 TO N DO

Begin


WRITE('A[', I, ',', J, '] '); READLN(A[I, J])

End;


FOR I := 1 TO N DO

Begin


Max := A[I, 1]; Ind := 1;

FOR J := 2 TO N DO

IF A[I, J] > Max THEN

Begin


Max := A[I, J]; Ind := J

End;


Vsp := A[I, I]; A[I, I] := A[I, Ind]; A[I, Ind] := Vsp

End;


FOR I := 1 TO N DO

Begin


WriteLn;

FOR J := 1 TO N Do Write(A[I, J] : 3);

End; WriteLn

End.
ПІДПРОГРАМИ

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

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

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

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

Підпрограми можуть бути двох видів: підпрограма без параметрів і підпрограма з параметрами. Звертання до підпрограми може бути організоване з будь-якого місця основної програми або іншої підпрограми скільки завгодно раз.

При роботі з підпрограмами важливими є поняття формальних і фактичних параметрів. Формальні параметри — це ідентифікатори вхідних даних для підпрограми. Якщо формальні параметри одержують конкретні значення, то вони називаються фактичними. Формальні параметри можуть одержати конкретні значення тільки в тій програмі, де виробляється звертання до даного модулю-підпрограмі. Тип і порядок запису фактичних параметрів повинні бути такими ж, як і формальних параметрів. У противному випадку результат роботи програми буде непередбаченим. Із цього треба, що фактичні параметри використаються при звертанні до підпрограми з основний, а формальні параметри - тільки в самому модулі.



Процедури

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

При складанні підпрограм з параметрами треба дотримувати наступних правил:

1) кожна підпрограма має своє ім'я й список формальних параметрів;

2) процедура з основної програми викликається командою виклику, що за формою нічим не відрізняється від виклику команди виконавця. Результат привласнюється однієї або декільком змінним, які перебувають у списку формальних параметрів. Але результатом можуть бути, звичайно, не тільки значення змінних, але яке або дія, виконана ЕОМ.

Приклад 1. Використаємо алгоритм знаходження найбільшого загального дільника двох натуральних чисел у якості допоміжного при рішенні завдання: скласти програму вирахування дробів (a, b, c, d — натуральні числа). Результат представити у вигляді звичайного нескоротного дробу.

Підпрограма.

1) Увести натуральні числа M, N.

2) Якщо M=N, перейти до п. 5, інакше до наступного пункту.

3) Якщо M>N, те M:=M-N, інакше N:=N-M.

4) Перейти до п. 2.

5) Передати значення M в основну програму.

6) Кінець підпрограми.

Основна програма.

1) Увести значення A, B, C, D.

2) E:=A*D - B*C.

3) F:= B*D.

4) Якщо E=0, вивести значення E і перейти до п. 9, інакше перейти до наступного пункту.

5) M:=|E|, N:=F, перейти до підпрограми обчислення НОД.

6) G := M.

7) E й F націло розділити на G.

8) Вивести значення E й F на печатку.

9) Кінець програми.

Program Sub;

Var A, B, C, D, G, E, F : Integer;

Procedure Nod(M, N : Integer; Var K : Integer);

Begin


While M <> N Do

If M > N Then M := M - N Else N := N - M;

K := M

End;


Begin

Write('Уведіть чисельники й знаменники дробів:');

ReadLn(A, B, C, D);

E := A * D - B * C;

F := B * D;

If E = 0 Then WriteLn(E)

Else

Begin


Nod(Abs(E), F, G);

E := E Div G;

F := F Div G;

WriteLn('Відповідь: ', E, '/', F)

End

End.


Як видно із прикладу, оголошення й тіло підпрограм перебуває в розділі описів. У заголовку підпрограми втримується список формальних параметрів із вказівкою їхнього типу, які умовно можна розділити на вхідні й вихідні (перед ними коштує службове Var). При звертанні до процедури вказується її ім'я й список фактичних параметрів. Формальні й фактичні параметри повинні відповідати по кількості й по типі.

Виклик процедури здійснюється в такий спосіб:



<Ідентифікатор (ім'я) процедури>(<список фактичних параметрів>);

Наприклад,

Nod(Abs(E), F, G);

По способі передачі фактичних значень у підпрограму в Turbo Pascal 7.0 виділяють параметра-змінної, параметра-значення, параметра-константи й масиви відкритого типу, рядка відкритого типу, параметра-процедури, параметрів-функції.



Функції

Функція (на відміну від процедури) завжди повертає єдине значення.

Покажемо, як зміниться підпрограма із приклада, якщо неї записати у вигляді функції.

Function Nod(M, N : Integer) : Integer;

Begin

While M <> N Do



If M > N Then M := M - N Else N := N - M;

Nod := M


End;

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

Виклик функції буде наступним:

G := Nod(Abs(E), F);

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

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



Приклад 2. Дано натуральне число n. Переставити місцями першу й останню цифри цього числа.

Program Integ;

Var N : Integer;

Begin


Write('Уведіть натуральне число: ');

ReadLn(N);

If Impossible(N)

Then WriteLn('Неможливо переставити цифри, виникне переповнення')

Else Begin

Change(N);

WriteLn('Відповідь: ', N)

End;


End.

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

Function Impossible(N : Integer) : Boolean;

Begin


If Number(N) < 5

Then Impossible := False

Else Impossible := (N Mod 10 > 3) Or

(N Mod 10 = 3) And

(N Mod 10000 Div 10 * 10 + N Div 10000 > MaxInt Mod 10000)

End;


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

Function Number(N : Integer) : Integer;

Var Vsp : Integer;

Begin


Vsp := 0;

While N > 0 Do

Begin

Vsp := Vsp + 1; N := N Div 10



End;

Number := Vsp

End;

Нарешті, остання процедура.



Procedure Change(Var N : Integer);

Var Kol, P, S, R : Integer;

Begin

Kol := Number(N);



P := N Mod 10; {остання цифра}

If Kol > 1 Then

S := N Div Round(Exp((Kol - 1) * Ln(10)))

Else S := 0; {перша цифра}

R := N Mod Round(Exp((Kol - 1) * Ln(10))) Div 10;

N := P * Round(Exp((Kol - 1) * Ln(10))) + R * 10 + S

End;

Можливі також підпрограми, які викликають самі себе. Вони називаються рекурсивними. Створення таких підпрограм є гарним прийомом програмування, але не завжди доцільно через надмірну витрату пам'яті ЕОМ.



Приклад 3. Знайти максимальну цифру в записі даного натурального числа.

Program MaxDigit;

Type NaturLong = 1..(High(LongInt));

Digit = 0..9;

Var A : LongInt;

Function Maximum(N : LongInt) : Digit;

Begin

If N < 10



Then Maximum := N

Else If N Mod 10 > Maximum(N Div 10)

Then Maximum := N mod 10

Else Maximum := Maximum(N Div 10)

End;

Begin


Write('Уведіть натуральне число: ');

ReadLn(A);

WriteLn('Максимальна цифра дорівнює ', Maximum(A))

End.


При створенні функції Maximum було використано наступне міркування: якщо число складається з однієї цифри, то вона є максимальної, інакше якщо остання цифра не є максимальною, то її варто шукати серед інших цифр числа. При написанні рекурсивного алгоритму варто подбати про граничну умову, коли ланцюжок рекурсивних викликів обривається й починається її зворотне «розкручування». У нашому прикладі ця умова N < 10.

Більш докладно про рекурсії говориться в наступній статті.



РЕКУРСІЯ

 Рекурсія — це такий спосіб організації допоміжного алгоритму (підпрограми), при якому ця підпрограма (процедура або функція) у ході виконання її операторів звертається сама до себе. Взагалі, рекурсивним називається будь-який об'єкт, що частково визначається через себе.

Наприклад, наведене нижче визначення двійкового коду є рекурсивним:

<двійковий код> ::= <двійкова цифра> | <двійковий код><двійкова цифра>

<двійкова цифра> ::= 0 | 1

Тут для опису поняття були використані, так називані, металінгвістичний формули Бекуса-Наура (мова БНФ); знак "::=" позначає "по визначенню є", знак "|" - "або".

Взагалі, у рекурсивному визначенні повинно бути присутнім обмеження, гранична умова, при виході на яке подальша ініціація рекурсивних обігів припиняється.

Приведемо інші приклади рекурсивних визначень.



Приклад 1. Класичний приклад, без якого не обходяться в жодній розповіді про рекурсії, — визначення факторіала. З одного боку, факторіал визначається так: n!=1*2*3*...*n. З іншого боку, Граничною умовою в цьому випадку є n<=1.

Пример 2. Визначимо функцію K(n), що повертає кількість цифр у заданому натуральному числі n:

Завдання. За аналогією визначите функцію S(n), що обчислює суму цифр заданого натурального числа.

Приклад 3. Функція C(m, n), де 0 <= m <= n, для обчислення біноміального коефіцієнта по наступній формулі є рекурсивною.

Нижче будуть наведені програмні реалізації всіх цих (і не тільки) прикладів.

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

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

Виконання дій у рекурсивній підпрограмі може бути організовано одним з варіантів:

Begin Begin Begin

P; оператори; оператори;

оператори; P P;

End; End; оператори

End;
рекурсивний підйом рекурсивний спуск і рекурсивний спуск, і рекурсивний підйом


Тут P — рекурсивна підпрограма. Як видно з малюнка, дії можуть виконуватися або на одному з етапів рекурсивного обігу, або на обох відразу. Спосіб організації дій диктується логікою розроблювального алгоритму.

Реалізуємо наведені вище рекурсивні визначення у вигляді функцій і процедур мовою Pascal й у вигляді функцій мовою C.

 Приклад 1.

{Функція на Pascal}

Function Factorial(N:integer):Extended;

Begin


If N<=1

Then Factorial:=1

Else Factorial:=Factorial(N-1)*N

End;


{Процедура на Pascal}

Procedure Factorial(N:integer; Var F:Extended);

Begin

If N<=1


Then F:=1

Else Begin Factorial(N-1, F); F:=F*N End

End;

Приклад 2.

{Функція на Pascal}

Function K(N:Longint):Byte;

Begin


If N<10

Then K:=1

Else K:=K(N div 10)+1

End;


{Процедура на Pascal}

Procedure K(N:Longint; Var Kol:Byte)

Begin

If N<10


Then Kol:=1

Else Begin K(N Div 10, Kol); Kol:=Kol+1 End;

End;

Приклад 3.

{Функція на Pascal}

function C(m, n :Byte):Longint;

Begin
If (m=0) or (m=n)

Then C:=1

Else C:=C(m, n-1)+C(m-1, n-1)

End;

{Процедура на Pascal}



Procedure C(m, n: Byte; Var R: Longint);

Var R1, R2 : Longint;

Begin

If (m=0) or (m=n)



Then R:=1

Else Begin

C(m, n-1, R1);

C(m-1, n-1, R2);

R:=R1+R2

End;


End;

Приклад 4. Обчислити суму елементів лінійного масиву.

При рішенні завдання використаємо наступне міркування: сума дорівнює нулю, якщо кількість елементів дорівнює нулю, і сумі всіх попередніх елементів плюс останній, якщо кількість елементів не дорівнює нулю.



{Програма мовою Pascal}

Program Rec2;

Type LinMas = Array[1..100] Of Integer;

Var A : LinMas;

I, N : Byte;

{Рекурсивна функція}

Function Summa(N : Byte; A: LinMas) : Integer;

Begin


If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A)

End;


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

Begin


Write('Кількість елементів масиву? '); ReadLn(N); Randomize;

For I := 1 To N Do

Begin

A[I] := -10 + Random(21); Write(A[I] : 4)



End;

WriteLn; WriteLn('Сума: ', Summa(N, A))

End.


Приклад 5. Визначити, чи є заданий рядок паліндромом, тобто читається однаково ліворуч праворуч і праворуч ліворуч.

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

{програма мовою Pascal}

Program Palindrom;

{Рекурсивна функція}

Function Pal(S: String) : Boolean;

Begin

If Length(S)<=1



Then Pal:=True

Else Pal:= (S[1]=S[Length(S)]) and Pal(Copy(S, 2, Length(S) - 2));

End;

Var S : String;



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

Begin


Write('Уведіть рядок: '); ReadLn(S);

If Pal(S) Then WriteLn('Рядок є паліндромом')

Else WriteLn('Рядок не є паліндромом')

End.


Завдання. Використовуючи аналогічний підхід, визначите, чи є задане натуральне число паліндромом.

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



СТВОРЕННЯ БІБЛІОТЕК ПІДПРОГРАМ В TURBO PASCAL

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

В Turbo Pascal це обмеження переборюється за рахунок, по-перше, введення зовнішніх процедур, по-друге, розробки й використання модулів. У дійсній публікації на прикладах розглянемо роботу з тими й іншими програмними одиницями.

Почнемо із зовнішніх підпрограм.

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

Покажемо це на прикладі завдань цілочисленої арифметики, де аргументи, результати й проміжні величини є цілими (Integer, Word, LongInt і т.д.). От кілька таких завдань.

1. Дано натуральне число n. Знайти суму першої й останньої цифри цього числа.

2. Дано натуральне число n. Переставити місцями першу й останню цифри цього числа.

3. Дано натуральне число n. Дописати до нього цифру k у кінець й у початок (якщо це можливо, тобто результат не вийде за діапазон припустимих значень), або повідомити про неможливість виконання операції.

4. Знайти найбільшу цифру в записі даного натурального числа.

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

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

От можливий варіант такої функції:

Function Digits(N : LongInt) : Byte;

Var Kol : Byte;

Begin


Kol := 0;

While N <> 0 Do Begin Kol := Kol + 1; N := N Div 10 End;

Digits := Kol

End;


Збережемо цей текст у файлі з розширенням .inc (це розширення зовнішніх підпрограм в Turbo Pascal), наприклад, digits.inc.

Ще необхідна функція зведення натурального числа в натуральний ступінь.

Function Power(A, N : LongInt) : LongInt; {файл power.inc}

Var I, St : LongInt;

Begin

St := 1;


For I := 1 To N Do St := St * A;

Power := St

End;

Спробуємо використати функції при рішенні завдання номер один.



Program Example1;

Var N, S : LongInt;

{$I digits.inc} {підключаємо зовнішню функцію digits.inc, що повертає кількість цифр у записі числа}

{$I power.inc} {зовнішня функція, що виконує зведення числа A у ступінь N}

Begin

Write('Уведіть натуральне число: ');



ReadLn(N);

{для визначення останньої цифри числа N беремо залишок від розподілу цього числа на 10, а для визначення першої ділимо N на 10 у ступені на одиницю меншу, чим кількість цифр у записі числа (нумерація розрядів починається з 0)}

S := N Mod 10 + N Div Power(10, Digits(N) - 1);

WriteLn('Шукана сума: ', S)

End.

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



Далі мова йтиме про модулі: їхній структурі, розробці, компіляції й використанні.

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

В основі ідеї модульности лежать принципи структурного програмування. Існують стандартні модулі Turbo Pascal, які звичайно описуються в літературі по даній мові.

Модуль має наступну структуру:

Unit <ім'я модуля>; {заголовок модуля}

Interface

{интерфейсная частина}

Implementation

{розділ реалізації}

Begin


{розділ ініціалізації модуля}

End.


Після службового слова Unit записується ім'я модуля, що (для зручності подальших дій) повинне збігатися з ім'ям файлу, що містить даний модуль. Тому (як прийнято в MS DOS) ім'я не повинне містити більше 8 символів.

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

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

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

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


Каталог: Documenty
Documenty -> Мета. Формувати розуміння того, що українська мова наш скарб, без якого не може існувати ні народ, ні Україна як держава. Розширювати знання про красу і багатство української мови. Ознайомити дітей з українськими обрядами і звичаями
Documenty -> Виступ на науково-пошуковій конференції “Типи учнівських проектів” заступника директора з нвр бойко Тетяни Петрівни
Documenty -> Урок №1 Растрова, векторна і фрактальна графіка. Історія анімації. Формати графічних і анімаційних файлів
Documenty -> Відомість про наукову, науково-методичну, дослідницьку роботу педагогічних працівників Вишнівської загальноосвітньої школи І-ІІІ ступенів №2
Documenty -> Затверджую: погоджено


Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8


База даних захищена авторським правом ©refos.in.ua 2019
звернутися до адміністрації

увійти | реєстрація
    Головна сторінка


завантажити матеріал