Федеральне агенство з освіти
ГОУ ВПО Тульський державний педагогічний
університет ім. Л.М. Толстого
Курсова робота
"Масиви у мові Паскаль"
Виконала
студентка 3 курсу
групи Б, ф-ту МФіІ
Дікшева О.А.
Перевірила
Торіна
Тула 2009
Зміст
Введення
1. Види масивів
1.1. Одновимірні масиви
1.2. Приклади завдань
1.3. Двовимірні масиви
1.4. Приклади завдань
2. Сортування масивів
2.1Метод простих обмінів (Бульбашкова сортування)
2.2. Сортування простим вибором
2.3 Сортування простим включенням (Метод вставки і зсуву)
3. Параметри-масиви і параметри-рядки
Список літератури
Введення
Існують різні типи даних в мові Паскаль. Розглянемо похідні типи. Кожне значення будь-якого з цих типів в загальному випадку являє собою вже нетривіальну структуру, тобто звичайно це значення має більш ніж одну компоненту. При цьому кожна компонента структури може бути як окремими даними, так і в свою чергу нетривіальною структурою, тобто, значенням будь-якого з похідних типів. Таким чином, значення похідних типів в загальному випадку мають ієрархічну структуру, на самому нижньому рівні якої фігурують тільки окремі дані. Цим компонентам нижнього рівня можуть присвоюватися значення і вони можуть бути присутніми у виразах, як і значення змінних скалярного типу. Дані, які є значеннями скалярних типів, займають порівняно мало місця в пам'яті ЕОМ. Окрема літера, наприклад, зазвичай представляється одним байтом (8 двійкових розрядів). Для чисел різні типів в залежності від реалізації відводять більше байт. Дані ж, складові значення похідного типу, зазвичай займають значний обсяг пам'яті ЕОМ. У зв'язку з цим при написанні програм для ЕОМ, що мають порівняно невеликий обсяг пам'яті, постає проблема економного її використання. У паскалі передбачена можливість вказівки транслятору на необхідність економного представлення значень похідних типів. Для цього завдання похідного типу необхідно почати зі службового слова packed, що означає упакований. Але ввівши вимога на упакованості даних, необхідно чітко уявляти собі, що, з одного боку, це вимога не завжди може бути виконано транслятором (якщо, наприклад, більш економного уявлення, ніж звичайне неупаковані подання для даних цього типу, в ЕОМ просто не існує) . А з іншого боку, якщо воно здійснимо, то призводить до збільшення часу виконання програми. Пояснимо на прикладі, за рахунок чого це відбувається. Як вже зазначалося раніше, одна літера займає один байт. Машинна комірка пам'яті, з якою працюють команди ЕОМ, в загальному випадку складається з декількох байтів. Тому, якщо у клітинку помістити одну літеру, го більша її частина не буде використана. Насправді в одну клітинку можна помістити кілька літер (упаковане подання). Але тоді кожен раз, коли необхідно виконати дію над окремою літерою, доведеться виробляти виділення цієї літери з комірки (розпакування літери з комірки). Аналогічно, під час запису окремої літери в пам'ять машини доведеться визначати те місце в комірці, куди її необхідно помістити, і заносити літеру саме туди, не змінюючи вміст інших розрядів (Запаковування літери в клітинку). Такі додаткові дії можуть займати значну частину загального часу роботи програми. Тому приймати рішення про використання упакованого подання даних повинен завжди програміст, в залежності від конкретних умов і цілей, які він переслідує. Отже, значення похідних типів можуть бути представлені в пам'яті ЕОМ в упакованому і не упакованому вигляді. Упаковане уявлення вимагає, взагалі кажучи, меншого обсягу пам'яті, але уповільнює процес виконання програми. Ми розглянемо найбільш уживаний похідний тип, а саме регулярний тип. Значення регулярного типу зазвичай називають масивом. Отже, масив - це впорядкований набір фіксованої кількості деяких значень (компонент масиву). Всі компоненти повинні бути одного і того ж типу, який називають типом компонент або базовим (для масиву) типом.
Тип даних Масив дозволяє одному ідентифікатору задати кілька значень, які відрізняються порядковим номером. Номер елемента масиву вказується після ідентифікатора в квадратних дужках {M [5] - п'ятий елемент масиву М}. При описі масиву вказується діапазон номерів елементів масиву і тип, до якого відноситься кожен його елемент. Масиви можуть бути одно-, двох-і багатовимірними.
Рис. Зображення одно-, дво-і тривимірних масивів.
Приклад опису та заповнення елементів масиву.
Var {опис масивів}
M: array [1 .. 5] of integer; {одновимірний масив М з номерами елементів від 1 до 5, що складається з цілих чисел}
M1: array [2 .. 3,11 .. 15] of char; {двовимірний масив М1 з номерами рядків від 2 до 3, з номерами стовпців від 11 до 15, що складається з символів}
Begin {заповнення масиву}
М [2]: = 100; {другого елементу чисельного масиву М присвоєно значення 100}
М1 [2,3]: = 'd'; {елементу другого рядка і третього стовпця символьного двомірного масиву М1 присвоєно значення 'd'}
End.
1. Види масивів
1.1 Одновимірні масиви
Кожному використовуваному в програмі конкретного масиву має бути дано своє ім'я. Це ім'я будемо називати повною змінної, оскільки її значення є весь масив. Кожна компонента масиву може бути явно позначена шляхом зазначення імені масиву, за яким слід селектор компоненти - узятий в квадратні дужки індекс, що задає правило обчислення номера потрібної частини. Ця відмінність від звичної запису індексу в математиці, коли він вказується праворуч в нижній позиції, пояснюється необхідністю використання лінійної запису програми, так що багаторівнева запис повинна бути виключена. При посиланні на компоненти масиву індекс записується на одному рівні з ім'ям і полягає у квадратні дужки. Таким чином, для посилання на окремі компоненти використовується запис виду (ім'я масиву) [<індекс>] яку будемо називати часткової змінної (оскільки її значенням є не весь масив, а окрема його компонента, номер якої задається індексом) - стосовно до масивів вона називається змінної з індексом. У нашому прикладі масив отримає ім'я v, а посилання на окремі його компоненти виробляються за допомогою часткових змінних v [1], v [2], ..., v [1ОО]. У загальному випадку в якості індексу може, бути використано вираз, значення якого і визначає номер компоненти масиву. При цьому важливо, що в індексне вираз можуть входити змінні, так що при зміні їх значень змінюється і значення індексу, яке визначає номер компоненти масиву. Таким чином, одна й та ж змінна з індексом в процесі виконання програми може позначати різні компоненти масиву. Тип значення індексного виразу називають типом індексу. Безліч значень типу індексу перенумерується безліччю, тим самим визначаючи кількість компонентів і їх впорядкованість. При завданні регулярного типу окрім типу індексу необхідно задати тип компонент. Завдання такого регулярного типу, як одновимірний масив, тобто вектор, має вигляд:
аrrау [(тип індексу)] оf <тип компонент>, де <тип компонент> - ім'я чи завдання типу.
1.2 Приклади завдань
Завдання 1. Дан лінійний масив цілих чисел. Підрахувати, скільки в ньому різних чисел.
{Підрахунок кількості різних чисел у лінійному масиві}.
ІДЕЯ РІШЕННЯ: заводимо допоміжний масив, елементами
якого є логічні величини (False - якщо елемент
вже зустрічався раніше, True - інакше)}
Program Razlichnye_Elementy;
Var I, N, K, Kol: Integer;
A: Array [1 .. 50] Of Integer;
Lo: Array [1 .. 50] Of Boolean;
Begin
Write ('Введіть кількість елементів масиву:'); ReadLn (N);
FOR I: = 1 TO N DO
Begin
Write ('A [', I,']='); ReadLn (A [I]);
Lo [I]: = True; {Заповнюємо допоміжний масив значеннями True}
End;
Kol: = 0; {змінна, в якій буде зберігатися кількість різних чисел}
FOR I: = 1 TO N DO
IF Lo [I] THEN
Begin
Kol: = Kol + 1;
FOR K: = I TO N DO
{У допоміжний масив заносимо значення False,
якщо число вже зустрічалося раніше або збігається з поточним елементом A [I]}
Lo [K]: = (A [K] <> A [I]) And Lo [K];
End;
WriteLn ('Кількість різних чисел:', Kol)
END.
Тест: N = 10; елементи масиву - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3. Відповідь: 6.
Завдання 2. Дан лінійний масив. Упорядкувати його елементи в порядку зростання.
{Сортування масиву вибором (у порядку зростання)}.
Ідея рішення: нехай частина масиву (з K-й елемент включно)
відсортована. Потрібно знайти в невідсортованої частині масиву
мінімальний елемент і поміняти місцями з (K +1)-м}
Program Sortirovka;
Var N, I, J, K, Pr: Integer; A: Array [1 .. 30] Of Integer;
Begin
Write ('Введіть кількість елементів:'); ReadLn (N);
For I: = 1 To N Do
Begin
Write ('Введіть A [', I, ']'); Readln (A [I]);
End;
WriteLn;
For I: = 1 To N - 1 Do
Begin
K: = I;
For J: = I + 1 To N Do If A [J] <= A [K] Then K: = J;
Pr: = A [I]; A [I]: = A [K]; A [K]: = Pr;
End;
For I: = 1 To N Do Write (A [I], '');
End.
Тест: N = 10; елементи масиву - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3.
Відповідь: -1, -1, 0, 1, 2, 2, 2, 3, 3, 34.
1.3 Двовимірні масиви
Двовимірний масив (прямокутна таблиця (матриця, набір векторів)) - це приклад масиву, в якому елементи нумеруються двома індексами.
Як номер (індексу) елемента масиву використовується вираз порядкового типу (частіше integer).
Двовимірним масивом називається таблиця, що складається з рядків і стовпців. Для опису масиву використовуються два індекси.
А11 А12 А13 ... А1m
A21 A22 A23 ... А2m
... ... ... ... ...
... ... ... ... ...
... ... ... ... ...
An1 An2 An3 ... Anm
Опис масиву
Спосіб 1. У розділі опису змінних
var
ІмяМассіва: array [Верх.Гр.1 .. Ніж.Гр.1, Верх.Гр.2 .. Ніж.Гр.2] of ТіпЕлементов;
Спосіб 2. У розділі опису типів
ІмяМассіва: array [Верх.Гр.1 .. Ніж.Гр.1, Верх.Гр.2 .. Ніж.Гр.2] of ТіпЕлементов;
Спосіб 3. У розділі опису констант
const
ІмяМассіва: array [1 .. 3,1 .. 3] of real = ((1.2,2.4,0.4), (0.045, -0.47,0.003), (1.24,1, -7.4));
Заповнення масиву даними (введення елементів)
Масив, описаний як типизированная константа, вже містить дані. Масиви, оголошені в розділі опису змінних, необхідно заповнити даними, перш ніж виконувати з ними будь-які дії.
Значення елементів масиву також можна задати наступним чином: при введенні даних з клавіатури:
write ('Введіть кількість рядків і стовпців');
readln (n, m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j ,']='); {Можна цю строчку в програмі не використовувати}
readln (a [i, j]);
end;
за допомогою датчика випадкових чисел:
randomize;
writeln ('Введіть кількість елементів масиву');
readln (n);
for i: = 1 to n do
begin
a [i]: = random (50);
writeln ('a [', i ,',', j ,']=', a [i, j]);
end;
прісваеніем заданих значень (наприклад за формулою i * i / i +2):
writeln ('Введіть кількість елементів масиву');
readln (n);
for i: = 1 to n do
begin
a [i]: = i * i / i +2;
writeln ('a [', i ,',', j ,']=', a [i, j]);
end;
Виведення масиву
висновок у стовпчик:
for i: = 1 to n do
writeln (a [i, j]);
по рядках і стовпцях:
for i: = 1 to n do
begin
for j: = 1 to m do
begin
write (a [i, j]: 3);
end;
readln;
end;
Обробка масивів
Часто потрібно обчислити суму елементів масиву, їх середнє арифметичне значення або знайти значення і номери максимального і мінімального елементів, а також змінити значення елементів масиву і т.д. Особливість роботи з двовимірними масивами полягає в тому, що розширюється можливість обробки масиву (з'явилися нові елементи: рядки, стовпці - є одновимірними масивами). Детально всі дії можна розглянути в задачах розібраних у цьому розділі.
Квадратна матриця
Квадратної називається така матриця, в якій кількість рядків дорівнює кількості стовпців. Виділяють наступні елементи квадратної матриці:
головна діагональ;
побічна діагональ;
елементи, розташовані вище головної діагоналі;
елементи, розташовані нижче головної діагоналі;
елементи, розташовані вище побічної діагоналі;
елементи, розташовані нижче побічної діагоналі;
Головна діагональ. Якщо значення індексів (i, j) елемента рівні, то елементи розташовані на головній діагоналі.
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
if i = j then <інструкції>
Побічна діагональ. Якщо для значень індексів (i, j) елементів виконується рівність: i + j = n +1, то елементи розташовані на побічної діагоналі.
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
if i + j = n +1 then <інструкції>
Для елементів, розташованих вище головної діагоналі необхідно використовувати один з наступних фрагментів програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 1 to n do
for j: = 1 to n do
if i <j then <інструкції>
for i: = 1 to n-1 do
for j: = i +1 to n do
<Інструкції>
Якщо елементи розташовані на головній діагоналі і вище її необхідно використовувати наступний фрагмент програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 1 to n do
for j: = 1 to n do
if i <= j then <інструкції>
Для елементів, розташованих нижче головної діагоналі необхідно використовувати наступний фрагмент програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 1 to n do
for j: = 1 to n do
if i> j then <інструкції>
Для елементів, розташованих нижче головної діагоналі і не ній необхідно використовувати наступний фрагмент програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 1 to n do
for j: = 1 to n do
if i> = j then <інструкції>
Якщо елементи, розташовані вище побічної діагоналі, то необхідно використовувати наступний фрагмент програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 1 to n-1 do
for j: = 1 to n-1 do
if i + j <= n then <інструкції>
Якщо елементи, розташовані нижче побічної діагоналі, то необхідно використовувати наступний фрагмент програми:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i: = 2 to n do
for j: = 2 to n-1 do
if i + j> n +1 then <інструкції>
Транспонування матриці.
Транспонованої матрицею називається матриця, у якої стовпці відповідають рядкам вихідної квадратної матриці. При цьому елементи головної діагоналі вихідної і транспонованої матриць, одні й ті ж.
Операція транспонування зводиться до обміну елементів матриці, розташованих симетрично головної діагоналі.
Вихідна матриця
Транспонована матриця
1
5
9
13
1
2
3
4
Фрагмент програми транспонування матриці:
for i: = 1 to n do {Перегляд всіх рядків матриці}
for j: = i +1 to n do {Перегляд всіх елементів у рядку, розташованих вище за головну діагональ}
begin
k: = a [i, j];
a [i, j]: = a [j, i];
a [j, i]: = k;
end;
1.4 Приклади завдань
1. Знайти суму всіх елементів деякого двовимірного масиву і порівняти їх з твором елементів деякої рядка.
program zadacha_1;
uses crt;
var
a: array [1 .. 50,1 .. 50] of integer; {масив}
i, j: integer; {змінні лічильники}
n, m: integer; {кількість рядків і стовпців масиву}
s: integer; {сума елементів масиву}
p: integer; {твір елементів деякої рядка}
q: integer; {деяка рядок}
begin
clrscr;
write ('Введіть кількість рядків:');
readln (n);
write ('Введіть кількість стовпців:');
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j ,']=');
readln (a [i, j]);
end;
writeln ('Матриця:');
for i: = 1 to n do
begin
for j: = 1 to m do
begin
write (a [i, j]: 3);
end;
readln;
end;
for i: = 1 to n do
for j: = 1 to m do
begin
s: = s + a [i, j];
end;
write ('Введіть номер рядка для роботи:');
readln (q);
p: = 1;
for j: = 1 to m do
begin
p: = p * a [q, j];
end;
writeln ('Сума елементів матриці:', s);
writeln ('Добуток елементів рядка', q, 'дорівнює', p);
if s> p then
begin
writeln ('Сума більше твору');
end
else
begin
writeln ('Твір більше твору');
end;
readln;
end.
2.Поменять другий стовпець матриці з передостаннім.
program zadacha_2;
uses crt;
var
a: array [1 .. 50,1 .. 50] of integer;
b: array [1 .. 50,1 .. 50] of integer;
m, n, i, j: integer;
begin
clrscr;
writeln ('Кількість рядків');
readln (n);
writeln ('Кількість стовпців');
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j ,']=');
readln (a [i, j]);
end;
writeln ('Вихідна матриця:');
for i: = 1 to n do begin
for j: = 1 to m do
write (a [i, j]);
writeln;
end;
for i: = 1 to n do begin
for j: = 1 to m do
b [i, j]: = a [i, j];
end;
for i: = 1 to n do begin
a [i, 2]: = b [i, m-1];
end;
for i: = 1 to n do begin
a [i, m-1]: = b [i, 2];
end;
writeln ('Отримана матриця:');
for i: = 1 to n do begin
for j: = 1 to m do
write (a [i, j]);
writeln;
end;
readln;
end.
3.Дана матриця розмірності m * n. Розташувати елементи останнього стовпця за спаданням.
program zadacha_3;
uses crt;
var
a: array [1 .. 50] of integer;
b: array [1 .. 50] of integer;
k, i, m, j, n, r, l: integer;
begin
clrscr;
write ('Введіть кількість рядків');
readln (n);
write ('Введіть кількість стовпців');
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,']={ b [', j ,']=}');
readln (a [i]);
end;
for i: = 1 to n-1 do
for k: = i +1 to n do
{For j: = 1 to m do}
if a [k]> a [i] then
begin
r: = a [i];
a [i]: = a [k];
a [k]: = r;
end;
writeln ('Отсортірований масив:');
for i: = 1 to n do
writeln (a [i]: 4);
readln;
end.
4. Дана квадратна матриця. Транспонувати її. Порахувати суму всіх непарних елементів транспонованої матриці.
program zadacha_4;
uses crt;
var
a: array [1 .. 5,1 .. 5] of integer;
S, i, j, n, c: integer;
begin
clrscr;
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
for j: = i +1 to n do
begin
c: = a [i, j];
a [i, j]: = a [j, i];
a [j, i]: = c;
end;
S: = 0;
for j: = 1 to n do
for i: = 1 to n do
begin
if a [j, i] mod 2 <> 0 then
begin
S: = S + a [j, i];
end;
end;
writeln ('S =', S);
readln;
end.
5. Дан двовимірний масив. Порахувати суму його двох стовпців, вивести велику суму.
program zadacha_5
uses crt;
var
a: array [1 .. 3,1 .. 3] of integer;
i, j, m, n, s, s1, p, p1, max, p3: integer;
begin
clrscr;
write ('введіть кількість рядків');
readln (n);
write ('введіть кількість стовпців');
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j ,']=');
readln (a [i, j]);
end;
begin
write ('введіть номер стовпця');
readln (p);
for i: = 1 to n do
for j: = 1 to m do
if j = p then s: = s + a [i, p];
write ('s =', s);
readln;
end;
s1: = 0;
begin
write ('введіть номер іншого стовпця');
readln (p1);
for i: = 1 to n do
for j: = 1 to m do
if j = p1 then s1: = s1 + a [i, p1];
write ('s1 =', s1);
readln;
end;
begin
max: = s;
if s <s1 then
begin
max: = s1;
write ('максимальна сума', max);
readln;
write ('вивести на екран номер стовпця більшої суми', p3);
readln (p3);
end;
end;
end.
end.
6. Заповнити матрицю за зразком:
0
0
0
0
program zadacha_6;
uses crt;
var
a: array [1 .. 50,1 .. 50] of integer;
n: integer;
i, j, k: integer;
begin
clrscr;
write ('Введіть кількість рядків і стовпців в матриці');
readln (n);
k: = 0;
for i: = 1 to n do
for j: = 1 to n do
if i = j then
begin
a [i, j]: = k;
k: = k +1;
end
else
begin
a [i, j]: = 0;
end;
for i: = 1 to n do
for j: = 1 to n do
begin
writeln ('a [', i ,',', j ,']=', a [i, j]);
readln;
end;
readln; end.
7. Дана квадратна матриця порядку N. У матриці обчислити середнє арифметичне позитивних елементів, що стоять на головній діагоналі
program zadacha_7;
uses crt;
Var
a: array [1 .. 50,1 .. 50] of integer; {масив}
i, j: integer;
s, n, k: integer;
sr: real;
begin
clrscr;
write ('введіть кількість рядків');
readln (n);
write ('введіть кол-во стовпців');
readln (n);
write ('введіть кол-во чисел');
readln (k);
for i: = 1 to n do
for j: = 1 to n do
begin
write ('a [', i ,',', j ,']=');
readln (a [i, j]);
end;
s: = 0;
begin
for i: = 1 to n do
for j: = 1 to n do
if a [i, j]> 0 then
s: = s + a [i, j];
sr: = s / n;
end;
write ('sr =', sr);
readln;
end.
8. Знайти суму всіх елементів квадратної матриці, розташованих по головній діагоналі і вище її.
program zadacha_8;
uses crt;
var
a: array [1 .. 30,1 .. 30] of integer;
i, j, s, n: integer;
begin
clrscr;
writeln ('введіть кількість рядків і стовпців:');
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
for j: = i +1 to n do
begin
if j> = i then
begin
s: = s + a [i, j];
end;
end;
writeln ('s =', s);
readln;
end.
9. Дана речова матриця розмірності n * m. Видалити k стовпець матриці.
program zadacha_9;
uses crt;
var
a: array [1 .. 100,1 .. 100] of real;
b: array [1 .. 100,1 .. 100] of real;
i, j: integer; {змінні лічильники}
n, m: integer; {кількість рядків і стовпців у масиві}
k: integer; {№ рядка яку необхідно видалити}
begin
clrscr;
write ('Введіть кількість рядків у масиві');
readln (n);
write ('введіть кількість стовпців у масиві');
readln (m);
write ('Введіть № рядка яку треба видалити');
readln (k);
randomize; {введення масиву випадкових чисел}
for i: = 1 to n do
for j: = 1 to m do
begin
a [i, j]: = random (100);
end;
for i: = 1 to n do
for j: = 1 to m do
begin
writeln ('a [', i ,',', j ,']=', a [i, j]);
end;
writeln ('Новий масив');
for i: = 1 to n do
for j: = 1 to m do
begin
if j <> k then
{Перевірка умови № стовпця
неравен № стовпця,
який необходімоудаліть}
begin
b [i, j]: = a [i, j];
{Якщо так, то новому масиву
присвоюємо перевіряється елемент}
end;
end;
for i: = 1 to n do {висновок нового масиву}
for j: = 1 to m do
writeln ('b [', i ,',', j ,']=', b [i, j]);
readln;
end.
10. Дана речова матриця розмірності n * m. Вивести номери стовпців, які містять лише негативні елементи.
program zadacha_10;
uses crt;
var
a: array [1 .. 50,1 .. 50] of real;
i, j: integer;
n, m: integer;
begin
clrscr;
write ('введіть кількість рядків');
readln (n);
write ('введіть кол-во стовпців');
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j, '] =');
readln (a [i, j]);
end;
for j: = 1 to m do
begin
if a [i, j] <0 then
begin
writeln ('номер стовпця, в якому всі елементи негативні =', J);
readln;
end
else
begin
writeln ('у стовпці', J, 'немає негативних або не
всі негативні елементи ");
end;
end;
readln;
end.
11. У двовимірному масиві знайти мінімальне число і визначити в якому рядку і якому стовпці він знаходиться.
program zadacha_11;
uses crt;
var
a: array [1 .. 50,1 .. 50] of integer; {опис масива}
i, j: integer; {змінні-лічильники}
min: real; {мінімальне число}
n, m: integer; {кількість рядків, кількість стовпців}
begin {початок програми}
clrscr;
write ('введіть кількість рядків'); {введення запланованого рядків}
readln (n);
write ('введіть кол-во стовпців'); {введення запланованого стовпців}
readln (m);
for i: = 1 to n do
for j: = 1 to m do
begin
write ('a [', i ,',', j, '] ='); {введення елементів масиву}
readln (a [i, j]);
end;
min: = a [1,1];
for i: = 1 to n do
for j: = 1 to m do
begin
if a [i, j] <min then {пошук мінімального числа}
min: = a [i, j];
end;
for i: = 1 to n do
for j: = 1 to m do
begin
if a [i, j] = min then
begin
writeln ('мінімальне число =', min: 5);
{Висновок мінімального числа}
writeln ('номер елемента i =', i ,',',' j = ', j);
{Висновок номери хв. чис-ла}
end;
end;
readln;
end.
12. Розгорнути квадратну матрицю на 90 градусів за годинниковою стрілкою.
program zadacha_12;
uses crt;
var
a: array [1 .. 30,1 .. 30] of integer; {вихідна матриця}
b: array [1 .. 30,1 .. 30] of integer; {проміжна матриця}
c: array [1 .. 30,1 .. 30] of integer; {Матриця розгорнута на 90?}
i, j: integer; {змінні лічильники}
m, n: integer; {кількість рядків і стовпців}
begin
clrscr;
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
for j: = 1 to n do
begin
b [i, j]: = a [n +1- i, j]; {проміжної матриці присвоюємо
елементи первісної матриці за законом: першого елемента
присвоюємо рядка останній, останньому першому, другому
елементу передостанній, передостанньому другий і тд.}
end;
writeln ('Матриця розгорнута на 90 ?.');
for i: = 1 to n do
for j: = 1 to n do
begin
c [i, j]: = b [j, i]; {третій матриці присвоюємо
елементи проміжної за законом: перший рядок
стає першим стовпцем і тд. }
writeln ('c [', i ,',', j ,']=', c [i, j]); {друк масиву розгорнутого на 90?}
readln;
end;
end.
2. Сортування масивів
Завдання сортування (впорядкування) елементів масиву у відповідності з їх значеннями відноситься до класу класичних завдань, які вирішувалися ще на перших е-mail-ах.
В даний час розроблено досить багато різних методів сортування. Одні з них відносяться до методів простих сортувань. Інші до поліпшеним. Проте до сьогоднішнього моменту задача розробки методу, поєднував би в собі всі кращі якості залишається відкритою. Домовимося, що лінійний масив, який необхідно впорядкувати вже задано, тобто описаний і згенерований.
Розрізняють такі типи сортувань:
1) за зростанням
2) за спаданням
3) по не зменьшенням
4) по не зростанням
При розгляді кожного методу будемо сортувати елементи за неспадання.
2.1 Метод простих обмінів (Бульбашкова сортування)
Ідея методу: Весь масив розглядається кілька разів, причому при кожному розгляді порівнюються значення 2-х сусідніх елементів. Якщо вони стоять в неправильному порядку, то проводиться їх перестановка. Так відбувається до тих пір, поки не буде виконано жодної перестановки. Метод називають бульбашкової сортуванням тому що менші значення елементів поступово "спливають", як пузирчики повітря у воді, переміщаючись в початок масиву, а "важкі" елементи "осідають на дно".
7 0 -4 3 1 -2 5
-4 7 0 -2 3 1 5
-4 -2 7 0 1 3 5
-4 -2 0 7 1 3 5
-4 -2 0 1 7 3 5
-4 -2 0 1 3 7 5
-4 -2 0 1 3 5 5
Фрагмент:
For i: = 2 to n do
For j: = n downto i do
if v [j] <v [j-1] then
begin
x: = v [j];
v [j]: = v [j-1];
v [j-1]: = x;
end;
2.2 Сортування простим вибором
Ідея методу: весь масив проглядається кілька разів і на кожному кроці шукається мінімальний елемент і запам'ятовується його порядковий номер. Потім знайдений мінімальний елемент змінюється значенням з першим, другим, третім і т.д. передостаннім елементом масиву і виключається з розгляду
7 0 -4 3 1 -2 5
-4 0 7 3 1 -2 5
-4 -2 7 3 1 0 5
-4 -2 0 3 1 7 5
-4 -2 0 1 3 7 5
-4 -2 0 1 3 5 7
For i: = to n do
Begin
min: = v [i];
ind: = i;
for j: = i to n-1 do
if v [j] <min then
bedin
min: = v [j];
ind: = j;
end;
x: = v [i];
v [i]: = v [ind];
v [ind]: = x;
end;
2.3 Сортування простим включенням (Метод вставки ісдвіга)
Ідея методу: робиться припущення, що перші р елементів масиву вже впорядковані і розглядається р +1 елемент. Якщо виявиться, що він менше ніж який або з перших р, то він займає місце більшого, а ділянка масиву обмежений його новим місцем і старим зміщується в право.
7 0 -4 3 1 -2 5
0 7 -4 3 1 -2 5
-4 0 7 3 1 -2 5
-4 0 3 7 1 -2 5
-4 0 1 3 7 -2 5
-4 -2 0 1 3 7 5
-4 -2 0 1 3 5 7
For i: = 2 to n do
For j: = 1 to i-1 do
if v [i] <v [j] then
begin
x: = v [i];
for h: = 1 downto j +1 do
v [h]: = i [h-1];
v [j]: = x;
end.
3. Параметри - масиви і параметри - рядки
Може скластися враження, що оголошення змінних в списку формальних параметрів підпрограми нічим не відрізняється від оголошення їх у розділі опису змінних. Дійсно, в обох випадках багато спільного, але є одна істотна відмінність: типом будь-якого параметра в списку формальних параметрів може бути тільки стандартний або раніше оголошений тип. Тому не можна, наприклад, оголосити наступну процедуру:
Procedure S (a: array [1 .. 10] of Real);
тому що в списку формальних параметрів фактично оголошується тип-діапазон, що вказує межі індексів масиву.
Якщо ми хочемо передати якийсь елемент масиву, то проблем, як правило, не виникає, але якщо в підпрограму передається весь масив, то слід спочатку описати його тип. Наприклад:
type
atype = array [1 .. 10] of Real;
Procedure S (a: atype);
Оскільки рядок є фактично своєрідним масивом, її передача в підпрограму здійснюється аналогічним чином:
type
intype = String [15];
outype = String [30];
Function St (s: intype): outype;
Вимога описати будь-який тип-масив або тип-рядок перед оголошенням підпрограми на перший погляд здається несуттєвим. Дійсно, в рамках найпростіших обчислювальних завдань зазвичай заздалегідь відома структура всіх використовуваних в програмі даних, тому статичний опис масивів не викликає проблем. Проте розробка програмних засобів універсального призначення пов'язана зі значними труднощами. По суті, мова йде про те, що в Турбо Паскалі неможливо використовувати в підпрограма масиви з "плаваючими" кордонами зміни індексів. Наприклад, якщо розроблена програма, обробна матрицю 10х10 елементів, то для обробки матриці 9x11 елементів необхідно перевизначити тип, тобто перекомпілювати всю програму (мова йде не про динамічному розміщенні масивів в купі, а про статичному описі масивів та передачі їх як параметрів у підпрограми). Цей недолік, як і відсутність в мові засобів обробки виняткових ситуацій (переривань), успадкований з стандартного Паскаля і являє собою об'єкт постійної і цілком заслуженою його критики. Розробники Турбо Паскаля не ризикнули кардинально змінити властивості базової мови, але, тим не менш, включили в нього деякі засоби, що дозволяють до певної міри пом'якшити відмічені недостаткі.Еті недоліки практично повністю усунені в мові Object Pascal, використовуваному у візуальному середовищі програмування Delphi.
Перш за все, в середовищі Турбо Паскаля можна встановити режим компіляції, при якому відключається контроль за збігом довжини фактичного і формального параметра-рядка (див. дод.1). Це дозволяє легко вирішити питання про передачу підпрограмі рядки довільної довжини. При передачі рядка меншого розміру формальний параметр буде мати ту ж довжину, що й параметр звернення; передача рядка більшого розміру призведе до її усікання до максимального розміру формального параметра. Слід сказати, що контроль включається тільки при передачі рядки, оголошеної як формальний параметр-змінна. Якщо, відповідний параметр оголошений параметром-значенням, ця опція ігнорується і довжина не контролюється.
Значно складніше йде справа з передачею масивів довільної довжини. Найбільш універсальним прийомом в цьому випадку буде, судячи з усього, робота з покажчиками і використання індексного арифметики. Трохи простіше можна вирішити цю проблему за допомогою нетипізовані параметрів (див. п.8.5). У версії Турбо Паскаля 7.0 мову підтримує так звані відкриті масиви, легко вирішують проблему передачі підпрограмі одновимірних масивів змінної довжини.
Відкритий масив являє собою формальний параметр підпрограми, що описує базовий тип елементів масиву, але не визначає його розмірності та межі:
Procedure MyProc (OpenArray: array of Integer);
Усередині підпрограми такий параметр трактується як одновимірний масив з нульовою нижньою межею. Верхня межа відкритого масиву повертається функцією HIGH, згадуваної в п.4.1.1. Використовуючи 0 як мінімальний індекс і значення, що повертається функцією HIGH, як максимальний індекс, підпрограма може обробляти одномірні масиви довільної довжини:
{Ілюстрація використання відкритих масивів: програма виводить на екран вміст двох одновимірних масивів різної довжини за допомогою однієї процедури ArrayPrint}
Procedure ArrayPrint (aArray: array of Integer);
var
k: Integer;
begin
for k: = 0 to High (aArray) do
Write (aArray [k]: 8);
WriteLn
end;
const
A: array [-1 .. 2] of Integer = (0,1,2,3);
B: array [5 .. 7] of Integer = (4,5,6);
begin
ArrayPrint (A);
ArrayPrint (B)
end.
Як видно з цього прикладу, фактичні межі масивів А і В, переданих в якості параметрів виклику процедурі ArrayPrint, не мають значення. Однак розмірність відкритих масивів (кількість індексів) завжди дорівнює 1 - за цим стежить компілятор. Якщо б, наприклад, ми додали в програму двовимірний масив З
var
З: array [1 .. 3,1 .. 5] of Integer;
то звернення
ArrayPrint (С)
викликало б повідомлення про помилку
Error26: Type mismatch.
(Помилка 26: Невідповідність типів.)
Список літератури
1.Пільщіков В.М. Збірник вправ з мови Паскаль: Учеб. посібник для вузов.-М.: Наука, 1989.-160с.
2. Семашко Г.Л., Салтиков А.І. Програмування на мові Паскаль. М.: Наука 1988.-128с.
3. Введення в мову Паскалью. / Абрамов В.Г. Трифонов Н.П. Трифонова Г.М. Учеб. посібник .- М.: Наука 1988.-320с.
4.Могілев А.В. Практикум з інф-ке. Навчальний посібник для студентів уч. Закладів \ Могилів А.В., Пак Н.І., Хеннер Є.К., М.: Академія, 2001.-608с.