Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Сортування масивів
|
|
Розглянемо масив елементів а1, а2, а3, …, аn. Нехай потрібно переставити елементи цього масиву так, щоб після перестановки вони були упорядковані за неубуванням: а1 
а2 … аn. Ця задача називається задачею сортування чи упорядкування масиву. Для розв’язання цієї задачі можна скористатися, наприклад, такими алгоритмами:
1 Знайти елемент масиву, що має найменше значення, переставити його з першим елементом, потім проробити теж саме, почавши з другого елемента і т.д. (сортування вибором).
2 Послідовним переглядом елементів а1, …, аn знайти найменше i таке, що аi> ai+1. Поміняти ai і аi+1 місцями, відновити перегляд з елемента аi+1 і т.д. Тим самим найбільший елемент пересунеться на останнє місце. Наступні перегляди починати знову спочатку, зменшуючи на одиницю кількість елементів, що переглядаються (сортування обміном або методом пухирця).
3 Переглядати послідовно а2, а3, …, аn і кожен новий елемент аi вставляти на придатне місце у вже упорядковану сукупність а1, а2, а3,..., аi-1. Це місце визначається послідовним порівнянням аi з упорядкованими елементами а1, а2,..., аi-1 (сортування вставками).
Якщо потрібно відсортувати частину масиву, що задовольняє заданим умовам, то спочатку відбирають елементи, що задовольняють заданій умові, у робочий масив, а потім його сортують.
Приклади виконання завдання лабораторної роботи
Приклад 17. Сформувати новий масив з позитивних елементів вихідного масиву x(15).
Порядок роботи:
Крок 1. Уводимо масив x(15).
Крок 2. Установлюємо вихідний індекс робочого масиву j=0.
Крок 3. Організовуємо цикл, що перебирає елементи вихідного масиву (тобто індекс i), починаючи з 1-го і кінчаючи 15-м.
Крок 4. Якщо xi £ 0, то йдемо на крок 7.
Крок 5. Встановлюємо індекс наступного елемента робочого масиву j = j + 1.
Крок 6. Привласнюємо елементу робочого масиву значення елемента вихідного масиву yj = xi.
Крок 7. Якщо цикл по i не закінчився, йдемо на початок циклу, тобто на крок 3.
Крок 8. Друкуємо j елементів робочого масиву y.
Крок 9. Останов.
Приклад 18. Сформувати і вивести на друк два масиви, що містять значення й індекси від’ємних елементів вихідного масиву В(15).
Програма розв’язання даного прикладу має вид:
program pr18;
uses Crt;
const N=15;
type Mas1=array[1..N] of real;
Mas2=array[1..N] of integer;
VAR B, X: MAS1; Y: MAS2; I, J: INTEGER; P: CHAR;
BEGIN CLRSCR;
WRITELN(' УВЕДІТЬ ', N, ' ЧИСЕЛ');
FOR I: =1 TO N DO READ(B[I]);
WRITELN(' ': 20, 'ВИХІДНИЙ МАСИВ');
for i: =1 to N do write(b[i]: 5: 1);
writeln;
j: =0;
for i: =1 to N do begin
if b[i]< 0 then
begin
j: =j+1; x[j]: =b[i]; y[j]: =i;
end;
END;
WRITELN(' ': 10, 'НОВІ МАСИВИ');
if j> 0 then for i: =1 to j do
writeln(' ': 5, 'x(', i, ')=', x[i]: 5: 1, 'y(', i, ')=', y[i]: 2)
else WRITELN(' ТАКИХ ЕЛЕМЕНТІВ НЕМА);
p: =readkey
end.
Приклад 19. Знайти суму двох найбільших негативних елементів масиву x(15).
Порядок роботи:
Крок 1. Уводимо масив x(15).
Крок 2. Установлюємо вихідний індекс робочого масиву j=0.
Крок 3. Організовуємо цикл, що перебирає елементи вихідного масиву (тобто індекс i), починаючи з 1-го і кінчаючи 15-м.
Крок 4. Якщо xi ³ 0, то йдемо на крок 7.
Крок 5. Встановлюємо індекс наступного елемента робочого масиву j = j + 1.
Крок 6. Привласнюємо елементу робочого масиву значення елемента вихідного масиву yj = xi.
Крок 7. Якщо цикл за i не закінчився, йдемо на початок циклу, тобто на крок 3.
Крок 8. Якщо j < 2, то видаємо повідомлення «Масив не сформований» і йдемо на крок 17.
Крок 9. Організовуємо цикл, що визначає кількість переглядів робочого масиву (тобто індекс k), починаючи з 1-го і кінчаючи j-м.
Крок 10. Організовуємо цикл, що визначає пару елементів робочого масиву, що переглядається, (тобто індекс i), починаючи з 1-го і кінчаючи (j-1) -м.
Крок 11. Якщо перший елемент не більше другого, то йдемо на крок 13.
Крок 12. Змінюємо два елемента місцями:
c = yi; yi = yi+1; yi+1 = c.
Крок 13. Якщо цикл по i не закінчився, йдемо на початок циклу, тобто на крок 10.
Крок 14. Якщо цикл за k не закінчився, йдемо на початок циклу, тобто на крок 9.
Крок 15. Обчислюємо суму s = yj + yj-1.
Крок 16. Друкуємо s.
Крок 17. Останов.
Приклад 20. Знайти добуток чотирьох найменших додатних кратних 5 елементів вихідного масиву Х(20).
Спочатку формуємо новий масив з додатних кратних 5 елементів вихідного масиву, а потім отриманий масив сортуємо методом виштовхування (пухирця). Програма має вид:
program pr20;
uses crt;
LABEL 1;
const n=20;
type raz=1..N; mac=array [raz] of integer;
var x, a: mac; d, i, j, k, r: integer; p: char;
BEGIN CLRSCR; WRITELN('УВЕДИ ', N, ' ЧИСЕЛ');
FOR I: =1 TO N DO READ(X[I]);
WRITELN(' ': 20, 'ВИХІДНИЙ МАСИВ');
FOR I: =1 TO N DO WRITE(X[I]: 4);
{ ФОРМУВАННЯ НОВОГО МАСИВУ }
writeln; j: =0;
for i: = 1 to N do begin
IF (X[I]> 0) AND (X[I] MOD 5 = 0) THEN
BEGIN J: =J+1; A[J]: =X[I]; END; END;
IF J=0 THEN WRITELN(‘ МАСИВ НЕ СФОРМОВАНО’): goto 1;
{ СОРТУВАННЯ ПО ЗРОСТАННЮ }
for k: = 1 to j do
for i: = 1 to j-k do
if a[i+1]< a[i] then
BEGIN D: =A[I]; A[I]: =A[I+1]; A[I+1]: =D; END;
WRITELN(' ': 5, 'ВІДСОРТОВАНИЙ МАСИВ');
for i: = 1 to j do write(a[i]: 4); writeln;
if j> =4 then begin r: =1;
for i: =1 to 4 do r: =r*a[i];
WRITELN('ДОБУТОК 4- Х НАЙМЕНШИХ=', R: 6); end
ELSE WRITELN(‘Масив не містить 4 додатних кратних 5 елементів’);
1: p: =readkey
end.
|
|