Аналіз завдання та розробка методу вирішення задач

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

Характеристика масиву:

· Розмірність — кількість індексів елемента (одновимірний, двовимірний, багатовимірний)

· Розмір — загальна кількість елементів у масиві.

· За типом поділяється на числовий та символьний.

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

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

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

Запам’ятайте, що у двовимірних масивах перший індекс завжди вказує на номер рядка, а другий – на номер стовпчика в цьому рядку!

Загальний вигляд опису масивів:

<ім’я змінної>: array [<межі зміни індексів>] of <тип>;

Наприклад:

Var

A: array [1..10] of real;

B: array [1..100,1..100] of byte;

C:array [1..100] of array [1..100] of byte.

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

оголошення масивів розміру n × n, де n = (k + g) mod 3+6, (k – номер студента в журналі групи, g − номер групи (1 або 2)).

const

k=22;

g=1;

n=9;

var

A:array[1..n, 1..n] of integer;

B:array[1..n] of integer;

Наступним етапом є введення елементів масиву – це процес одержання значень елементів масиву. Існує декілька варіантів організації введення масиву: з використанням генератора випадкових чисел, за формулою, з використанням компонентів Memo, StringGrid і т.д.

Виходячи з завдання курсової роботи ми вводили елементи масиву А(n n) генеруючи числа випадковим чином з проміжку [-10g, 10k].

For i:=1 to n do

For j:=1 to n do

A[i, j]:= RendomRange(-10g, 10k);

З масиву, що відповідає матриці А (n n) утворили одновимірний масив В розмірністю n елементи якого є сумою непарних елементів відповідного рядка:

For i:=1 to n do

Begin

S:=0;

For j:=1 to n do

if A[i, j] mod 2<>0 then S:=S+a[i, j];

B[i]:=S;

End;

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

Для використання елементів масиву необхідно вказати ім’я масиву та індекселемента.

Виконуючи завдання 2, що полягає у пошуку максимального по модулю елемента масиву серед выдэмних А (n n) використовуємо алгоритм простого перебору:

for i:=1 to n do

for j:=1 to n do

if(a[i,j]<0) and (max<abs(a[i,j]))then max:=abs(a[i,j]);

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

Наведемо приклад опрацювання елементів одновимірних масивів В та С розмірності n для виконання обчислень в₁с₁+ в₂с₂+…+в_nc_n:

S:=0;

For i:=1 to n do

S:=S+B[i]*C[i];

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

Сортування (sortіng) − процес, що дозволяє впорядкувати безліч подібних даних у зростаючому або спадаючому порядку.

Алгоритми сортування добре досліджені і вивчені. Хоча деякі методи в середньому можуть бути краще інших, жоден з методів не буде ідеальним

для всіх ситуацій, тому кожен програміст повинен мати у своєму

розпоряджені кілька різних типів сортування. Можна виділити кілька типів які використовуються найчастіше: метод сортування вибором, метод сортування обміном, метод сортування вставки.

Один з найпростіших методів сортування працює наступним чином: знаходимо найменший елемент в масиві і обмінюємо його з елементом знаходяться на першому місці. Потім повторюємо процес з другої позиції у файлі і знайдений елемент обмінюємо з другим елементному і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором, оскільки він працює, циклічно вибираючи найменший з елементів, що залишилися, як показано на малюнку 1. При першому проході символ пропуску йде на перше місце, обмінюючись з буквою 'П'. На другому проході елемент 'В' обмінюється з елементом 'Р' і так далі.

Наступна програма дає повну реалізацію цього процесу. Для кожного i від 1 до N-1, вона обмінює найменший елемент з a [i.. N] з a [i]:

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

Цей метод - один з найпростіших, і він працює дуже добре для невеликих файлів. Його «внутрішній цикл» складається з порівняння a [i] <a [min] (плюс код необхідний для збільшення j та перевірки на те, що він не перевищив N), що навряд чи можна ще спростити.

Крім того, хоча сортування вибором є методом «грубої сили», він має дуже важливе застосування: оскільки кожен елемент пересувається не більше ніж раз, то він дуже гарний для великих записів з маленькими ключами.

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

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

Цей процес реалізований в наступній програмі. Для кожного i від 2 до N, подмассів a [1.. i] сортується за допомогою приміщення a [i] у відповідну позицію серед уже відсортованих елементів:

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

Проте є ще одна важлива деталь: програма insertion не завжди працює, оскільки while може проскочити за лівий край масиву, коли v - найменший елемент масиву. Щоб виправити ситуацію, ми поміщаємо «сторожовий» ключ в a [0], роблячи його, по крайней мере, не більше, ніж найменший ключ масиву. Сторожові елементи повсюдно використовуються в ситуаціях подібних до цієї для запобігання додаткової перевірки (у даному випадку j> 0), що майже завжди допомагає у внутрішніх циклах.

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

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

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

Наведемо приклад як сортується одновимірний масив методом вставки та двох вимірний масив методом обміну.

Сортування одновимірного масиву методом вставки:

for i:=1 to n-1 do

begin

m_in:=i;

for j:=i+1 to n do

if c[j]<c[m_in] then m_in:=j;

t:=c[i];

c[i]:=c[m_in];

c[m_in]:=t;

end;

Сортування двовимірного масиву методом обмінного сортування:

for k:=1 to n do

for i:=1 to n-1 do

if Y[i]>Y[i+1]then

begin

t:=Y[i];

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

Y[i+1]:=t;

for j:=1 to n do

begin

t:=D[i,j];

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

D[i+1,j]:=t;

end;

Під виведенням розуміють вивід на екран монітора (у діалогове вікно) значень елементів масиву. Для даного процесу зазвичай використовують компоненту Memo та StringGrid.

У нашому випадку - виведення елементів одно та двовимірного масиву використовуючи компоненту StringGrid.

Одновимірний масив:

for i:=1 to n do

В[i]:=StrToInt(StringGrid1.Cells[0,i-1]);

Двовимірний масив:

for i:=1 to n do

for j:=1 to n do

StringGrid1.Cells[j,i]:=IntToStr(A[i,j]);
3 Опис структури программного проекту

procedure TForm1.N31Click(Sender: TObject);

begin

for i:=1 to n do

for j:=1 to n do

if(a[i,j]<0) and (max<abs(a[i,j]))then max:=abs(a[i,j]); ]); // Знаходження максимального по модулю елемента серед відємних.

edit1.Text:='Максимальний по модулю елемент серед відємних -'+IntToStr(max);

label3.caption:='В двовимірному масиві,що відповідає матриці A,'

+#13+ 'Максимальний по модулю елемент серед відємних'

end;

procedure TForm1.N41Click(Sender: TObject);

var

s:integer;

begin

for j:=1 to n do

begin

s:=1;

for i:=1 to n do

if A[i,j] mod 2=0 then

s:=s*A[i,j];

b[j]:=s;

StringGrid2.Cells[j-1,0]:=IntToStr(b[j]); //Виведення відсортоваго масиву

label3.caption:='З масиву, що відповідає матриці А утворити одновимірний масив В '

+#13+'B[i] є добутком парних елементів і-го стовпців:';

end;

end;

procedure TForm1.N51Click(Sender: TObject);

var

t:integer;

m_in:integer;

begin

for i:=1 to n do

c[i]:=b[i];

for i:=1 to n-1 do// Сортування масиву С

begin

Сортування масиву С

m_in:=i;

for j:=i+1 to n do

if c[j]<c[m_in] then m_in:=j;

t:=c[i];

c[i]:=c[m_in];

c[m_in]:=t;

end;

for i:=1 to n do

StringGrid3.Cells[i-1,0]:=IntToStr(c[i]); //Виведення відсортоваго масиву

Label3.Caption:='Відсортувати одновимірний масив В за методом вибору.'

+#13+'Результатом сортування - масив С.';

end;

procedure TForm1.N21Click(Sender: TObject);

begin

for i:=1 to n do

for j:=1 to n do

begin

A[i,j]:=RandomRange(-10,10*k);

StringGrid1.Cells[j-1,i-1]:=IntToStr(a[i,j]);

label3.caption:='Задано квадратну матрицю А розміром n*n, де n=(k+g) mod 3+6,'

+#13+'(k-номер студента в журналі групи, g-номер групи (1 або 2)).'

+#13+'матрицz заповнюються випадковим чином з проміжку [-10g,10k]';

end;

end;

procedure TForm1.N61Click(Sender: TObject);

var

S:real;

begin

S:=0;

for i:=1 to n do

begin

S:=S+cos(C[n-i+1]-B[i]);

edit2.text:=FloatToStr(S);

label3.caption:='Використовуючи елементи масивів В та С, виконати обчислення '

+#13+'';

image1.Visible:=true;

end;

end;

procedure TForm1.N71Click(Sender: TObject);

var

s,min,t,k:integer;

begin

//Обчислюємо характеристику стовпців матриці а

for i:=1 to n do

begin

s:=0;

for j:=1 to n do

if a[i,j] mod 2 <> 0 then

begin

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

x[i]:=s;

StringGrid4.Cells[0,i-1]:=IntToStr(x[i]);

end;

image1.Visible:=false;

end;

for i:=1 to n do

begin

//копія массиву x

y[i]:=x[i];

StringGrid6.Cells[0,i-1]:=IntToStr(x[i]);

end;

for i:=1 to n do

for j:=1 to n do

begin

d[i,j]:=a[i,j]; //копія массиву A

StringGrid5.Cells[j-1,i-1]:=IntToStr(d[i,j]);

label3.caption:='Відсортувати матрицю методом бульбашок'

end;

begin

for k:=1 to n do// Сортування масиву методом "Обміного сортування "

for i:=1 to n-1 do

if Y[i]>Y[i+1]then

begin

t:=Y[i];

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

Y[i+1]:=t;

for j:=1 to n do

begin

t:=D[i,j];

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

D[i+1,j]:=t;

end;

end;

for i:=1 to n do

StringGrid6.Cells[0,i-1]:=IntToStr(y[i]); //Виведення відсортованої характеристики

for i:=1 to n do

for j:=1 to n do

StringGrid5.Cells[j-1,i-1]:=IntToStr(d[i,j]); //Виведення відсортованого масиву

Label2.Caption:=('Завдання 6.'+#13+'Сортування масиву методом "Обміного сортування".');

end;

end;

procedure TForm1.N1Click(Sender: TObject);

begin

close;

end;

procedure TForm1.N72Click(Sender: TObject);

begin

for i:=1 to n do

begin

St:=' ';

for j:=1 to n do

St:=St+#9+IntToStr(A[i,j]); // Виведення матриці А в поле memo1.

Memo1.lines.add(st)

end;

Memo1.Lines.SaveToFile('A.txt'); // Виведення матриці А з поля memo в текстовий документ.

for i:=1 to n do

begin

St:=' ';

St:=St+#9+IntToStr(B[i]);

Memo2.lines.add(st)

end;

Memo2.Lines.SaveToFile('B.txt');

for i:=1 to n do

begin

St:=' ';

St:=St+#9+IntToStr(C[i]);

Memo3.lines.add(st)

end;

Memo3.Lines.SaveToFile('C.txt');

for i:=1 to n do

begin

St:=' ';

St:=St+#9+IntToStr(X[i]);

Memo4.lines.add(st)

end;

Memo4.Lines.SaveToFile('X.txt');

for i:=1 to n do

begin

St:=' ';

for j:=1 to n do

St:=St+#9+IntToStr(d[i,j]);

Memo5.lines.add(st)

end;

Memo5.Lines.SaveToFile('d.txt');

label3.caption:='Збереження масивів';

end;

end.

Дата добавления: 2015-11-04