Тема уроку: "Алгоритми пошуку в таблицях елементів із деякою властивістю"

Мета уроку: Навчити розробляти алгоритми пошуку в таблицях елементів із заданими властивостями.
Тип уроку: Лекційний з практичними прикладами.

Для організації пошуку в таблиці елементів із заданими властивостями необхідно організувати циклічний перегляд всіх елементів, кожний з яких командою розгалуження порівняти із заданим еталоном або перевірити на деяку властивість. Якщо масив одновимірний, цикл для організації перегляду всіх елементів буде один, якщо ж масив двовимірний - циклів буде два.
Задача №314 (2).
Умова: Дано натуральне число n та послідовність дійсних чисел a1, a2, … an. Визначити в цій послідовності кількість сусідств двох чисел різного знаку.
Перш за все запропонуємо в цій задачі інший метод опису масиву з використанням константи, що задає розмір масиву, та вказівки Type. А, по-друге, звертаємо вашу увагу на те, що для визначення двох сусідніх елементів масиву використовується загальний опис індексів i та i+1 (можна і-1 та і), а це при організації циклу можне викликати ситуацію виходу за межі масиву. Дійсно, якщо організувати цикл з параметром для зміни індексу від 1 до N, де N - кількість елементів масиву, то при i=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 - масив для зберігання даних  
                    чисел}

          i,count:byte; {і - змінна циклу, count - кількість  
                                    сусідств} 
Begin 
  Randomize;  
  Clrscr; 
  count:=0; 
 For i:=1 to N do 
   Begin 
    A[i]:=random*100-random*50; {Заповнення масиву  
                                 випадковими дійсними числами} 
   Write(A[i]:8:2); {Виведення масиву на екран  
                     для контролю правильності  
                     роботи програми} 
   End; 
     For i:=1 to N-1 do 
      Begin 
        If (A[I]<0) and (A[I+1]>0) or  
           (A[I]>0) and (A[I+1]<0) 
        then count:=count+1; 
     End; 
   Writeln; 
   Writeln('Кількість заданих сусідств ',count); 
   Readkey; {Затримка зображення на екрані} 
End. 

Задача №321(1,2).
Умова: Дано одновимірний масив цілих чисел A[і], де і =1,2,…,n. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу.
Для розв'язку цієї задачі спочатку необхідно пройти по всіх елементах масиву і знайти серед них максимальний, запам'ятавши його номер. Для цього користуються стандартним алгоритмом, що полягає в наступному:
1) береться будь-який елемент масиву (як правило, перший) і його значення присвоюється змінній max, тобто він вважається за еталон найбільшого елементу;
2) по черзі з масиву вибираються всі останні елементи і, якщо серед них знайдеться більший за вибраний еталон, то змінній max присвоюється нове значення, яке тепер буде новим еталоном. В іншій змінній, наприклад, N_max запам'ятовується номер цього найбільшого елементу (початкове значення цієї змінної було 1, тому що спочатку ми вважали найбільшим 1-ий елемент).
Після закінчення перегляду всього масиву змінна max буде містити шуканий максимум, а змінна N_max - його номер. Щоб запам'ятати номер першого максимального елемента, необхідно шукати в матриці елемент, що точно більше еталону. Якщо ж ми будемо шукати елемент, що не менший за еталон, то в змінній N_max залишиться номер останнього найбільшого елементу (подумайте чому).
Після знаходження максимуму другим проходом можна вже підрахувати кількість таких елементів в масиві. Для цього кожен елемент порівнюється з еталоном, що знаходиться в змінній max, та до лічильника count додається одиниця у випадку співпадання цих значень.
Програма, що реалізує описаний алгоритм, наведена нижче:

Program Example_321_1_2; 
 Uses crt; 
 Const n = 30; 
Var A:array[1..n] of integer; {A - масив даних  
                               чисел} 
    i:byte; {і - зміннa циклу} 
    count,N_max:byte; {count - кількість  
                      максимальних елементів в  
                      масиві, N_max - номер першого  
                      найбільшого елементу} 
    max:integer; {max - максимальний елемент  
                 масиву} 
Begin 
 Clrscr; 
 Randomize; 
 {Заповнення масиву випадковими числами та  
 виведення його на екран для контролю за  
 роботою програми} 
For i:=1 to n do 
  Begin 
      A[i]:=random(150) - random(80); 
  Write(A[i]:5); 
 end;  
 {Надання змінним початкових значень} 
  max:=A[1]; 
  N_max:=1; 
 count:=0; 
{Прохід по масиву для пошуку максимуму та його  
номеру} 
for i:=1 to n do 
 begin 
   if A[i]> max 
  then 
     begin 
        max:=A[i]; 
        N_max:=i; 
     end; 
end; 
   {Другий прохід по масиву для підрахунку кількості  
   максимальних елементів} 
 for i:=1 to n do 
begin 
  if A[i]= max 
  then count:=count+1; 
end; 
 Writeln('Максимум = ',max);  
 Writeln('Номер першого максимума = ',N_max);  
 Writeln('Кількість максимумів = ',count);  
 Readkey; {Затримка зображення на екрані} 
End. 

Задача №350(1).
Умова: Дано натуральне число n. Визначити кількість додатних та від'ємних елементів таблиці aij, де i,j = 1,2,…,n, якщо: Aij = sin(i+j).
Візьмемо дві змінних count_plus та count_minus для зберігання кількості додатних та від'ємних елементів масиву відповідно .
На початку програми в даній задачі необхідно заповнити масив за законом, що заданий в умові. А після обчислення елементу масиву можна перевірити, являється він додатнім чи від'ємним і в залежності від результату перевірки додати одиницю до однієї чи другої змінної.
Програма, що реалізує запропонований алгоритм, наведена нижче:

 Program Example_350_1;  
  Uses crt; 
 Const n = 8; 
 Type 
   Masiv = array[1..n,1..n] of real; 
     Var A:Masiv; {A - масив для зберігання даних  
                   чисел} 
      i,j:byte; {і,j - змінні циклу} 
count_plus,count_minus:word; 
Begin 
  Clrscr; 
  count_plus:=0; 
  count_minus:=0; 
For i:=1 to n do 
 Begin 
   For j:=1 to n do 
    begin 
       A[i,j]:=sin(i+j); {Заповнення масиву} 
       Write(A[i,j]:8:2); {Виведення на екран} 
    If A[I,j] > 0 
        Then count_plus: = count_plus + 1; 
    If A[I,j] < 0 
        Then count_minus: = count_minus + 1; 
      end;  
     writeln; 
End; 
   Writeln('Кількість додатних елементів масиву - ',count_plus);  
   Writeln('Кількість від'ємних елементів масиву - ',count_minus);  
   Readkey; {Затримка зображення на екрані} 
End. 

Задача №352.
Умова: Дано квадратну дійсну матрицю порядку n. Усі максимальні елементи матриці замінити нулями.
В даній задачі спочатку необхідно визначити, який елемент матриці є максимальним. Для цього використовується алгоритм, що наведений вище. Єдина різниця полягає в тому, що в цій задачі масив двовимірний і тому циклів для проходу по ньому буде два. Після цього другим проходом по масиву ми будемо порівнювати елементи зі знайденим значенням максимуму і, якщо елементи будуть дорівнювати значенню max, вони будуть замінюватись на нуль. Програма для розв'язку описаного алгоритму має наступний вигляд:

Program Example_352; 
Uses crt; 
   Const n = 10; 
Type 
  Masiv = array[1..n,1..n] of real; 

Var   A : Masiv; {A - масив для зберігання даних чисел} 
    i,j : byte; {і,j - змінні циклу} 
    max : real; {max - максимальний елемент масиву} 
Begin 
 Randomize;  
 Clrscr; 
For i:=1 to n do 
 Begin 
    For j:=1 to n do 
 begin 
A[i,j]:=random(120)/3-random*20; 
  Write(A[i,j]:8:2);  
 end;  
 writeln; 
End; 
max:=A[1,1]; {Беремо у якості еталону перший  
елемент масиву} 
  For i:=1 to n do 
    For j:=1 to n do 
  begin 
     if A[i,j]>max then Max:=A[i,j]; 
             {Порівнюємо кожен елемент масиву з еталоном  
              і, якщо черговий елемент більший за еталон, переприсвоюємо еталон} 
  end;  
End; 
 Writeln('Максимальний елемент масиву - ',max:8:2); 
 Writeln('Перетворена матриця: '); 
For i:=1 to n do 
 begin 
   For j:=1 to n do 
     begin 
         if A[i,j]=max then A[i,j]:=0; 
          {Шукаємо максимуми в масиві і, знайшовши,присвоюємо їм нуль} 
         write(a[i,j]:8:2); 
    end;  
 writeln; 
 end;  
 End; 
 Readkey; {Затримка зображення на екрані}

 End. 

Задача №355_1.
Умова: Дано квадратну дійсну таблицю розмірності n. Обчислити кількість входжень даного елемента.
В даній задачі необхідно крім масиву чисел ввести (або задати якимось іншим шляхом) значення шуканого елементу. Тоді алгоритм підрахунку кількості цих елементів зводиться до організації порівняння кожного елемента масиву з шуканим значенням. У випадку співпадання обох виконується підрахунок кількості стандартним способом: Count:=count+1;
де count - лічильник, що зберігає кількість знайдених чисел.

Program Example_355_1; 
Uses crt; 
Const n = 10; 
Type 
Masiv = array[1..n,1..n] of real; 
Var A:Masiv;  
i,j:byte; {і,j - змінні циклу} 
x:real; {x - шуканий елемент} 
count:word; {count - кількість входжень} 
Begin 
Randomize;  
Clrscr; 
Write('Введіть шуканий елемент: '); 
Readln(x); 
Count:=0; {Початок обрахунку} 
For i:=1 to n do 
Begin 
For j:=1 to n do 
begin 
A[i,j]:=random*120-random*80; 
Write(A[i,j]:8:2);  
If A[i,j]=x 
Then count:=count+1;  
end;  
writeln; 
End; 
Writeln('Кількість шуканих елементів - ',count); 
Readkey; {Затримка зображення на екрані} 
End. 

Задача №356.
Умова: Дано цілочислову прямокутну таблицю порядку n х m. Усі елементи таблиці, менші за середнє арифметичне її значень, замінити на "-1", а більші - на "1".
Щоб виконати задану заміну, необхідно на початку програми обчислити середнє арифметичне елементів таблиці. Для цього потрібно знайти суму всіх елементів, а потім поділити на їх кількість (елементів в таблиці всього n*m). Після виконання зазначених обчислень необхідно ще раз організувати прохід по масиву, в результаті якого командою розгалуження вибрати додатні та від'ємні елементи і замінити їх згідно з умовою задачі.

Program Example_356; 
 Uses crt; 
 Const n = 9; 
       m = 12; 
 Type 
      Masiv = array[1..n,1..m] of integer; 
 Var A : Masiv;  
   i,j : byte; {і,j - змінні циклу} 
Sum,SA : real; {Sum - сума елементів таблиці, SA - середнє арифметичне} 
 Begin 
    Randomize;  
    Clrscr; 
    Sum:=0; {Початкове значення суми} 
    Writeln('Вихідний масив: '); 
 For i:=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[i,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.
Умова: У даній дійсній матриці розмірністю 6 х 9 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент в матриці єдиний.
Щоб знайти суму елементів заданого рядка, спочатку необхідно визначити, в якому з рядків матриці знаходиться максимальний елемент. Тому, визначивши, який з елементів є найбільшим, ми повинні ще запам'ятати номер рядка, в якому він знаходиться. Використаємо для цього додаткову змінну N_max. Після повного проходу по масиву з метою пошуку максимуму, організовуємо новий цикл, але вже не по всьому масиву, а тільки по рядку з номером N_max для обчислення суми елементів цього рядка.
Програма для реалізації описаного алгоритму має наступний вигляд:

Program Example_358; 
  Uses crt; 
 Type 
  Masiv = array[1..6,1..9] of real; 
 Var  A:Masiv;  
    i,j:byte; {і,j - змінні циклу} 
    Sum,max:real; {Sum - сума елементів таблиці,  
    max - максимальний елемент  
    таблиці} 
    N_max:byte; {N_max - номер рядка, що  
    містить максимальний елемент} 
Begin 
  Randomize;  
  Clrscr; 
 Writeln('Вихідний масив: '); 
   For i:=1 to 6 do 
Begin 
   For j:=1 to 9 do 
  begin 
   A[i,j]:=random*12-random(65)/11; 
   Write(A[i,j]:8:2);  
  end;  
  writeln; 
End; 
  max:=A[1,1]; {Беремо у якості еталону перший  
  елемент масиву} 
  N_max:=1; 
  For i:=1 to 6 do 
    For j:=1 to 9 do 
     Begin 
       if A[i,j]>max  
            then  
               Begin  
                  max:=A[i,j]; 
                  N_max:=i; 
               End; 
   End; 
     Writeln('Максимальний елемент масиву - ',max:8:2); 
     Sum:=0; {Початкове значення суми} 
     For j:=1 to n do 
       Begin 
         Sum:=Sum+A[N_max,j]; 
       End; 
     Writeln('Отримана сума - ',Sum:8:2); 
     Readkey; {Затримка зображення на екрані} 
End.