IX. Пошук елементів у масивах

ЗАДАЧА № 51

Постановка задачі:

Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від’ємними числами, а дівчаток – додатними у вигляді цілих значень а₁, а₂, …, а_n? Крім того, у всіх дівчаток на голівках зав’язані бантики заввишки 10 см, а висота паркану Н см.

Аналіз алгоритму:

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

Текст програми:

Program Task_51;

Uses crt;

Var N, H:word;{N – кількість дітей в дитсадочку, Н – висота паркану}

А:аrrау[1..100] of longint;

{А – зарезервований масив для зберігання зросту дітей}

і, Count_Girl, Count_Boy:longint;

{і – змінна циклу,

Count_Girl – кількість дівчаток,

Count_Boy – кількість хлопців}

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)>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.

ЗАДАЧА № 52

Постановка задачі:

Дано натуральне число п та послідовність дійсних чисел а₁, а₂, …, а_n. Визначити кількість сусідств двох чисел різного знаку.

Аналіз алгоритму:

Перш за все запропонуємо в цій задачі інший метод опису масиву з використанням константи, що задає розмір масиву, та вказівки Туре. А, по-друге, зверніть увагу, що для визначення двох сусідніх елементів масиву використовується загальний опис індексів і та і + 1 (можна і – 1 та і), а це при організації циклу можне викликати ситуацію виходу за межі масиву. Дійсно, якщо організувати цикл з параметром для зміни індексу від 1 до N, де N – кількість елементів масиву, то при і = N значення і + 1 буде виходити за межі масиву. Це є помилкою, що призводить до неочікуваних результатів, тому цикл треба організовувати для зміни індексу не від 1 до N, а для зміни від 1 до N – 1.

Текст програми:

Program Task_52;

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:=1 to N–l do

If ((A[i]<0)>0)) or ((A[i]>0) and (A[i+1]<0))

Then Count:=Count+l;

Writeln;

Writeln(‘Кількість заданих сусідств = ‘, Count);

Readkey;

End.

ЗАДАЧА № 53

Постановка задачі:

Дано одновимірний масив цілих чисел A[i], де i = 1, 2, …, п. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу.

Аналіз алгоритму:

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

1) береться будь-який елемент масиву (як правило, перший) і його значення присвоюється змінній max, тобто він вважається за еталон найбільшого елементу;

2) по черзі з масиву вибираються всі останні елементи і, якщо серед них знайдеться більший за обраний еталон, то змінній max присвоюється нове значення, яке тепер буде новим еталоном. В іншій змінній, наприклад, N_max запам’ятовується номер цього найбільшого елементу (початкове значення цієї змінної було 1, тому що спочатку ми вважали найбільшим 1-ий елемент). Після закінчення перегляду всього масиву змінна max буде містити шуканий максимум, а змінна N_max – його номер. Щоб запам’ятати номер першого максимального елемента, необхідно шукати в матриці елемент, що точно більший еталону. Якщо ж ми будемо шукати елемент, що не менший за еталон, то в змінній N_max залишиться номер останнього найбільшого елементу (подумайте чому).

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

Текст програми:

Program Task_53;

Uses crt;

Const n = 30;

Var A:array[1..n] of integer; {A – масив даних чисел}

і:byte; {і – змінна циклу}

count, N_max:byte;

{count – кількість максимальних елементів в масиві,

N_max – номер першого найбільшого елементу}

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[1];

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.

ЗАДАЧА № 54

Постановка задачі:

Дано цілочислову прямокутну таблицю порядку N × M. Усі елементи таблиці менші за середнє арифметичне її значень, замінити на «– 1», а більші – на «1».

Аналіз алгоритму:

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

Текст програми:

Program Task_54;

Uses crt;

Const n = 9; m = 12;

Type Masiv = array[1..n, 1..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] <>

if A[i,j] > SA then A[i,j]:=1;

Write(A[i,j]:5);

End;

Writeln;

End;

Readkey;

End.

ЗАДАЧА № 55

Постановка задачі:

У даній дійсній матриці розмірністю 6×9 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент у матриці єдиний.

Аналіз алгоритму:

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

Текст програми:

Program Task_55;

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; {N_max – номер рядка, що містить макс. елемент}

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)/11;

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.

VIII. Двовимірні масиви

ЗАДАЧА № 49

Постановка задачі:

Дано натуральні числа п, т. Обчислити значення елементів матриці С_ij, (і = 1, 2,…, п, j=1, 2,…, т), якщо:

Текст програми:

Program Task_49;

Uses crt;

Const n = 20; m = 15;

Var C:array[1..n, 1..m] of integer;

i, j:integer; {i, j – змінні циклу}

Begin

Clrscr;

For i:=1 to n do

Begin

For j:=1 to m do

Begin

If і

Else C[i,j]:=i*i + j*j;

Write(C[i,j]:5);

End;

Writeln;

End;

Readkey;

End.

ЗАДАЧА № 50

Постановка задачі:

Дано квадратну матрицю розмірності п. Надрукувати суму елементів бічної діагоналі.

Аналіз алгоритму:

Розв’язок задачі є тривіальним, якщо згадати, яку залежність мають індекси бічної діагоналі
(і + j = п + 1). Перевіривши цю залежність у середині циклів, що організовують проходження по масиву, ми знайдемо бажану суму.

Текст програми:

Program Task_50;

Uses crt;

Const n = 10;

Var A:array[1..n, 1..n] of real;

і,j:integer; {і, j – змінні циклу}

Sum:real; {Sum – сума елементів бічної діагоналі}

Begin

Randomize;

Clrscr;

{Заповнення масиву та виведення його на екран}

For і:=1 to n do

Begin

For j:=1 to n do

Begin

A[i,j]:=random*50–random(80)/3;

Write(A[i,j]:8:3);

End;

Writeln;

End;

Sum:=0; {Початкове значення суми}

For і:=1 to n do

Begin

For j:=1 to n do

If і+j=n+1 Then Sum:=Sum+A[і,j];

End;

Writeln(‘Сума елементів бічної діагоналі = ‘, Sum:8:2);

Readkey;

End.

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

Sum:=0; {Початкове значення суми}

For i:=1 to n do Sum:=Sum+A[i,n+1–i];

VII. Одновимірні масиви

ЗАДАЧА № 44

Постановка задачі:

Дано одновимірний масив цілих чисел А[і], де і = 1, 2, …, n. Вивести елементи масиву з парними індексами.

Аналіз алгоритму:

У даному випадку незручно користуватися для виведення на екран елементів з парними індексами циклом з параметром, тому що він дозволяє зміну індексу тільки на одиницю. Тому пропонуємо скористатися циклом з перед- або післяумовою.

Текст програми:

Program Task_44;

Uses crt;

Var N, і:word; {N – кількість елементів масиву, і – змінна циклу}

A:array[1..100] of longint; {A – заданий масив}

Begin

Clrscr;

Write(‘Введіть кількість елементів масиву (<100):>

Readln(N);

For i:=1 to N do

Begin

А[і] :=random(300) ; {Заповнення масиву випадковими числами}

Write(A[i]:5); {Виведення масиву на екран для контролю правильності роботи програми}

End;

Writeln; {Переведення курсору на наступний рядок}

і:=2;

while i<=N do

Begin

Write(A[i]:5);

i:=i+2; {Змінна циклу змінюється на 2, щоб вибрати тільки парні елементи}

End;

Readkey;

End.

ЗАДАЧА № 45

Постановка задачі:

Барон Мюнхгаузен, вийшовши на екологічно чисте полювання, зарядив свою рушницю кісточками вишень. Після того, як він вдало влучив поміж роги оленям (в яких влучило відповідно k₁, k₂, …, k_N кісточок), у них на головах виросли чудові молоді вишеньки. Скільки саджанців зміг подарувати барон Мюнхгаузен садівникам-дослідникам?

Аналіз алгоритму:

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

Текст програми:

Program Task_45;

Uses crt;

Var N:word;

К:array[1..100] of longint;

{K – зарезервований масив для зберігання кількості кісточок, що влучили в оленів}

і,Sum:longint; {і – змінна циклу,

Sum – загальна кількість кісточок, що влучили в оленів}

Begin

Randomize; {Ця процедура запускається з метою зробити числа генератора випадкових чисел ще більш «випадковими»}

Clrscr;

Sum:=0; {Спочатку Мюнхгаузен ще ні в кого не влучив}

Write(‘Олені, в яких влучив Мюнхгаузен (<=100): ‘);

Readln(N);

For і:=1 to N do

Begin

К[і]:=random(50)+20;{Заповнення масиву випадковими числами в діапазоні від 20 до 70}

Write(К[і]:5); {Виведення на екран для контролю}

Sum: =Sum+K[і]; {Знаходження кількості влучених кісточок}

End;

Writeln; {Переведення курсору на новий рядок}

Writeln(‘Кількість нових саджанців: ‘, Sum);

Readkey;

End.

ЗАДАЧА № 46

Постановка задачі:

Дано натуральне число А. Складіть програму, що представляє його у вигляді многочлена. Наприклад, 123 = 1 × 10² + 2 × 10¹ + 3 × 10⁰.

Аналіз алгоритму:

Ця задача фактично зводиться до пошуку окремих цифр числа. Оскільки ми не знаємо на початку роботи, скільки цифр має число, для їх зберігання можна використати масив цілих чисел, причому розмірність цього масиву можна задати не більше 10 елементів, тому що навіть найбільше ціле число типу longint має в своєму складі не більше 10 цифр. Щоб вивести на екран отриманий многочлен, ми спочатку знаходимо кількість цифр у числі та виділяємо кожну цифру окремо, а потім організовуємо цикл від «найстаршої» значущої (ненульової) цифри числа до «наймолодшої» з виведенням на екран самої цифри, помноженої на 10 у степені номер розряду–1 (тобто i–1).

Текст програми:

Program Task_46;

Uses crt;

Var N, і, Count:longint; {N – задане ціле число,

і – змінна циклу,

Count – кількість цифр в числі}

Cifra:array[1..10] of byte; {Cifra – масив для зберігання цифр числа}

Begin

Clrscr;

Count:=0;

Write(‘Введіть ціле число: ‘);

Readln(N);

While N>0 do

Begin

Count:=Count+1;

Cifra[Count]:=N mod 10;

N:=N div 10;

End;

Write(‘N = ‘);

For i:=Count downto 1 do

Begin

Write(Cifra[i],‘*10^’,i–l); {Якщо доданок не останній, то до нього дописується знак «+»}

If і>1 Then write(‘ + ‘);

End;

Readkey;

End.

ЗАДАЧА № 47

Постановка задачі:

Дано дійсні числа а₁₉₅₁, а₁₉₅₂, … , а₂₀₀₀ – кількість опадів (у мм), що випали у місті за останні 50 років XX століття. Обчислити середню кількість опадів за цей період і щорічне відхилення від середнього значення.

Аналіз алгоритму:

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

Текст програми:

Program Task_47;

Uses crt;

Var N, i:longint; {N – кількість елементів масиву, і – змінна циклу}

А:аrrау[1951..2000] of real; {A – масив для зберігання кількості опадів у відповідному році}

В:array[1951..2000] of real; {В – масив для зберігання відхилення від середнього значення}

Begin

Randomize;

Clrscr;

Sum:=0;

For і:=1951 to 2000 do

Begin

A[i]:=random(500)/7;{Заповнення масиву випадковими дійсними числами}

Write (А[і]:8:2);{Виведення масиву на екран для контролю}

Sum:=Sum+K[і];

End;

Sum:=Sum/50; {Середня кількість опадів за рік}

Writeln;

WriteIn(‘Щорічні відхилення від середньої кількості опадів за період 1951–2000 p.p.‘);

For і:=1951 to 2000 do

Begin

В[і]:=Sum – А[і]; {Знаходження щорічного відхилення}

Write(В[і]:8:2); {Виведення результатів на екран}

End;

Readkey;

End.

ЗАДАЧА № 48

Постановка задачі:

Дано дійсні числа а₁, а₂, … , a₃₀ та b₁, b₂, …, b₃₀. Обчислити

Аналіз алгоритму:

Очевидно, що для обчислення результату цієї задачі спочатку необхідно знайти чисельник та знаменник дробу. Причому зверніть увагу на те, що кількість доданків і в одному, і в іншому випадках дорівнює 15, тільки в чисельнику вибираються елементи масивів з непарними індексами, а в знаменнику – із парними. Щоб організувати зміну індексів за заданим правилом, можна скористатися таким штучним прийомом: якщо в циклі з параметром індекс і змінюється від 1 до п, то для отримання непарних чисел з проміжку [1..2n] використовується формула:            2*і-1.

Запропонуйте дітям подумати, яка формула дасть змогу отримати парні числа (Відповідь: 2*і).

Текст програми:

Program Task_48;

Uses crt;

Var A, B:array [1..30] of real;

{А, В – масиви для зберігання вхідних даних}

і:byte; {і – змінна циклу}

Rl, R2:real; {R1 – чисельник дробу, R2 – знаменних дробу}

Rez:real; {Rez – результат обчислень}

Begin

Randomize;

Clrscr;

Writeln(‘Масив А:’);

For i:=1 to 30 do

Begin

A[i]:=random(200)/7–random*15;

Write(A[i]:8:2);

End;

Writeln;

Writeln(‘Масив В:’);

For i:=1 to 30 do

Begin

B[i]:=random*200–random*100;

Write(B[i]:8:2);

End;

Writeln;

Rl:=0; R2:=0; {Початкові значення дорівнюють 0, тому що результат є накопиченням суми}

For і:=і to 15 do

Begin

R1:= R1+(A[2*i–1]+B[2*i–1]);

R2:= R2+(A[2*i]+B[2*i]) ;

End;

Rez:=Rl/R2;

Writeln(‘Результат обчислень = ‘, Rez:8:2);

Readkey;

End.