Мета уроку.* Навчити розробляти алгоритми пошуку в таблицях елементів із заданими властивостями.
Для організації пошуку в таблиці елементів із заданими властивостями слід організувати циклічний перегляд всіх елементів, кожний з яких командою розгалуження порівняти із заданим еталоном або перевірити на деяку властивість. Якщо масив одновимірний, цикл для організації перегляду всіх елементів буде один, якщо ж масив двовимірний—циклів буде два.
ЗАДАЧА № 302
Умова: Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від’ємними числами, а дівчаток — додатними у вигляді цілих значень а1 а2 .... аn? Крім того, у всіх дівчаток на голівках зав’язані бантики заввишки 10см, а висота паркану Н см.
Розв’язання: При розв’язанні цієї задачі, заповнюючи масив, необхідно генерувати як додатні, так від’ємні числа. Для пошуку в масиві елементів із заданою властивістю (в даному випадку чисел, що за модулем більші, ніж задане) використовується вже відома команда розгалуження.
Таким чином програма буде мати наступний вигляд:
Program Example_302;
Uses crt;
Var N,H:word;
{N — кількість дітей в дитсадочку, Н — висота паркану}
А:аггау[1..100] of longint;
{А — зарезервований масив для зберігання зросту дітей}
і,Count_girl,Count_boy:longint;
{і — змінна циклу, Count_girl — кількість дівчаток,
Countjboy — кількість хлопців}
Begin
Randomize;
Clrscr;
Count_girl:=0; Count_boy:=0;
Write(‘Введіть висоту паркану: ‘);
Readln(H);
Write(‘Введіть кількість дітей в дитсадочку: ‘);
Readln(N);
For i:=1 to N do
Begin
A[i]:=random(300)-150;
{Заповнення масиву випадковими числами від -150 до +150}
Write(А[і]:5) ;
{Виведення масиву на екран для контролю роботи програми}
if (A[i]<0) and (abs(A[i])>H) then Count_Boy: =Count_Boy+1;
if (A[i]>0) and (A[i]+10>H) then Count_Girl: =Count_Girl+1;
End;
Write(‘хлопчики, яких видно з-за паркану ‘,Count_Boy);
Write(‘дівчатка, яких видно з-за паркану ‘ ,Count_girl);
Readkey; {Затримка зображення на екрані}
End.
ЗАДАЧА №314(2)
Умова: Дано натуральне число п та послідовність дійсних чисел а1 а2 ...ап. Визначити кількість сусідств двох чисел різного знаку.
Розв ‘язання: Перш за все запропонуємо в цій задачі інший метод опису масиву з використанням константи, що задає розмір масиву, та вказівки Туре. А, по-друге, зверніть увагу, що для визначення двох сусідніх елементів масиву використовується загальний опис індексів і та і + 1 (можна і — 1 та і), а це при організації циклу можне викликати ситуацію виходу за межі масиву. Дійсно, якщо організувати цикл з параметром для зміни індексу від 1 до N, де N — кількість елементів масиву, то при і = N значення і + 1 буде виходити за межі масиву. Це є помилкою, що призводить до неочі-куваних результатів, тому цикл треба організовувати для зміни індексу не від 1 до N, а для зміни від 1 до N - 1.
Program Example_314_2;
Uses crt;
Const N=100;
Type Masiv = array[1..N] of real;
Var A:Masiv; {A — масив для зберігання даних чисел}
і,count:byte; {і — змінна циклу, count — кількість сусідств}
Begin
Randomize;
Clrscr;
count:=0;
For і:=1 to N do
Begin
A[i]:=random*100-random*50;
{Заповнення масиву випадковими дійсними числами}
Write(А[і]:8:2);
End;
For i:=l to N-l do
If ((A[i]<0) and (A[i+1]>0)) or ((A[i]>0) and (A[i+1]<0))
then count:=count+l;
Writeln;
Writeln(‘Кількість заданих сусідств ‘,count);
Readkey; {Затримка зображення на екрані}
End.
ЗАДАЧА № 321 (1,2)
Умова: Дано одновимірний масив цілих чисел A[i], де i = 1, 2, ..., п. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу.
Розв’язання: Для розв’язку цієї задачі спочатку необхідно пройти по всіх елементах масиву і знайти серед них максимальний, запам’ятавши його номер. Для цього користуються стандартним алгоритмом:
1) береться будь-який елемент масиву (як правило, перший) і його значення присвоюється змінній max, тобто він вважається за еталон найбільшого елементу;
2) по черзі з масиву вибираються всі останні елементи і, якщо серед них знайдеться більший за обраний еталон, то змінній max присвоюється нове значення, яке тепер буде новим еталоном. В іншій змінній, наприклад, Nmax запам’ятовується номер цього найбільшого елементу (початкове значення цієї змінної було 1, тому що спочатку ми вважали найбільшим 1 -ий елемент). Після закінчення перегляду всього масиву змінна max буде містити шуканий максимум, а змінна N_max — його номер. Щоб запам’ятати номер першого максимального елемента, необхідно шукати в матриці елемент, що точно більший еталону. Якщо ж ми будемо шукати елемент, що не менший за еталон, то в змінній Nmax залишиться номер останнього найбільшого елементу (подумайте чому).
Після знаходження максимуму другим проходом можна вже підрахувати кількість таких елементів в масиві. Для цього кожен елемент порівнюється з еталоном, що знаходиться в змінній max, та до лічильника count додається одиниця у випадку співпадання цих значень.
Програма, що реалізує описаний алгоритм, наведена нижче:
Program Example_321_1_2;
Uses crt;
Const n = 30;
Var A:array[1..n] of integer; {A — масив даних чисел}
і:byte; {і — змінна циклу}
count,N_max:byte; {count — кількість максимальних елементів в масиві, Н_тах — номер першого найбільшого елементу}
max:integer; {max — максимальний елемент масиву}
Begin
Clrscr;
Randomize;
For і:=1 to n do
Begin
A[i]:«random(150) - random(80); Write(A[i]:5);
end;
{Надання змінним початкових значень)
max:=A[l];
N_max:=1;
count:=0;
{Прохід по масиву для пошуку максимуму та його номера}
for і:=2 to n do
if A[i]> max
then begin max:=A[i]; N_max:=i; end;
{Другий прохід по масиву для підрахунку кількості максимальних елементів}
for i:=1 to n do
if A[i]= max then count:=count+1;
Writeln( Максимум = ‘ ,max);
Writeln(‘Номер першого максимума = ‘ ,N_max);
Writeln(‘Кількість максимумів = ‘,count);
Readkey;
End.
ЗАДАЧА № 356
Умова: Дано цілочислову прямокутну таблицю порядку п х т. Усі елементи таблиці, менші за середнє арифметичне її значень, замінити на «-1», а більші — на «1».
Розв ‘язання: Щоб виконати задану заміну, необхідно спочатку обчислити середнє арифметичне елементів таблиці. Для цього знайдемо суму всіх елементів, а потім поділимо на їх кількість (елементів у таблиці всього п х т). Після виконання зазначених обчислень необхідно ще раз організувати прохід по масиву, в результаті якого командою розгалуження вибрати додатні та від’ємні елементи і замінити їх відповідно до умови.
Program Example_356;
Uses crt;
Const n = 9; m = 12;
Type Masiv = array[1..n,l..m] of integer;
Var A:Masiv; i,j:byte; {i,j — змінні циклу}
Sum,SA:real;
{Sum — сума елементів таблиці, SA — середнє арифметичне}
Begin
Randomize;
Clrscr; Sum:=0; {Початкове значення суми}
Writeln(‘Вихідний масив: ‘);
For і: =1 to n do
Begin
For j : =1 to m do
begin
A[i,j]:=random(120)-random(65); Write(A[i,j]:5);
Sum:=Sum+A[і,j]; {Накопичення суми елементів масиву}
end;
writeln;
End;
SA:=Sum/(n*m);
Writeln(‘Середнє арифметичне - ‘,SA:8:2);
Writeln(‘Результуючий масив: ‘);
For i:=1 to n do
Begin
For j:=1 to m do
begin
if A[i,j] < SA then A[i,j]:=-1;
if A[i,j] > SA then A[i,j]:=1;
Write<A[i,j]:5);
end;
writeln;
End;
Readkey;
End.
ЗАДАЧА № 358
Умова: У даній дійсній матриці розмірністю 6x9 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент у матриці єдиний.
Розв’язання: Щоб знайти суму елементів заданого рядка, спочатку визначимо, в якому з рядків матриці знаходиться максимальний елемент. Після цього ми повинні запам’ятати номер рядка, в якому він знаходиться. Використаємо для цього додаткову змінну N_max. Після повного проходу по масиву з метою пошуку максимуму, організовуємо новий цикл, але вже не по всьому масиву, а тільки по рядку з номером Njnax для обчислення суми елементів цього рядка. Програма для реалізації описаного алгоритму має наступний вигляд:
Program Example_358;
Uses crt;
Type masiv = array[1..6,1..9] of real;
Var A: Masiv;
i,j:byte; {i,j - змінні циклу}
Sum,max:real;
{Sum — сума елементів таблиці, max — махе. елемент таблиці}
N_max:byte; {Njnax — номер рядка, що містить махс. елемент}
Begin
Randomize;
Clrscr;
Writeln(‘Вихідний масив: ‘);
Fox i:=1 to 6 do
Begin
For j:=1 to 9 do
begin
A[i,j]:=random*12-random(65)/ll; Write(A[i,j]:8:2);
end;
writeln;
End;
{Беремо у якості еталону перший елемент масиву}
mах:=А[1,1];
Nmax:=1; For i:=1 to 6 do
For j:=1 to 9 do
if A[i,j]>max then
Begin max:=A[i,j]; N_max:=i; End;
Writeln(‘Максимальний елемент масиву - ‘,max:8:2);
Sum:=0; {Початкове значення суми}
For j:=1 to n do
Sum: =Sum+A [ N_max, j ] ;
Writeln(*Отримана сума - ‘,Sum:8:2); Readkey;
End.
Домашнє завдання:
• Задачі № 314, № 321, № 350(2), № 353(1), № 355(2), № 360(1), № 361.