Додаток 1
Оформлення сторінки тексту
Номер сторінки
25мм
10мм
25мм
297мм
Умовні позначення елементів блок-схем
(згідно з ГОСТ 19.003
15мм
210мм
Додаток 2
Умовні позначення елементів блок-схем (згідно з ГОСТ 19.003-80)
Позначення |
Найменування |
|
Пуск-зупин(початок-кінець) |
|
Процес (дія) |
|
Розв’язок(умова) |
|
Модифікація(зациклювання) |
|
Зумовлений процес(процедура, модуль) |
|
Ввід-вивід |
|
З’єднувач |
|
Міжсторінковий з’єднувач |
|
Лінія потоку |
|
Паралельні дії |
|
Коментар |
|
Транспортування носіїв(інформаційний потік) |
|
Ручна операція |
|
Допоміжна операція |
|
Документ |
|
Файл |
|
Магнітний диск |
|
Дисплей |
Додаток 6
Приклад розв'язування задачі з обробки масиву
1 Умова задачі
Згідно із заданою квадратною матрицею n×n побудувати вектор, елементи якого - максимуми елементів діагоналей, паралельних головній діагоналі.
2 Аналіз задачі
Вихідними даними задачі є двовимірний масив з n рядками та n стовпцями. Нехай елементи масиву є будь-які дійсні числа. Число п буде задаватись у процесі виконання задачі, але не перевищуватиме значення деякої константи Кn=10. Масив розмірністю n×n має 2n-1 діагоналей. Тому результатом є одновимірний масив розмірністю 2n-1. Якщо вважати n<=10, то розмірність вихідного (результуючого) масиву повинна бути меншою чи рівною 19. У процесі розв'язування задачі необхідно послідовно проглядати елементи діагоналі, щоб визначити більший з них. Наприклад, у матриці А розмірністю 10 × 10 одна з діагоналей складається з таких елементів: а31 , а42 , а53 , a64 , а75 , а86 , а97 , а108 .Індекси кожного наступного елемента діагоналі збільшуються на одиницю. Останній з них має значення одного з індексів, що дорівнює n. В останнього елемента головної діагоналі обидва індекси дорівнюють n. Проглянемо діагоналі, починаючи знизу вверх, відносно головної діагоналі. Індекси перших елементів діагоналей до головної діагоналі: n,1; n-1,1; n-2,1; ...; 3,1; 2,1; 1,1. Індекси перших елементів діагоналей, вище головної: 1,2; 1,3; 1,4;...; 1,n-2; 1,n-1; 1,n.
Таким чином, для формування індексів першого елемента діагоналі необхідно знати положення її відносно головної діагоналі (знаходиться вона вище чи нижче неї). Індекси головної діагоналі рівні. Тому при перегляді діагоналей можна зафіксувати момент проходження через головну діагональ.
3 Розробка алгоритму
Алгоритм розробляємо за допомогою спадного проектування. Спочатку ( вводимо матрицю АМ[n×n] з клавіатури. Далі копіюємо її в результуючий файл (до нього ж будемо заносити і результати всіх подальших обчислень). Для індикації діагоналей матриці (паралельних головній) вводимо дві булевські змінні: Rav (яка набуває значення True, якщо індекси стали рівними) та Kon (набуває значення True, якщо вибрано останній елемент матриці); початкове значення цих змінних False.
Перегляд діагоналей матриці здійснюємо, починаючи з лівого нижнього кута, тому задаємо значення індексів Кі:=n; Kj:= 1. Далі в циклі for виконуємо послідовний виклик допоміжних алгоритмів:
- побудови одновимірного вектор-масиву діагональних елементів;
- занесення у файл вихідних даних побудованого масиву;
- пошуку максимального елемента у вектор-масиві;
- переходу на наступну діагональ.
Після завершення циклу for виводимо результуючий масив, у якому, знаходяться максимальні елементи діагоналей.
3.1 Допоміжні алгоритми
3.1.1 Допоміжний алгоритм побудови одновимірного вектор-масиву діагональних елементів
Індекси першого елемента діагоналі Кі, Kj одержуємо з основного, алгоритму: Доти поки не вичерпаються елементи цієї діагоналі, k-му елементу вектор-масиву діагональних елементів AV присвоюємо значення ij-го елемента масиву AM.
3.1.2 Допоміжний алгоритм занесення у файл вихідних даних побудованого масиву
З основного алгоритму одержуємо вектор-масив діагональних елементів та кількість елементів у цьому масиві. Доки не вичерпані всі елементи масиву АV, ми друкуємо їх у файл вихідних даних, по п'ять елементів у рядку.
3.1.3 Допоміжний алгоритм пошуку максимального елемент у вектор-масиві
Допоміжній змінній Maxd присвоюємо значення першого елемента вектор-масиву діагональних елементів. Далі в циклі від 2 до максимальної кількості елементів цього масиву порівнюємо Maxd та і-й елемент масиву AV. Якщо і-й елемент більше Maxd, останній стає рівним AV[i]. Значення максимального елемента після закінчення циклу присвоюється змінній Мах.
3.1.4 Допоміжний алгоритм переходу на наступну діагональ
Якщо не вибрано останній елемент матриці AM (Kon=false), аналізуємо значення Rav При Rav-false (це не головна діагональ) перехід до наступної діагоналі здійснюється переходом на перший елемент рядка, розташованого вище даного, a Rav не змінюється, доки не доберемось до головної діагоналі.
Якщо Raw-true, тобто ми на головній діагоналі, перехід до наступної діагоналі здійснюється таким чином: беремо елемент, який .знаходиться у першому рядку відповідного стовпця. Слідкуємо, щоб не вийти за межі масиву за допомогою зміни Коn.
4 Розробка програми
4.1 Загальна специфікація та розділ опису програми
Кількість рядків та кількість стовпців вихідної матриці AM можуть знаходитись у межах від 1 до Кп. Введемо тип Index=1..Kn. Тоді вихідний масив AM буде Array [Index,Index] of real. Оскільки ми задали Кn<=10, то кількість елементів вихідного масиву MaxVec не повинна перевищувати 19. Введемо тип IndVec=1..19; тоді вихідний масив можна подати як Array [IndVec] of real. Масив АV буде складатись з елементів вибраної діагоналі матриці AM.
Змінні Кі та Kj будуть визначати індекси першого елемента діагоналі, змінна КМах - біжучий індекс вихідного масиву MaxVec.
Розділ опису програми матиме такий вигляд:
Program MaxDia;
Const Kn-10;
Type
Index= 1..Kn;
IndVec=1..19;
Vector=Array [IndVec] of real;
Matrix=Array [Index,Index] of real;
Var
Ki,Kj,n:Index;
i,j,KMax,KolVec:lndVec;
AM:Matrix;
AV,MaxVec:Vector;
B:real;
Rav,Kan:boolean;
Namef:string;
f1:text;
4.2 Подання даних
Const Kn-10; - константа максимальної кількості рядків та стовпців вихідного масиву.
Вводимо такі типи змінних:
Index=1..Kn;
IndVec=1..19;
Matrix=Array (Index,Index] of real;
Vector=Array[IndVec] of real;
Змінні
Ki,Kj - індекси першого елемента діагоналі;
n - кількість рядків та стовпців вихідної матриці ;
КМах - індекс масиву MaxVec;
KolVec - кількість елементів у діагоналі масиву AV;
AV - одновимірний масив елементів діагоналі;
AM - двовимірний масив;
MaxVec- одновимірний масив максимальних елементів діагоналей матриці АМ;
Rav - змінна типу Boolean, що набуває значення True при Ki=Kj;
Коп - змінна тішу Boolean, що набуває значення True, коли вибрано останній елемент матриці AM;
Namef - повне ім'я результуючого файла;
f1 - логічне ім'я результуючого файла;
i,j,b - допоміжні змінні.
У результаті розв'язання задачі видається:
- вихідна матриця AM;
- масив. Діагональних елементів AV;
- масив максимальних елементів діагоналей MaxVec.
4.3 Опис програми
Введення матриці здійснюється процедурою VVODM; копіювання у файл процедурою VYVODM; побудова масиву діагональних елементів процедурою DIAGON, параметри, що передаються програмі: BV - побудований масив і Kb - кількість елементів в цьому масиві. Процедура використовує значення глобальних змінних Кі і Kj.
Для визначення максимального елемента масиву AV використовується функція МАХ, до якої передаються вектор-масив діагональних елементів BV та кількість елементів у ньому. Функція набуває значення найбільшого елемента заданого масиву.
Для визначення індексів першого елемента наступної діагоналі використовується процедура USTIND, яка також встановлює значення змінної Rav, що дорівнює True при Ki=Kj. Значення змінної Кoп встановлюється True, якщо вибрана остання діагональ матриці AM
Для виведення одновимірного масиву використовується процедура VYVVEC; параметрами, що передаються, є масив BV i кількість елементів масиву Kb. Процедура здійснює виведення по п'ять чисел у форматі 7:2.
Основна програма здійснює виклик відповідних процедур згідно з алгоритмом. Початкове значення змінних Rav i Коп – False.
5 Набір тестів для налагодження
n=5;
Вихідна матриця :
48 22 14 46 25
30 19 3 43 18
13 22 9 45 11
48 22 20 5 23
37 27 30 24 2
У результаті роботи програми повинні одержати:
Діагоналі матриці:
37
48 27
13 22 30
30 22 20 24
48 19 9 5 2
22 3 45 23
14 43 11
46 18
25
Масив максимальних елементів діагоналей:
37 48 30 30 48
45 43 46 25
Для другого тесту введемо матрицю 10×10. Діагоналі матриці повинні виводитись по п'ять елементів у рядку,
Повний текст програми наведений у додатку 10, а результати розрахунків по двом тестовим завданням відповідно у додатках 11 та 12.
Лістинг програми розв'язування задачі
{Програма будує, вектор MaxVec, елементи якого дорівнюють максимальним елементам діагоналей квадратної матриці п×п}
Const Кn=10;
Туре
Index=1..Kn;
IndVec=1..20,
Vector =Array[lndVec] of real;
Matrlx=Array[Index,Index] of real;
Var
Ki,Kj {індекси першого елемента діагоналі },
n:Index;
і, J, КМах {індекс результуючого вектора MaxVec},
KolVec {кількість елементів у векторі An) :IndVec;
AV {вектор оброблюваної діагоналі}, MaxVec:Vector;
AM {вихідна квадратна матриця} :Matrix;
В :геаl;
Rav {набуває значення True, якщо індекси стали рівними},
Коn {набуває значення True, якщо вибрано останній елемент матриці}:Вооlеаn;
namef: string; {повне ім'я результуючого файла}
f1: Text; {файл для виведення результатів}
Procedure VVODM;
var i,j:Index;
Begin
for i:=1 to n do
for j:=1 to n do
read (AM[i,j])
End;
Procedure VYVVEC (BV:Vector; Kb:IndVec);
var i,j:IndVec;
Begin
i:=1;
While i<=Kb do
Begin
writeln(f1);
j:=1;
Repeat
write(fl,BV[i]:7:2);
i:=i+1; j:=j+1;
until (j>5) or (i>Kb)
End;
writeln(fl)
End;
Procedure VVVODM;
var i,j:Index;
Begin
for i:=l to N do
Begin
for j:=l to n do
write (fl,AM[i,j]:7:2);
writeln(fl)
End
End;
Procedure DIAGON (var BV:Vector; Kb:JndVec);
var i,j:IndVec;
Begin
Kb:=l; i:=Ki; j:=Kj;
While (i<=n) and (J<=n) do
Begin
BV[Kb]:=AM[i,j];
i:=i+l;j:=j+l; Кb:=Кb+1
End;
Kb:=Kb-l
End;
Function MAX (var BV:vector, Kb:IndVec):real;
var i:Index; Maxd:real;
Begin
Maxd:=BV[l];
For i:=2 to Kb do
if Maxd<BV[і] then Maxd:=BV[і];
Max:=Maxd
End;
Procedure USTIND;
Begin
if not Kon
then
if not Rav
then
Begin
Ki:=Ki-1;
Rav:=(Ki=Kj);
End
else
Begin
Ki:=1;
Kj:=Kj+1;
Kon:=(Kj=n)
End
End;
{Основна програма}
BEGIN
Writeln (' Введіть повне ім'я результуючого файла ’);
Read (namef);
Assign(fl, namef);
Rewrite(f1);
Wrіtеln(' Введіть значення n<=1, kn div 2);
Read(n);
Writeln(‘ Введіть матрицю ', n, '*', n);
VVODM;
Writeln(fl, '******* Результати виконання програми ******');
Writeln(fl);
Writeln(ft, ' Вихідна матриця :');
Writeln(fl);
VYVODM;
Writeln(fl, ' Діагоналі матриці: ');
Writeln(fl);
Kon:=false;
Rav:=false;
Ki:=n;
KJ:=1;
for KMax:=l to (n*2-l) do
Begin
DIAGON (AV,KolVec);
VYVVEC (AV,KolVec);
MaxVec[KMax]:=MAX(AV,KolVec);
USTIND
End;
Writeln(f1);
Writeln(f1, ' Масив максимальних елементів діагоналей:');
VYVVEC (MaxVec,n*2-l);
Writeln(fl);
Writeln(fl,’************************************’);
Close(fl)
END.
Результати тестування 1 (матриця 5x5)
*************Результати виконання програми************
Вихідна матриця :
48.00 22.00 14.00 46.00 25.00
30.00 19.00 3.00 43.00 18.00
13.00 22.00 9.00 45.00 11.00
48.00 22.00 20.00 5.00 23.00
37.00 27.00 30.00 24.00 2.00
Діагоналі матриці:
37.00
48.00 27.00
13.00 22.00 30.00
30.00 22.00 20.00 24.00
48.00 19.00 9.00 5.00 2.00
22.00 3.00 45.00 23.00
14.00 43.00 11.00
46.00 18.00
25.00
Масив максимальних елементів діагоналей:
37.00 48.00 30.00 30.00 48.00
45.00 43.00 46.00 25.00