Список літератури

1. Абрамов С.А., Зима Е.В. Початку інформатики. —М.: Наука, 1990.

2. Грогоно П. Програмування мовою Паскаль. - М.: Світ, 1982.

3. Йенсен К., Вирт H. Паскаль. Керівництво для користувача й опис мови. -М.: Фінанси і статистики, 1982.

4. Перминов О.Н. Програмування мовою Паскаль. - М.: Радіо і зв'язок, 1988.

5. Пильщиків В.Н. Збірник вправ по мові Паскаль. - М.:

Павука, 1989.

6. Прайс Д. Програмування мовою Паскаль. Практичне керівництво. -М.: Світ, 1987.

7. Турбо Паскаль 7.0. - К.: Тортово-издательское бюро BHV, 1996.

8. Фараонов В.В. Турбо Паскаль 7.0. Початковий курс. Навчальний посібник.-М.: «Нолидж», 1997.

Додаток а (довідковий) Основні алгоритми обробки масивів

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

1. Підсумовування елементів вектора..

Дано вектор А(n)=a¹,a², …,aⁿ... Знайти .

Приклад програми:

const

n = 10;

type massiv = array[1..n] of integer;

var

a : massiv; i, s : integer;

begin

writeln(‘Введіть’,n,’значень елементів вектора:’);

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

{обчислення суми}

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

writeln(‘сума елементів вектора = ‘,s);

end.

2. Підсумовування елементів матриці.

Дано матрицю A(nXm). Знайти суму елементів матриці. Приклад програми:

const

N = 3; m = 5;

type massiv = array[1..n,1..m]of real;

var

a : massiv; i, j : integer; s : real;

begin

writeln (‘Введіть’,n,’X’,m,’=’,n*m,’елементів матриці:’);

for i := 1 to n do

for j :=1 to m do

read (a[i,j]);

{обчислення суми}

for i := 1 to n do

begin

for j :=1 to m do s := s+a[i,j];

end;

writeln(‘сума елементів матриці = ‘,s:3:1);

end.

4. Підсумовування діагональних елементів двох векторів (обчислення сліду матриці).

Дано квадратну матрицю А(nXm). Обчислити слід матриці.

Приклад програми:

const

n = 4;

турі massiv = array[1..n,1..n] of real;

var

a : massiv; i,j : integer; s : real;

begin

writeln(‘Введіть ’,n,’X’,n,’ = ’,n*n,’ елементів матриці:’);

for i := 1 to n do

for j := 1 to n do

read(a[i,j]);

{обчислення сліду матриці}

for i := 1 to n do s := s+a[i,j];

write(‘Слід матриці = ’,s:3:1);

end.

1. Підсумовування елементів двох векторів.

Для векторів А и В розміром n необхідно обчислити s := a[i]+b[i]; i=1,2…,n...

Приклад програми:

сonst

n = 4;

type massiv = array[1..n] of real;

var

a, b : massiv; i : integer; s: real;

begin

writeln (‘Введіть ‘,n,’ елементів вектора А:’);

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

writeln (‘Введіть ‘,n,’ елементів вектора B:’);

for i :=1 to n do read(b[i]);

{обчислення суми}

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

write(‘Сума векторів А+У = ‘,s:3:1);

end.

5. Підсумовування елементів двох матриць.

Для матриць А и В розміром nXm необхідно обчислити s := a[i,j]+b[i,j] , i=1,2,…,m...

Приклад програми.

const

n = 3, m = 4;

type massiv = array[1..n, 1..m]of real;

var

a,b : massiv; i,j : integer; s : real;

begin

writeln(‘Введіть матрицю А розміром’,n,’X’,m,’:’);

for i:= 1 to n do

for j:= 1 to m do

read(a[i,j]);

writeln(‘Введіть матрицю B розміром’,n,’X’,m,’:’);

for i := 1 to n do

for j:= 1 to m do

read(b[i,j]);

for i:= 1 to n do {обчислення суми}

for j:= 1 to m do

s := s+a[i,j]+b[i,j];

write(‘Сума матриць А+У = ‘,s:3:1);

end.

2. Підсумовування елементів заданого рядка матриці..

Дано матрицю А(nXm). Знайти суму елементів 2-го рядка.

Приклад програми:

const

n = 3, m = 4;

type massiv = array[1..n, 1..m] of real;

var

a : massiv; i,j : integer; s : real;

begin

writeln(‘Введіть матрицю А розміром’,n,’X’,m,’:’);

for i:= 1 to n do

for j:= 1 to m do

read(a[i,j]);

{обчислення суми}

i := 2;

for j := 1 to m do s := s+a[i,j];

write(‘сума 2-го рядка матриці = ‘,s:3:1);

end.

7. Підсумовування елементів рядків матриці.

Обчислити суму елементів кожного рядка матриці А(nXm). Результат вивести у виді вектора В(n).

Приклад програми:

const

n = 3,m = 4;

type massiv = array[1..n, 1..m] of real;

var

a : massiv; i,j : integer; s : real;

begin

writeln(‘Введіть матрицю А розміром’,n,’X’,m,’:’);

for i:= 1 to n do

for j:= 1 to m do

read(a[i,j]);

write(‘Сума кожного рядка матриці виведена у вектор У(‘,n,’) = ‘);

for i:= 1 to n do

begin

s := 0;

for j := 1 to m do s := s+a[i,j];

write(s:3:1,’ ’:2);

end;

end.

3. Транспонування матриці.

Транспонуванням матриці називається таке її перетворення, при якому i-й стовпець стає i-й рядком, тобто необхідно обчислити b[i,j]:=a[i,j]; i=1,2,...,n; j=1,2,…,m...

Наприклад транспонування

матриці дає матрицю

Приклад програми:

{транспонування матриці А(nXm) заміною рядків матриці її стовпцями}

const

n = 3;

type massiv = array[1..n, 1..m] of real;

var

a : massiv; i,j : integer; s : real;

begin

writeln(‘Введіть матрицю А розміром’,n,’X’,n,’:’);

for i:= 1 to n do

for j:= 1 to m do

read(a[i,j]);

writeln(‘транспонована матриця В:’);

for i:= 1 to n do

begin

for j:= 1 to n do

begin

b[i,j] := a [j,i];{заміна рядка відповідним стовпцем}

write(b[i,j]:3:1,’ ‘,:2);

end;

writeln;

end;

end.

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

На приведеній нижче матриці елементи верхнього і нижнього трикутника виділені жирним шрифтом, а елементи головної діагоналі – звичайним шрифтом.

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

Приклад програми:

{Транспонування квадратної матриці перестановкою відповідних елементів верхнього і нижнього трикутників щодо головної діагоналі}

const

n = 3;

type massiv = array[1..n,1..n] of integer;

var

a : massiv; i, j : integer;

b : integer; {допоміжна змінна}

begin

writeln(‘Введіть матрицю розміром ‘,n,’X’,n,’:’);

for i :=1 to n do

for j :=1 to n do

read(a[i,j]);

{змінюємо місцями елементи верхнього трикутника з відповідними} {елементами нижнього трикутника}

for i := 1 to n do

begin

for j := i+1 to n do

begin

b := a[i,j]; {за допомогою змінної b}

a[i,j] :=a[j,i]; {змінюємо елементи місцями}

a[j,i] := b;

end;

end;

writeln(‘транспонована матриця:’);

for i :=1 to n do

begin

for j :=1 to n do write(a[i,j],’ ‘);

writeln;

end;

end.

4. Множення матриці на вектор.

Обчислити добуток P матриці A(nXm) та вектору B(m), тобто виконати p:=a[і,j]*b[j];

Приклад програми:

const

n = 3; m = 4;

type massiv = array[1..n,1..m] of real;

vector = array[1..m] of real;

var

a : massiv; b : vector; i, j, : integer; p :real;

begin

writeln(‘Введіть матрицю розміром ‘,n,’X’,m,’:’);

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

writeln(‘Введіть вектор розміром ‘,m,’:’);

for j :=1 to m do read (b[j]);

(обчислення добутку)

write(‘Добуток матриці А на вектор В =’);

for i := 1 to n do

begin

for j:= 1 to m do

begin

p := p+a[i,j]*b[j];

end;

end;

write(p:3:1);

end.

9. Множення матриці на матрицю.

Множити можна матриці, що відповідають одне одному за розміром, тобто число стовпців першої матриці повинне дорівнювати числу рядків другої матриці. Для множення матриці A(nXm) на матрицю B(kXm) необхідно обчислити p:=a[і,l]*b[l,j], при і := 1,...,n; j := 1,…m; l:=1,…k

Приклад програми:

const

n = 2; m = 3; k = 3;

type massiv1 = array[1..n,1..k] of real;

massiv2 = array[1..k,1..m] of real;

var

a : massiv1; b : massiv2; i, j, l : integer; p : real;

begin

writeln(‘Введіть матрицю А розміром ‘,n,’X’,k,’:’);

for i := 1 to n do

for j := 1 to k do

read(a[i,j]);

writeln(‘Введіть матрицю B розміром ‘,k,’X’,m,’:’);

for i := 1 to n do

for j := 1 to m do

read(b[i, j]);

write(‘добуток матриць A на B = ’);

for i := 1 to n do

begin

for j :=1 to m do

begin

for l :=1 to k do p := p+a[i,l]*b[l,j];

end;

end;

write(p:3:1)

end.

10. Видалення елемента з вектора.

Видалити k-й елемент із вектора A(n) можна, зрушивши весь “хвіст” вектора, починаючи з (k+1)-го елемента, на одну позицію вліво, тобто виконуючи операції a[i]:=a[i+1]; при i := k, k+1,...,n-1.

Приклад програми:

const

n = 5;

type

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

var

a : massiv; I,k :integer;

begin

writeln(‘Введіть вектор з ‘,n,’ цілих чисел:’);

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

writeln(‘Введіть номер елемента, що видаляється, (від 1 до',n,'):');

read(k);

for i:= k to n-1 do a[i] :=a[i+1];

writeln (‘Вектор без ‘,k,’-го елемента:’);

for i := k to n-1 do write(a[i],’ ‘);

end.

10. Видалення елемента з матриці.

Видалити k-й елемент у i-му рядку матриці A(nXm) можна, зрушивши весь “хвіст” i-й рядка, починаючи з (k+1)-го елемента, на одну позицію вліво, тобто виконуючи операції a[i,j] := a[i,j+1]; при j :=k,k+1,...m-1;

Після зрушення значення елемента в останньому рядку стане рівним нулю тобто a[і,j]:=0 при j := m;

Приклад програми:

const

n = 3; m = 3;

var

a := array[1..n,1..m] of integer; i, j, k : integer;

begin

writeln(‘Введіть матрицю розміром ‘,n,’X’,m,’=’,n*m,’цілих чисел:’);

for i :=1 to n do

for j :=1 to m do

read (a[i,j]);

writeln(‘Задайте номер рядка елемента, що видаляється:');

readln(i);

writeln(‘Задайте позицію елемента, що видаляється:');

readln(k);

for j := k to m-1 do {видалення елемента}

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

j := m; a[i,j] := 0;

writeln(‘Матриця, з якої вилучений елемент a[‘,i,’,’,k,’]:’);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j],’ ‘);

writeln;

end;

end.

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

Для включення елемента в i-у позицію вектора необхідно пересунути його “хвіст” вправо на одну позицію, виконуючи операцію a[i+1] :=a[i], при i:=n, n-1,…,i... Переміщення виконують з кінця, інакше весь “хвіст” буде заповнений елементом a[і]. Далі, a[і]-му елементу привласнюється задане значення b. Розмір масиву збільшується на 1.

Приклад програм:

{Варіант рішення з використанням циклу For}

const

n = 5;

var

a : array[1..n+1] of integer; i, b :integer;

begin

writeln(‘Введіть’,n,’ цілих чисел вектора:’);

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

writeln(‘Задайте позицію включення нового елемента:’);

readln(i);

writeln(‘Задайте ціле значение елемента, що включається:');

readln(b);

for i := n downto i do {включення елемента}

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

a[i] := b;

writeln(‘Вектор із включеним елементом:’);

for i := 1 to n+1 do write(a[i],’ ‘)

end.

{Варіант рішення з використанням стандартної процедури move}

const

n = 5;

var

a : array[1..n+1] of integer; i, b : integer;

begin

writeln(‘Введіть ‘,n,’ цілих чисел вектора:’);

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

writeln(‘Задайте позицію включення нового елемента:’);

readln(i);

writeln(‘Задайте ціле значение елемента, що включається:');

readln(b);

{включення елемента}

{помноженого на 2, тому що тип integer займає 2 байти}

move(a[i],a[i+1],(n+1-i)*2);

a[i]:=b;

writeln(‘Вектор із включеним елементом:’);

for i := 1 to n+1 do write(a[i],’ ‘)

end.

Застосування процедури Move, що відразу пересилає вміст основної пам'яті, починаючи з першого байта змінної a[i], в область, яка починається з першого байта змінної a[i+1], вигідно відрізняється швидкістю виконання від змінної циклу For, у якому проглядаються всі елементи вектора.

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

Для включення елемента в j-у позицію i-го рядка скористаємося стандартною процедурою Move, потім привласнимо a[i,j] значення елемента, що включається, b.

Приклад програми:

{Включення елемента в визначену позицію квадратної матриці}

const

n = 3; m = 4;

var

a : array[1..n,1..m] of integer; i, j, b : integer;

begin

writeln(‘Введіть матрицю розміром ‘,n,’X’,n,’=’,n*n,’цілих чисел:’);

for i := 1 to n do

for j := 1 to n do

read(a[i,j]);;

writeln(‘задайте номер i рядка для елемента, що включається:');

readln(i);

writeln(‘задайте позицію j у рядку для елемента, що включається:');

readln(j);

{включення елемента}

writeln(‘Введіть значення елемента, що включається:');

readln(b);

move(a[i,j],a[i,j+1],(m-j)*2);

a[i,j] := b;

writeln(‘матриця з включеним елементом:’);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j], ‘ ‘);

writeln;

end;

end.

Для матриці, що складає з елементів типу Real, у програмі в процедурі Move існує параметр, що визначає довжину області, помножений на 6 (стільки байт необхідно для типу Real):

Move(a[i,j],a[i,j+1],(m-j)*6);

10. Включення елемента в упорядкований за зростанням вектор зі збереженням упорядкованості.

Приклад програми:

const

n = 5;

var

a : array[0..n] of integer; i,b : integer;

control : Boolean;

begin

writeln(‘Введіть впорядкований за зростанням вектор з ‘,n, ‘цілих ‘чисел:’);

for i := 0 to n-1 do

read(a[i]);

writeln(‘Задайте ціле значение елемента, що включається:');

readln(b);

{включення елемента}

for i := 0 to n-1 do if b < a[i] then

begin

move(a[i], a[i+1],(n-1)*2);

a[i] := b;

control := true;

break;

end;

if not control then a[n] := b;

writeln(‘Вектор із включеним елементом:’);

for i := 0 to n do write(a[i],’ ‘);

end.

15. Видалення рядка з матриці.

Для видалення k-й рядка потрібно всі рядки, починаючи з (k+1)-го, перемістити нагору, а їхнє число зменшити на 1.

Приклад програми:

const

n = 3; m = 4;

type

massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k : integer;

begin

writeln(‘Введіть матрицю розміром’,n,’х',m,’:’);

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

writeln(‘Введіть номер рядка, що видаляється, (від 1 до ',n,'):');

read(k);

for i := k to n-1 do

for j := 1 to m do

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

writeln(‘матриця без ‘,k,’-го рядка:’);

for i:=1 to n-1 do

begin

for j:= 1 to m do

begin

write(a[i,j],’ ‘);

end;

writeln;

end;

end.

15. Включення вектора у вектор.

Для включення вектора В до вектора А з позиції i потрібно зрушити елементи вектора А праворуч, починаючи з позиції i, на довжину вектора, що включається.

Приклад програми:

const n = 8; {довжина вектора А}

m = 4; {довжина вектора, що включається, У}

var

a : array[1..n+m] of integer;

b : array[1..m] of integer;

i : integer;

begin

writeln(‘Введіть ’,n,’ цілих чисел вектора А:’);

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

writeln(‘Введіть ’,m,’ цілих чисел вектора, що включається, В:');

for i := 1 to m do read(b[i]);

writeln(‘Задайте позицію у векторі А для включення вектора В:’);

readln(i);

{включення вектора}

move(a[i],a[i+m].(n-i+1)*2);

move(b,a[i],m*2);

writeln(‘Вектор А з включеним вектором В:’);

for i := 1 to n+m do write(a[i],’ ‘);

end.

15. Включення стовпця в матрицю

Для включення стовпця в матрицю потрібно зрушити її стовпці вправо, збільшуючи їхню кількість на 1.

Приклад програми:

const

n = 3; m = 4;

var

a : array[1..n,1..m] of integer; i, j : integer;

begin

writeln (‘Введіть матрицю ’,n,’X’,m-1,’=’,n*(m-1),’ цілих чисел:’);

for i := 1 to n do

for j := 1 to m-1 do

read(a[i,j]);

writeln(‘Введіть номер стовпця матриці (від 1 до ‘,m-1,’), куди потрібно’, ‘вставити новий стовпець:’);

read(j);

for i := 1 to n do move(a[i,j],a[i,j+1],(m-j)*2);

writeln(‘Введіть дані стовпця, що вставляється, з ',n,' цілих чисел:');

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

writeln(‘Матриця з включеним стовпцем:’);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j],’ ‘);

writeln;

end;

end.

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

Приклад програми:

const

n = 3; m = 3;

type massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k, l : integer;

x : integer; {допоміжна змінна}

begin

writeln(‘Введіть ‘,n,’X’,m,’=’,n*m,’ значень елементів матриці:’);

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

writeln(‘Введіть індекси i,j елемента, що переставляється:');

read(i,j);

writeln(‘Введіть індекси k,l елемента, що переставляється:');

read(k,l);

{перестановка заданих елементів}

x := a[i,j];

a[i,j] := a[k,l];

a[k,l] := x;

writeln(‘Матриця з переставленими елементами:’);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j],’ ‘);

writeln;

end;

end.

15. Перестановка рядків матриці виконується за допомогою допоміжної змінної.

Приклад програми:

const

n = 3; m = 3;

type massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k, x : integer;

begin

writeln(‘Введіть ‘,n,’X’,m,’=’,n*m,’ значень елементів матриці:’);

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

writeln(‘Введіть номер i-й рядка, що переставляється:');

read(i);

writeln(‘Введіть номер k-й рядка, що переставляється:');

read(k);

{перестановка рядків матриці}

for j := 1 to m do

begin

x := a[i,j];

a[i,j] := a[k,j];

a[k,j] := x;

end;

writeln(‘Матриця з переставленими ‘,i,’ і ‘,k,’ рядками:’);

for i := 1 to n do

begin

for j := 1 to m do write(a[i,j],’ ‘);

writeln;

end;

end.

20. Множення рядка матриці на число.

Приклад програми:

const

n = 3; m = 3;

type massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k : integer;

begin

writeln(‘Введіть ‘,n,’X’,m,’=’,n*m, ‘значень елементів матриці:’);

for i := 1 to n do

for j:= 1 to m do

read(a[i,j]);

writeln(‘Введіть номер i-го рядка:’);

read(i);

writeln(‘Введіть число K на яке потрібно ‘ ,

‘помножити рядок:’);

read(k);

{множення рядка на число}

for j:=1 to m do

begin

a[i,j]:=a[i,j]*k;

end;

writeln(‘матриця з рядком ‘,i,’,помноженим на ‘,k,’:’);

for i:=1 to n do

begin

for j:=1 to m do write(a[i,j],’ ’);

writeln;

end;

end.

21.Множення стовпця матриці на число. Приклад програми:

const

n = 3; m = 3;

type massiv=array[1..n,1..m] of integer;

var

a : massiv; i, j, k : integer;

begin

writeln(‘Введіть’,n,’X’,m,’=’,n*m,‘ значень елементів матриці:’);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

writeln(‘Введіть номер j-го стовпця:’);

read(j);

writeln(‘Введіть число K на яке потрібно помножити стовпець:’);

read(k);

for i:=1 to n do{множення стовпця на число}

begin

a[i,j]:=a[i,j]*k;

end;

writeln(‘матриця зі стовпцем ‘,j,’,помноженим на ‘,K,’:’);

for i:=1 to n do

begin

for j:=1 to m do write(a[i,j],’’);

writeln;

end;

end.

22.Додавання рядків матриці

Приклад програми:

const

n = 3; m = 3;

type massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k : integer;

begin

writeln(‘Введіть ‘,n,’X’,m,’=’,n*m, ‘ значень елементів матриці:’);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

writeln(‘Введіть номер i-го рядка:’);

read(i);

writeln(‘Введіть номер k-го рядка:’);

read(k);

{додавання рядків}

for j:=1 to m do a[i,j]:=a[i,j]+a[k,j];

writeln(‘матриця з рядком ‘,i,‘ , елементи якого є сумою ‘,

’рядків ‘,i,’та’,k,’:’);

for i:=1 to n do

begin

for j:=1 to m do write(a[i,j],’’);

writeln;

end;

end.

23.Додавання стовпців матриці.

Приклад програми:

const

n = 3; m = 3;

type massiv = array[1..n,1..m] of integer;

var

a : massiv; i, j, k : integer;

begin

writeln(‘Введіть’,n,’X’,m,’=’,n*m,‘ значень елементів матриці:’);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

writeln(‘Введіть номер j-го стовпця:’);

read(j);

writeln(‘Введіть номер k-го стовпця:’);

read(k);

{додавання стовпців}

for i:=1 to n do a[i,j]:=a[i,j]+a[i,k];

writeln(‘матриця зі стовпцем ‘,j,’, елементи якого є сумою’, ‘стовпців ‘,j,’та’,k,’:’);

for i:=1 to n do

begin

for j:=1 to m do write(a[i,j],’’);

writeln;

end;

end.

24. Перетворення матриці на вектор.

Швидкість обробки вектора набагато вище швидкості обробки матриці, тому часто приходяться елементи матриці пересилати у вектор того ж розміру. Наприклад, потрібно переслати елементи матриці A(nXm) у вектор B того ж розміру по рядках зі збереженням порядку проходження елементів. Приклад програми:

const

n = 3; m = 4;

type

matriza = array[1..n,1..m] of integer;

var

a : matriza; i, j : integer;

begin

writeln(‘Введіть матрицю розміром ‘,n,’X’,m,’:’);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

writeln(‘Виведення матриці, перетвореної у вектор:’);

write(‘вектор B(‘,n*m,’)=’);

for i:=1 to n do

for j:=1 to m do

write(a[i,j],’ ’);

end.