вівторок, 2 червня 2020 р.

Алгоритми сортування лінійного масиву

Сортування елементів у одновимірних масивах

Задача 1. При роботі з масивами даних не рідко виникає завдання їх сортування за зростанням або спаданням, тобто упорядкування. Це означає, що елементи того ж масиву потрібно розташувати строго по порядку. Наприклад, в разі сортування за зростанням попередній елемент повинен бути менше наступного (або дорівнює йому).
Розв’язання
Існує безліч методів сортування. Одні з них є більш ефективними, інші - простіше для розуміння. Досить простий для розуміння є сортування методом бульбашки, який також називають методом простого обміну. У чому ж він полягає, і чому у нього така дивна назва: "метод бульбашки"?
Як відомо повітря легше води, тому бульбашки повітря спливають. Це просто аналогія. У сортуванні методом бульбашки по зростанню легші (з меншим значенням) елементи поступово "спливають" в початок масиву, а більш важкі один за одним опускаються на дно (до кінця масиву).
Алгоритм і особливості цього сортування такі:
1.     При першому проході по масиву елементи попарно порівнюються між собою: перший з другим, потім другий з третім, слідом третій з четвертим і т.д. Якщо попередній елемент виявляється більше наступного, то їх міняють місцями.
2.     Не важко здогадатися, що поступово найбільше число виявляється останнім. Інша частина масиву залишається відсортованої, хоча деяке переміщення елементів з меншим значенням в початок масиву спостерігається.
3.     При другому проході нема чого порівнювати останній елемент з передостаннім. Останній елемент вже стоїть на своєму місці. Значить, число порівнянь буде на одне менше.
4.     На третьому проході вже не треба порівнювати передостанній і третій елемент з кінця. Тому число порівнянь буде на два менше, ніж при першому проході.
5.     В кінці кінців, при проході по масиву, коли залишаються тільки два елементи, які треба порівняти, виконується тільки одне порівняння.
6.     Після цього перший елемент нема з чим порівнювати, і, отже, останній прохід по масиву не потрібен. Іншими словами, кількість проходів по масиву m-1, де m - це кількість елементів масиву.
7.     Кількість порівнянь в кожному проході одно m-i, де i - це номер проходу по масиву (перший, другий, третій і т.д.).
8.     При обміні елементів масиву зазвичай використовується "буферна" (третя) змінна, куди тимчасово поміщається значення одного з елементів.
Програма на мові Паскаль:
const
    m = 10;
var
    arr: array[1..m] of integer;
    i, j, k: integer;
begin
    randomize;
    write ('Початковий масив: ');
    for i := 1 to m do begin
        arr[i] := random(256);
        write (arr[i]:4);
    end;
    writeln; writeln;
    for i := 1 to m-1 do
        for j := 1 to m-i do
            if arr[j] > arr[j+1] then begin
                k := arr[j];
                arr[j] := arr[j+1];
                arr[j+1] := k
            end;
    write ('Відсортований масив: ');
    for i := 1 to m do
        write (arr[i]:4);
    writeln;
readln
end.

 Найшвидший  алгоритм Хоора(Гоара) для сортування одновимірного масиву у вигляді процедури мовою програмування Pascal
Ця процедура, після її оголошення, сортує масив mas, який складається з елементів типу integer.
Procedure QuickSort(first, last :integer);
Var v, x, left, right :integer;
begin
  left := first;
  right := last;
  v := mas[(left + right) div 2];
  while left <= right do
    begin
    while mas[left] < v do
      left := left + 1;
    while mas[right] > v do
      right := right - 1;
    if left <= right then
      begin
        x := mas[left];
        mas[left] := mas[right];
        mas[right] := x;
        left := left + 1;
        right := right - 1;
      end;
    end;
  if first < right then 
    QuickSort(first, right);
  if left < last then
    QuickSort(left, last);
end;



Задача 2. Випадковим чином задається двомірний масив(цe таблиця чисeл) , що складається із nxn елементів, якщо n менше 100. Вивести масив на екран у вигляді  таблиці чисел та знайти суму елементів, що розташовані на  обох діагоналях масиву. Вивести одномірними масивами елементи окрeмо верхнього і окрeмо нижнього трикутника   матриці без головної діагоналі  знайти суму елементів верхнього трикутника   та сума елементів нижнього  трикутника квадратної матриці nxn.
Розв′язання.
Program Summa_trukutnuk_matriza;
const m=100;  n=100;
var  sum,f,s,  d, c:real;    b:array[1..m*n] of real;
 xn:array[1..m*n] of real;     xv:array[1..m*n] of real;      a:array[1..m,1..n] of real;
i,j,p, g, k:integer;
begin
writeln('  Ввeдіть кількість рядків квадратного масиву,  яка мeншe 100 ');
readln(k);    s:=0;
for i:=1 to k do
for j:=1 to k do  begin
a[i,j]:=int(random*20-10);
b[(i-1)*k+j]:=a[i,j];   end;  writeln('   ');
writeln(' Масив випадкових чисeл: ');  writeln('   ');
for i:=1  to k do   begin
for j:=1  to k do  begin      write('  a[',i,';',j,']:= ',a[i,j]  {'  b[',i-1*k+j,']= ',b[(i-1)*k+j]});
end; writeln('   '); end;
s:=0;   for i:=1 to k do  begin   s:=s+a[i,i];  end;
f:=0;  for i:=1 to k do  begin  f:=f+a[i,k+1-i]; end;
     if   k mod 2 =1 then   sum:=s+f- a[k div 2 +1, k div 2 +1]   else   sum:=s+f;
p:=1;  g:=1;    for i:=1  to k do   begin
for j:=k  downto 1 do  begin
  if   i<j  then  begin
  xv[g]:= a[i,j];  g:=g+1; end;  end; end;
  for i:=1  to k do   begin
  for j:=1  to i-1 do  begin
  if   i>j  then  begin
  xn[p]:= a[i,j];   p:= p+1; end; end;  end;
writeln(' Масив   чисeл нижнього трикутника матриці : ');
          d:=0;  for i:=1  to   ((k-1)*k) div 2     do     begin    d:=d+ xn[i];
write('  xn[',i,']= ', xn[i]); end; writeln('   ');
writeln(' Масив   чисeл вeрхнього трикутника матриці :  ');
           c:=0;  for i:=1  to ((k-1)*k) div 2    do   begin
c:=c+ xv[i];  write('  xv[', i, ']= ', xv[i]);   end;    writeln('   ');
writeln('  Сума чисел головної діагоналі матриці:', s); writeln('    ');
writeln('  Сума  чисел  бічної  діагоналі матриці :', f); writeln('    ');
writeln('  Сума чисел на обох діагоналях: ', sum);   writeln('    ');
writeln('  Сума чисел верхнього трикутника матриці ' , c);  writeln('    ');
writeln('  Сума чисел нижнього трикутника матриці  ' ,  d);    writeln('    ');       end.



Задача 3. Вагони
(Час: 1 сек. Пам'ять: 16 Мб Складність: 23%)

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

Відомі алгоритми сортування

За час 
  • Сортування вибором — ( англ.  Selection sort ) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
  • Сортування вставкою — (англ. Insertion sort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
  • Сортування обміном (сортування бульбашкою ( англ.  Bubble sort )) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
  • Сортування методом бінарної вставки
За час 
За час  з використанням додаткової інформації про елементи
За час 
За час 

В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.
Опубліковано о Немає коментарів:

Тип даних масиви в Pascal

У різних розділах математики та інших наук дані, що мають вигляд інформації, заданої як послідовність рядків і стовпчиків, називають по-різному: матриці - у вищій алгебрі, таблиці - у розрахункових задачах, масиви - у програмуванні.
       Зразки числових масивів:
  а) Одновимірний масив на множині цілих чисел з 5 елементів:
            1   -2   5   0  -6
       

      б)    Двовимірний масив розміром 3х4 на множині цілих чисел з 12 елементів:
            1   2   5   6
           4  4   -7   -1
           -1 0   0   9

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

Масив - це великий простір чогось однорідного за типом. (Зі словника іноземних слів, 1954 р.)
Масив у програмуванні - це тип структури даних, що має складені значення. (З Оксфордського словника англійської мови, 1995 р.)
Масив - це впорядкований скінченний набір елементів (даних) одного типу. Зазвичай працюють з масивами, які містять числа.

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

Індексом називається порядковий номер елемента масиву.

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

Як звернутися до елементів цього масиву? Для цього необхідно вказати індекс.

Наприклад,

T[2], T[5], T[i], T[i + j].

Але в третьому і четвертому прикладах для визначення необхідного елемента масиву треба знати значення величин і та j. Така загальність визначення індексу масиву є дуже потужним засобом програмування, але разом з цим і провокує можливі помилки: отриманий результат обчислення індексу масиву може виходити за межі інтервалу, виділеного для індексів даного масиву.

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

Тепер зрозуміло, як у циклі перебирати різні значення елементів масиву: для цього достатньо змінювати їх індекси. А закон зміни індексів дуже простий - кожне наступне значення більше попереднього на одиницю. Дуже зручна закономірність!


Оскільки у мові Pascal усе з чим ми працюємо потрібно оголошувати, то масиви також потрібно оголосити. Це можна зробити кількома способами:

у полі const

const <ім'я змінної>=array[1 .. <клькість елементів>] of <тип> = (1,2,3, ... <значення>);

у полі type

type <ім'я типу>=array[1 .. <кількість елементів>] of <тип>;
var <ім'я змінної> : <ім'я типу>; 

у полі var

var <ім'я змінної> : array[1 .. <кількість елементів>] of <тип>;

Приклад:

type Mas = array[1 .. 5] of integer;
var a : Mas;

Масиви бувають одновимірними (у вигляді послідовності чисел), двовимірними (у вигляді таблиць чисел розміром m x n) і багатовимірними (3-,4-вимірні і т.д. 3-вімірні - це об'ємний простір з комірками, а 4-вимірні і більше - це фантастично-абстрактні поняття). 

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

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

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

Розмірність масивів у Pascal необмежена, вона визначається лише об'ємом пам'яті вашого комп'ютера.

Резонним буде запитання: а як же розташовуються масиви в пам'яті комп'ютера? Пояснення для одновимірних масивів дуже просте – всі вони розташовані в пам'яті підряд. Двовимірні масиви розташовуються дещо інакше - спочатку елементи пер­шого рядка, потім другого і т. д. Розташування масивів більшої розмірності пояснюється аналогічно.

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

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

Наприклад,

varA: array[1..10] of real;B: array[1..100,1..100] of byte;C: array[1..100] of array[1..100] of byte.

Цікаво, що другий і третій приклади описують однакові ма­сиви. Справді, адже будь-яку таблицю можна розглядати як послідовність рядків, де кожний рядок у свою чергу є також послідовністю. Звернення до елементів останнього масиву буде мати такий вигляд: C[i][j].

Зауваження.

По-перше, межі індексів завжди вказуються через два символи «.».

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

По-третє, межі зміни індексів повинні бути сталими величи­нами, а не змінними, інакше невідомо буде, скільки місця не­обхідно відвести в пам'яті під такий масив.

Розглянемо таку задачу.
Нехай дано таблицю здійснення рейсів N автобусами протягом M днів. Рейси, що відбулися, позначаються в таблиці цифрою 1, а ті, що з деяких причин не відбулися, - цифрою 0. Треба скласти програму, яка підраховує кількість рейсів, що не відбулися.

Приклад програми

program voyage;
var R :array[1..30,1..100] of byte;
і, j, n, m, count : integer;
begin
write ('Задайте кількість автобусів: ');
repeatreadIn(n) until (n > 0) and (n <= 30);
write ('Задайте кількість днів: ');
repeatreadln (m) until (m > 0) and (m <= 100);
writeln ('Задайте інформацію про здійснення рейсів: ');
for i := 1 to n do for j := 1 to m do beginwrite (i, ' автобус, ', j, ' день: ');
repeatreadln(R[i,j]) until (R[i, j] = 0) or (R[i, j] = 1) end;count := 0;
for і := 1 to n do
for j := 1 to m do
if R[i. j] = 0 then count := inc (count);
writeln ('Кількість нездійснених рейсів: ', count:5);
repeat
until
Key
Pressed
end.

У цій програмі використано нову стандартну процедуру мови Pascal inc (count). Ії призначення - заміна значення пара­метра на 1. Можливий ще такий варіант використання цієї процедури: inc (n, step). У цьому разі збільшення параметра п відбуватиметься з кроком step. У Pascal існує альтернативна процедура Dec, яка зменшує значення вказаного параметра.

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

Повернемося до початку знайомства з Pascal, де вводилося поняття про розділ констант const. У цьому розділі ідентифіка­торами позначаються сталі величини. Надалі в програмі замість цих сталих величин вказуватимемо лише відповідні їм ідентифікатори. Зручність полягає в тому, що якщо знадобить­ся поміняти значення якоїсь константи, то достатньо це зроби­ти тільки в розділі const, не чіпаючи всієї програми.

Наприклад, можна розміри масиву задати таким чином:

const SizeLine = 100;
SizeColumn = 100;
var A: array [1..SizeLine, 1..SizeColumn] of real;
.............................................
repeatread (n, m) until (n > 0) and (n <= SizeLine) and (m > 0) and (m <= SizeColumn);

Зверніть увагу на те, що в розділі констант стоїть символ «=», а не символ «:=».Використовуючи в програмі константи, необхідно врахувати таку особливість: їх значення не можна змінювати під час виконання програми. Тобто ідентифікаторам, що визначають

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

Ми говорили про те, як незручно під час редагування програми щоразу заново задавати значення елементів масиву. Спробуємо і це зробити за допомогою розділу констант:

constA:array[1..3, 1..4] of real= ((1.5, 1.2, 2.1,-4.42), (2.4,5.7,-1, 45.4), (-1.1,7, 45,-10));

3 останнього прикладу видно, що в розділі констант можна задавати ще й тип. Такі константи називаютьсятипізованими. Значення масивам задаються таким чином: в одновимірних масивах вони записуються через кому, у двовимірних – значення елементів рядків беруться у круглі дужки, для тривимірних – аналогічним чином. Відмінність типізованих констант від простих, для яких тип не вказується, полягає в тому, що їх значен­ня можна змінювати під час виконання програми.

Якщо ж вас не цікавлять конкретні дані, які будуть надані елементам масиву під час виконання програми, то скористайтеся можливостями стандартної процедури Pascal Randomize та функції Random (n), що генерують випадкові числа. Параметр n (типу Word) у процедурі Random визначає праву межу інтервалу, в якому будуть визначатися випадкові числа (ліва межа завжди 0). Функція Random може задаватися і без параметра. У цьому разі вона генеруватиме те дійсне число в діапазоні [0; 1). А для того щоб випадкові числа в програмі з кожним її наступним запуском не повторювалися (хоча вони і випадкові, але послідовність цих чисел постійна), то скористайтеся процедурою Randomize, яка встановить початок відрахунку випадкових чисел залежно від поточного стану системного годинника вашого комп'ютера.

Фрагмент програми, що використовує випадкові числа, може виглядати так:

randomize;
for і := 1 to n doa[i] := random (100);

 Завдання для самостійного опрацювання

Одновимірні масиви 
  Введення масиву з клавіатури
     for i:=1 to n do readln(a[i]);    тут (і надалі) і - параметр, n - кількість елементів у 
                                                       масиві, а -  одновимірний масив
  Друк масиву на екран 
     for i:=1 to n do writeln(a[i]);
   Перебір всіх елементів
     for i:=1 to n do
        begin
       if a[i]=0 then s:=s+1;    - кількість елементів, які відповідають умові (у даному разі 
                                       ті, що рівні  нулю). Кількість буде записана до змінної s 
      if a[i]=0 then k:=i;        - порядковий номер елементу, який відповідає умові (=0)
        end;
  Пошук мінімального/максимального елеманту 
Припускаємо, що це перший і переглядаємо масив. Якщо зустрінемо більший (чи менший) за нього елемент, то цей елемент стає максимальним (мінімальним). Розглянемо пошук максимального:
max:=a[1]; 
for i:=1 to n do
   if a[i]>max then max:=a[i];
  Сортування за зростанням/спаданням 
Переглянемо масив n разів. Кожного разу розглядаємо всі елементи від 1 до n-1. Якщо елемент більший (сортування за зростанням) за нступний за ним, то міняємо їх місцями.
fo j:=1 to n do        {переглядаємо масив n разів}
for i:=1 to n-1 do    {переглядаємо кожного разу елементи від 1 до n-1 (бо можемо                          
                      поміняти міцями  a[n-1] і a[n] - а у програмі буде a[i] та a[i+1] при i=n-1)}
    if a[i]>a[i+1] then
       begin
            b:=a[i];       {зберігаємо значення a[i] в іншу змінну, тип якої такий як і   
                                               елементів масиву}
            a[i]:=a[i+1];  {власне міняємо місцями елементи - записуємо менше значення на 
                                              місце    більшого}
            a[i+1]:=b;       {"витягуємо" з пам'яті значення a[i], більше, і записуємо на нове   
                                                               місце}
       end; 
Такий метод сортування називається бульбашковим (або "Метод бульбашки"). Різні особи по-різному трактують цю назву, тому я взагалі не буду трактувати її. Сприймайте цей метод так, як його обізвали.

Двовимірні масиви (n x m)

  Введення масиву з клавіатури 
for i:=1 to n do       {перебір n рядків}
  for j:=1 to m do     {перебір m стовпців}
    readln(a[i,j]);         {власне ввід кожного елементу}
  Вивід масиву на екран 
Щоб вивести двовимірний масив на екран у вигляді таблиці роблять наступне: 
for:=1 to n do     {перебір рядків}
  begin
     for j:=1 to m do write(a[i,j],' ');      {вивід кожного рядка}
     writeln;                                       {перехід на новий рядок}
  end; 

Приклад програми.

Утворити і вивести масив у з елементами у(к), к=1,12. Перший додатний елемент поміняти місцями з максимальним

program Masuvu;
uses crt;
var y,g:array [1..12] of real; max,h:real;
k,n,m:integer;
begin 
clrscr; 
max:=-1000000; 
n:=0; 
for k:=1 to 12 do 
begin 
y[k]:=sin(k*k)*cos(k*k*k)-sin(k)+5.2; 
if y[k]>max then 
begin 
max:=y[k]; 
m:=k; 
end; 
if y[k]>0 then 
begin 
n:=n+1; 
g[n]:=y[k]; 
h:=g[1]; 
end; 
if y[k]=g[1] then 
begin 
y[k]:=max; 
y[m]:=h; 
end; 
writeln (k,' element ',y[k]:5:2); 
if n>0 then writeln ('pershuj dodatnij element',g[1]:5:2)else writeln('nema dodatnih elementiv'); 
writeln ('maksumalnuj element - ', m,' -',max:5:2); 
readln; 
end. 
end. 

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

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

Задача:Дано натуральне число 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. 

Задача: Дано одновимірний масив цілих чисел 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. 

Задача:Дано натуральне число n. Визначити кількість додатних та від'ємних елементів таблиці aij, де i,j = 1,2,…,n, якщо: Aij = sin(i+j).

Візьмемо дві змінних count_plus та count_minus для зберігання кількості додатних та від'ємних елементів масиву відповідно.

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

Програма, що реалізує запропонований алгоритм, наведена нижче: 

Program Example_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. 

 Array1. Дано ціле число  N  (> 0). Сформувати і вивести цілочисельний масив розміру  N , що містить  N  перших позитивних непарних чисел: 1, 3, 5, ....
Array2. Дано ціле число  N  (> 0). Сформувати і вивести цілочисельний масив розміру  N , що містить ступеня двійки від першої до  N -й: 2, 4, 8, 16, ....
Array7 °. Дан масив розміру  N . Вивести його елементи в зворотному порядку.
Array8. Дан цілочисельний масив розміру  N . Вивести все що містяться в даному масиві непарні числа в порядку зростання їх індексів, а також їх кількість  K .
Array18. Дан масив  A  ненульових цілих чисел розміру 10. Вивести значення першого з тих його елементів  A K , які задовольняють нерівності  A K  <  A 10 . Якщо таких елементів немає, то вивести 0.
Array19. Дан цілочисельний масив  A  розміру 10. Вивести порядковий номер останнього з тих його елементів  A K , які задовольняють подвійному нерівності  A 1  <  A K  <  A 10 . Якщо таких елементів немає, то вивести 0.
Array33. Дан масив розміру  N . Знайти номер його останнього локального максимуму ( локальний максимум  - це елемент, який більше будь-якого зі своїх сусідів).
Array34. Дан масив розміру  N . Знайти максимальний з його локальних мінімумів (визначення  локального мінімуму  дано в завданні Array32 ).
В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.

Опубліковано о Немає коментарів:
Підписатися на: Дописи (Atom)