X. Впорядкування масивів

ЗАДАЧА № 56

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

Дано натуральне число п та послідовність дійсних чисел а₁, а₂, …, а_п. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.

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

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

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

Program Task_56;

Uses crt;

Const N = 100;

Type Masiv = array[1..N] of real;

Var A, B:Masiv; {A – масив для зберігання початкової послідовності,

В – відсортований масив}

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

count – кількість елементів, що залишились на своїх місцях}

Max:real; {Мах – максимальний елемент підмасиву}

N_max:byte; {N_max – номер максимального елементу}

Begin

Randomize;

Clrscr;

For i:=1 to N do

Begin

A[i]:=random*100–random*50;

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

End;

B:=A; {Копіювання елементів масиву А в масив В}

For i:=1 to N–1 do

Begin

Max:=B[i]; {Зберігання еталону максимуму}

N_Max:=i; {Зберігання номера максимуму}

For j:=i+1 to N do

If B[j]>Max Then

Begin

Max:=B[j]; {Перевизначення еталону}

N_Max:=j; {Зберігання номеру еталону}

End;

{Обмін місцями мінімуму та першого елементу підмасиву}

B[N_Max]:=В[і]; В[і]:=Мах;

End;

count:=0;

For і:=1 to N do

Begin

If A[i]=B[i] Then count:=count+1;

End;

Writeln;

Writeln(‘Кількість елементів, що не змінили місця = ‘ , count) ;

Readkey;

End.

ЗАДАЧА № 57

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

Дано натуральне число п та послідовність дійсних чисел а₁, а₂, …, а_п. Визначити усі числа, що входять у послідовність по одному разу.

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

Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, оскільки однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, «бульбашка»), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.

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

Program Task_57;

Uses crt;

Const N = 100;

Type Masiv = array[1..N] of real;

Var A:Masiv; {A – масив для вихідної послідовності}

і, j, count:byte; {і, j – змінні циклу,

count – кількість елементів, що входять у послідовність один раз}

k: integer; {к – змінна, що коригує праву границю сортування}

Flag:Boolean; {Flag – змінна, що фіксує, чи була перестановка}

Begin

Randomize; Clrscr;

For i:=1 to N do

Begin

A[i]:=random(300)/11–random*15;

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

End;

k:=1;

Repeat

Flag:=false;

For i:=1 to N–k do

Begin

If A[i]

Begin {Обмін елементів масиву через третю змінну}

Rez:=A[i]; А[і]:=А[і+1]; A[i+1]:=Rez;

Flag:=true;

End;

k:=k–1;

End;

Until Flag = false;

count:=0;

For i:=1 to N–1 do

Begin If A[i]OA[i+l] then count: =count+1; End;

count:=count+l;

Writeln;

Write (‘Кількість елементів, що входять у послідовність 1 paз = ‘);

Writeln(count);

Readkey;

End.

X. Впорядкування масивів (вступна частина)

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

У ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення є неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше N-1 разів, де N – кількість елементів у масиві.

Найпростіший алгоритм «бульбашки» має наступний вигляд:

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

Program Bubble_1; {Сортування за зростанням}

Const N=20;

Var Mas:array[1..N] of integer;

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

Rez: integer; {Rez – додаткова змінна для обміну елементів масиву між собою}

Begin

For i:=1 to N do

For j:=1 to N–1 do

If Mas[j]>Mas[j+1] Then

Begin

{Обмін елементів масиву через третю змінну)

Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez;

End;

End.

 

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

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

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

Program Bubble_2; {Сортування за зростанням}

Const N=20

Var Mas:аrray[1..N] of integer;

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

Rez:integer; {Rez – додаткова змінна для обміну елементів масиву між собою}

Begin

For i:=1 to N do

For j:=1 to N–i do

If Mas[j]>Mas[j+1] then

Begin

{Обмін елементів масиву через третю змінну}

Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez;

End;

End.

Зверніть увагу, що в цьому алгоритмі у вкладеному циклі, що безпосередньо здійснює порівняння елементів, змінна циклу змінюється за іншим законом, ніж у попередньому випадку: від 1 до N–i, де і – змінна циклу зовнішньої команди повторення.

Другий метод модифікації алгоритму «бульбашки» полягає в тому, що ми вводимо додаткову змінну булівського типу (так званий прапорець), яка фіксуватиме при черговому проході була здійснена хоча б одна перестановка елементів чи ні. Адже очевидно, що якщо при черговому проході не відбулося жодної перестановки, то масив уже відсортований і процес перегляду можна припинити. Домовимось вважати прапорець «опущеним» (тобто рівним значенню false), якщо перестановки не відбулося, і «піднятим» (рівним true) – у протилежному випадку. Крім того, як і в попередньому випадку, після кожного проходу по масиву найбільший елемент «спливає» угору, тобто займає своє позицію. Тому вводимо додаткову змінну k, що фіксує праву границю впорядкованості, тобто при першому проході k = 1 і ми впорядковуємо всі елементи від 1 до N–1, на другому проході k = 2 і будуть впорядковуватись усі елементи від 1 до N–2 (останній елемент уже впорядкований) і так далі.

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

Program Bubble_3; {Сортування за зростанням}

Const N=20;

Var Mas:array[1..N] of integer;

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

k – змінна, що фіксує праву границю впорядкування}

Rez:integer; {Rez – додаткова змінна для обміну елементів масиву між собою}

Flag:Boolean; {Flag – змінна, що фіксує перестановку}

Begin

k:=1;

Repeat

Flag:=false; {Робимо припущення, що масив відсортований, а потім перевіряємо, чи правильним було це припущення, тобто чи немає серед елементів таких, що неправильно розташовані, якщо такі елементи будуть, то ми їх переставляємо і Flag присвоюємо значення true}

For і:=1 to N–k do

If Mas[i]>Mas[i+1] Then

Begin

{Обмін елементів масиву через третю змінну}

Rez:=Mas[i];

Mas[і]:=Mas[i+1];

Mas[i+1]:=Rez;

Flag:=true;

End;

k:=k–1;

Until Flag = false;

End.

 

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

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

Program Selection;

Const N=20;

Var Mas:array[1..N] of integer;

і, j, Min, N_Min:integer;

Begin

For i:=1 to N–1 do

Begin

Min:=Mas[x]; {Зберігання еталону мінімуму}

N_Min:=i; {Зберігання номера мінімуму}

For j:=i+1 to N do

If Mas[j]

Begin

Min:=Mas[j]; {Перевизначекня еталону}

N_Min:=j; {Зберігання номеру еталону}

End;

{Обмін місцями мінімуму та першого елементу підмасиву}

Mas[N_Min]:=Mas[i];

Mas[i]:=Min;

End;

End.

Зверніть увагу, що пошук мінімуму в програмі організований стандартно, тобто перший елемент береться за еталон, а потім порівнюється з усіма останніми і, якщо новий елемент виявляється меншим за еталон, то еталон переприсвоюється. Крім цього, в алгоритмі запам’ятовується місце знаходження цього мінімального елемента для того, щоб після виходу з циклу можна було обміняти місцями знайдений мінімум і перший елемент підмасиву. Але оскільки підмасив увесь час змінює свій розмір, за еталон береться перший елемент саме того підмасиву, який розглядається на наступному кроці, тобто i-ий елемент початкового масиву
(і – змінна зовнішнього циклу, що вказує на початок нового підмасиву на кожному кроці).

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

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

12 -8 0 30 5 100

Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої – всі останні {-8 0 30 5 100}. Запишемо тепер процес впорядкування по етапах:

І етап: елемент, що впорядковується = -8.

1) -8 <>

-8 12 0 30 5 100

На цьому цикл припиняє свою роботу, тому що досягнуто початку масиву (і=1).

II етап: елемент, що впорядковується = 0.

1) 0 <>

-8 0 12 30 5 100

2) 0 > -8, значить обмін не виконується, здійснюється вихід із циклу, масив залишається без змін.

III етап: елемент, що впорядковується = 30.

1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін.

IV етап: елемент, що впорядковується = 5.

1) 5 <>

–8 0 12 5 30 100

2) 5 <>

–8 0 5 12 30 100

3) 5 > 0, цикл припиняє свою роботу, масив залишається без змін.

V етап: елемент, що впорядковується = 100.

1) 100 <>

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

Program Insert;

Const N=20;

Var Mas:array[1..N] of integer;

і, j, Rez:integer;

Begin

For i:=2 to N do

Begin

j:=i; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початок масиву}

While (j>1) and (Mas[j] <>

Begin

Rez:=Mas[j]; Mas[j]:=Mas[j–1]; Mas[j–1]:=Rez; j:=j–1;

End;

End;

End.

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.