Презентація на тему:
Вступ до програмування на мові Паскаль

Програмування на мові Паскаль Тема 1. Вступ

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

Програма Програма – це алгоритм, записаний на будь-якій мові програмування набір команд для комп’ютера Команда – це опис дій, які повинен виконати комп’ютер. звідки отримати вихідні дані? що потрібно з ними зробити?

Мови програмування Машинно-орієнтовані (низького рівня) – кожна команда відповідає одній команді процесора (асемблер) Мови високого рівня – наближені до реальної (англійської) мови, легше сприймаються людиною, не залежать від відповідного комп’ютера для навчання: Бейсик, ЛОГО, Паскаль професійні: Сі, Фортран, Паскаль для задач штучного інтелекту: Пролог, ЛИСП для Інтернету: JavaScript, Java, Perl, PHP, ASP

Мова Паскаль 1970 – Ніклаус Вірт (Швейцарія) мова для навчання студентів розробка програм “зверху-вниз” різноманітні структури даних (масиви, структури, множини)

З чого складається програма? program ; const …;{константи} var …; {змінні} begin … {основна програма} end. { процедури і функції } коментарі у фігурних дужках не опрацьовуються

З чого складається програма? Константа – постійна величина, яка має ім’я. Змінна – змінна величина, яка має ім’я (комірка пам’яті). Процедура – додатковий алгоритм, який описує деякі дії (малювання кола). Функція – додатковий алгоритм, для виконання обчислень (обчислення квадратного кореня, sin).

Імена програм, констант, змінних Імена можуть містити латинські букви (A-Z) цифри знак підкреслення _ великі і маленькі букви не розрізняються Імена НЕ можуть містити українські букви пропуски дужки, знаки +, =, !, ? та ін. ім’я не може починатися з цифри Які імена правильні? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

Константи const i2 = 45; { ціле число } pi = 3.14; { дійсне число } qq = 'Вася'; { рядок символів } L = True; { логічна величина } ціла і дробова частина відділяються крапкою можна використовувати українські букви! Може приймати два значення: True (істина, “так") False (хибність, "ні")

Змінні Змінна – це величина, яка має ім’я, тип і значення. Значення змінної величини під час виконання програми може змінюватися. Типи змінних: integer { цілі } real { дійсні } char { один символ } string { рядок } boolean { логічні } Оголошення змінних (виділення пам’яті): var a, b: integer; Q: real; s1, s2: string;

Як змінюється значення змінної? Оператор – це команда мови програмування високого рівня. Оператор присвоєння служить для зміни значення змінної. Приклад: program qq; var a, b: integer; begin a := 5; b := a + 2; a := (a + 2)*(b – 3); end. a ? 5 5 b ? 5+2 7 a 5 7*4 28

Оператор присвоєння Загальна структура: := ; Арифметичні вирази можуть містити константи імена змінних знаки арифметичних дій: + - * / div mod виклики функцій круглі дужки ( ) множення ділення ділення націло остача від ділення

program qq; var a, b: integer; x, y: real; begin a := 5; 10 := x; y := 7,8; b := 2.5; x := 2*(a + y); a := b + x; end. Які оператори неправильні? ім’я змінної повинно знаходитися зліва від знака := ціла і дробова частина відділяються крапкою неможливо записати дійсне значення в цілу змінну

Ручна прокрутка програми program qq; var a, b: integer; begin a := 5; b := a + 2; a := (a + 2)*(b – 3); b := a div 5; a := a mod b; a := a + 1; b := (a + 14) mod 7; end. a b ? ? 5 7 28 5 3 4 4

Порядок виконання операцій обчислення виразів у дужках множення, ділення, div, mod зліва направо додаванні і віднімання зліва направо 2 3 5 4 1 7 8 6 9 z := (5*a*c+3*(c-d))/a*(b-c)/ b; 2 6 3 4 7 5 1 12 8 11 10 9 x:=(a*a+5*c*c-d*(a+b))/((c+d)*(d-2*a));

Додавання двох чисел Задача. Ввести два цілих числа і вивести на екран їх суму. Найпростіше розв’язання: program qq; var a, b, c: integer; begin read ( a, b ); c := a + b; writeln ( c ); end.

Оператор введення read ( a ); { ввести значення змінної a} read ( a, b ); { ввести значення змінних a і b} Як вводяться два числа? через пропуск: 25 30 через Enter: 25 30

Оператор виведення write ( a ); { вивести значення змінної a} writeln ( a ); { вивести значення змінної a і перейти на новий рядок} writeln ( ‘Привіт!' ); { виведення тексту} writeln ( ‘Відповідь: ', c ); {виведення тексту і значення змінної c} writeln ( a, '+', b, '=', c );

Формати виведення program qq; var i: integer; x: real; begin i := 15; writeln ( '>', i, '', i:5, '', x, '', x:10, '', x:7:2, '

Повний розв’язок program qq; var a, b, c: integer; begin writeln(‘Ввести два цілих числа'); read ( a, b ); c := a + b; writeln ( a, '+', b, '=', c ); end. Протокол: Ввести два цілих числа 25 30 25+30=55 це виводить комп'ютер це вводить користувач

Блок-схема лінійного алгоритму початок кінець c := a + b; ввести a, b вивести c блок «початок» блок «ввести» блок «процес» блок «вивести» блок «кінець»

Завдання "4": Ввести три числа, знайти їх суму і добуток. Приклад: Ввести три числа: 4 5 7 4+5+7=16 4*5*7=140 "5": Ввести три числа, знайти їх суму, добуток і середнє арифметичне. Приклад: Ввести три числа: 4 5 7 4+5+7=16 4*5*7=140 (4+5+7)/3=5.33

Програмування на мові Паскаль Тема 2. Розгалуження

Алгоритми розгалуження Задача. Ввести два цілих числа і вивести на екран більше з них. Ідея розв’язання: потрібно вивести на екран перше число, якщо воно більше другого, або друге, якщо воно більше першого. Особливості: дії виконавця залежать від деяких умов (якщо … інакше …). Алгоритми, в яких послідовність кроків залежить від виконання деяких умов, називаються розгалуженими.

Варіант 1. Блок-схема повна форма розгалуження блок «логічний вираз»

Варіант 1. Програма program qq; var a, b, max: integer; begin writeln(‘Ввести два цілих числа'); read ( a, b ); if a > b then begin end else begin end; writeln (‘Більше число ', max); end. max := a; max := b; повна форма умовного оператора

Умовний оператор if then begin {що робити, якщо умова правильна} end else begin {що робити, якщо умова неправильна} end; Особливості: перед else НЕ ставиться крапка з комою друга частина (else …) може бути відсутня (неповна форма) якщо в блоці один оператор, можна забрати слова begin і end

Що неправильно? if a > b then begin a := b; end else b := a; end; if a > b then begin a := b; else begin b := a; end; if a > b then begin a := b; end; else begin b := a; end; if a > b then begin a := b; end else b > a begin b := a; end; begin end begin end

Варіант 2. Блок-схема неповна форма розгалуження

Варіант 2. Програма program qq; var a, b, max: integer; begin writeln(‘Ввести два цілих числа'); read ( a, b ); max := a; if b > a then writeln (‘Більше число ', max); end. max := b; неповна форма умовного оператора

Варіант 2Б. Програма program qq; var a, b, max: integer; begin writeln(‘Ввести два цілих числа'); read ( a, b ); max := b; if ??? then ??? writeln (‘Більше число ', max); end. max := a; a > b

Що неправильно? if a > b then begin a := b; else b := a; if a > b then begin a := b; end; else b := a; if a > b then else begin b := a; end; if a > b then a := b; else b := a; end; a := b end a := b if b >= a then b := a;

Завдання "4": Ввести три числа і знайти найбільше з них. Приклад: Ввести три числа: 4 15 9 Найбільше число 15 "5": Ввести п’ять чисел і знайти найбільше з них. Приклад: Ввести п’ять чисел: 4 15 9 56 4 Найбільше число 56

Складені умови Задача. Фірма набирає співробітників від 25 до 40 років включно. Ввести вік людини і визначити, чи підходить вона фірмі (вивести відповідь “підходить” або “не підходить”). Особливості: потрібно перевірити, виконання двох умов одночасно.

Варіант 1. Алгоритм початок ввести x ‘підходить' кінець так ні x >= 25? так ні x

Варіант 1. Програма program qq; var x: integer; begin writeln(‘Ввести вік'); read ( x ); if x >= 25 then if x

Варіант 2. Алгоритм початок ввести x ‘підходить' так ні x >= 25 і x

Варіант 2. Програма program qq; var x: integer; begin writeln(‘Ввести вік'); read ( x ); if (x >= 25) and (x

Складена умова Складена умова – це умова, яка складається з декількох простих умов (відношень), зв’язаних з допомогою логічних операцій: not – НІ (заперечення, інверсія) and – І (логічне множення, кон'юнкція, одночасне виконання умов) or – АБО (логічне додавання, диз'юнкція, виконання хоча б одної з умов) xor – виключаюче АБО (виконання тільки одної з двох умов, але не обох) Прості умови (відношення) < >= = дорівнює не дорівнює

Складена умова Порядок виконання вирази в дужках not and or, xor =, =, Особливості – кожна з простих умов обов'язково береться в дужки. Приклад 4 1 6 2 5 3 if not (a > b) or (c d) and (b a) then begin ... end

Істинне чи хибне при a := 2; b := 3; c := 4; not (a > b) (a < b) and (b < c) not (a >= b) or (c = d) (a < c) or (b < c) and (b < a) (a < b) xor not (b > c) Для яких значень x істинні умови: (x < 6) and (x < 10) (x < 6) and (x > 10) (x > 6) and (x < 10) (x > 6) and (x > 10) (x < 6) or (x < 10) (x < 6) or (x > 10) (x > 6) or (x < 10) (x > 6) or (x > 10) Складена умова True True FALSE (- , 6) (6, 10) (10, ) (- , 10) (- , 6) (10, ) (- , ) (6, ) x < 6 x > 10 x < 10 x > 6 True True

Завдання "4": Ввести номер місяця і вивести назву пори року. Приклад: Ввести номер місяця: 4 весна "5": Ввести вік людини (від 1 до 150 років) и вивести його разом з наступним слово “рік”, “роки" або “років". Приклад: Ввести вік: Ввести вік: 24 57 Вам 24 роки Вам 57 років

Оператор вибору Задача: Ввести номер місяця і вивести кількість днів в цьому місяці. Розв’язання: Кількість днів у місяцях: 28 днів – 2 (лютий) 30 днів – 4 (квітень), 6 (червень), 9 (вересень), 11 (листопад) 31 день – 1 (січень), 3 (березень), 5 (травень), 7 (липень), 8 (серпень), 10 (жовтень), 12 (грудень) Особливості: Вибір не з двох, а з декількох варіантів в залежності від номера місяця.

Алгоритм початок кінець оператор вибору жоден з варіантів не підійшов ввести M так ні M = 1? D := 31; ні M = 2? D := 28; так ні M = 12? D := 31; так вивести D помилка

Програма program qq; var M, D: integer; begin writeln(‘Ввести номер місяця:'); read ( M ); case M of 2: begin D := 28; end; 4,6,9,11: begin D := 30; end; 1,3,5,7,8,10,12: D := 31; else D := -1; end; if D > 0 then writeln(‘В цьому місяці ', D, ' днів.') else writeln(‘Неправильний номер місяця'); end. жоден варіант не підійшов

Оператор вибору Особливості: після case може бути ім’я змінної або арифметичний вираз цілого типу (integer) або символьного типу (char) case i+3 of 1: begin a := b; end; 2: begin a := c; end; end; var c: char; ... case c of 'а': writeln('Антилопа'); 'б': writeln('Борсук'); else writeln('Не знаю'); end;

Оператор вибору Особливості: якщо потрібно виконати тільки один оператор, слова begin і end можна не писати не можна ставити два однакових значення case i+3 of 1: a := b; 1: a := c; end; case i+3 of 1: a := b; 2: a := c; end;

Оператор вибору Особливості: значення, при яких виконуються однакові дії, можна групувати case i of 1: a := b; 2,4,6: a := c; 10..15: a := d; 20,21,25..30: a := e; else writeln(‘Помилка'); end; перечислення діапазон суміш

Що неправильно? case a of 2: begin a := b; 4: a := c; end; case a of 2: a := b 4: a := c end; ; case a of 2..5: a := b; 4: a := c; end; case a of 0..2: a := b; 6..3: a := c; end; 3..6: case a+c/2 of 2: a := b; 4: a := c; end; case a of 2: a := b; d := 0; 4: a := c; end; begin end;

Завдання (з захистом від неправильного введення) "4": Ввести номер місяця і вивести кількість днів в ньому, а також кількість помилок при введенні. Приклад: Введіть номер місяця: Введіть номер місяця: -2 2 Введіть номер місяця: В цьому місяці 28 днів. 11 Ви вводили неправильно 0 раз. В цьому місяці 30 днів. Ви вводили неправильно 1 раз. "5": Ввести номер місяця і номер дня, вивести кількість днів, які залишилися до Нового року. Приклад: Ввести номер місяця: 12 Ввести день: 25 До Нового року залишилося 6 днів.

Програмування на мові Паскаль Тема 3. Цикли з умовою

Цикл з невідомою кількістю кроків Приклад: Відрізати поліно від колоди. Скільки разів потрібно зробити рух пилкою? Задача: Ввести ціле число (

Алгоритм початок count кінець ні так n 0? count := 0; count := count + 1; n := n div 10; обнулити лічильник цифр ввести n виконувати "поки n 0"

Програма program qq; var n, count: integer; begin writeln(‘Ввести ціле число'); read(n); count := 0; while n 0 do begin count := count + 1; n := n div 10; end; writeln('В числі ', n, ' знайшли ', count, ' цифр'); end. , n1: integer; n1 := n; n1, виконувати "поки n 0"

Цикл с умовою while do begin {тіло циклу} end; Особливості: можна використовувати складені умови: якщо в тілі циклу тільки один оператор, слова begin і end можна не писати: while (a

Цикл з умовою Особливості: умова перевіряється кожен раз при вході в цикл якщо умова на вході в цикл хибна, цикл не виконується жодного разу якщо умова ніколи не стане хибною, програма зациклиться a := 4; b := 6; while a > b do a := a – b; a := 4; b := 6; while a < b do d := a + b;

Скільки разів виконується цикл? a := 4; b := 6; while a < b do a := a + 1; 2 рази a = 6 a := 4; b := 6; while a < b do a := a + b; 1 раз a = 10 a := 4; b := 6; while a > b do a := a + 1; 0 разів a = 4 a := 4; b := 6; while a < b do b := a - b; 1 раз b = -2 a := 4; b := 6; while a < b do a := a - 1; зациклювання

Заміна for на while і навпаки for i:=1 to 10 do begin {тіло циклу} end; i := 1; while i = b do begin {тіло циклу} i := i - 1; end; Заміна while на for можлива тільки тоді, коли можна наперед розрахувати кількість кроків циклу. Заміна циклу for на while можлива завжди.

Завдання "4": Ввести ціле число і знайти суму його цифр. Приклад: Ввести ціле число: 1234 Сума цифр числа 1234 рівна 10. "5": Ввести ціле число і визначити, чи правда, що в його записі є дві однакові цифри. Приклад: Ввести ціле число: Ввести ціле число: 1234 1224 Ні. Так.

Послідовності Приклади: 1, 2, 3, 4, 5, … 1, 2, 4, 7, 11, 16, … 1, 2, 4, 8, 16, 32, … an = n a1 = 1, an+1 = an+1 a1 = 1, an+1 = an + n an = 2n-1 a1 = 1, an+1 = 2an b1 = 1, bn+1 = bn+1 c1 = 2, cn+1 = 2cn

Послідовності Задача: знайти суму всіх елементів послідовності, які по модулю більші 0,001: Елемент послідовності (починаючи з №2): b := b+1; c := 2*c; z := -z; n 1 2 3 4 5 ... b 1 2 3 4 5 ... c 2 4 8 16 32 ... z -1 1 -1 1 -1 ...

Алгоритм початок S кінець ні так |a| > 0.001? S := S + a; S := 0; b := 1; c := 2; z := -1; a := 1; початкове значення a := z*b/c; b := b + 1; c := 2*c; z := -z; перший елемент новий елемент зміни

Програма program qq; var b, c, z: integer; S, a: real; begin S := 0; z := -1; b := 1; c := 2; a := 1; while abs(a) > 0.001 do begin S := S + a; a := z * b / c; z := - z; b := b + 1; c := c * 2; end; writeln('S =', S:10:3); end. перехід до наступного доданка початкове значення збільшення суми розрахунок елемента послідовності

Завдання "4": Знайти суму елементів послідовності з точністю 0,001: Відповідь: S = 1.157 "5": Знайти суму елементів послідовності з точністю 0,001: Відповідь: S = 1.220

Цикл з післяумовою Задача: Ввести ціле додатне число (

Цикл з післяумовою: алгоритм початок кінець так ні n > 0? тіло циклу умова ВИХОДУ блок "типовий процес" ввести n основний алгоритм

Програма program qq; var n: integer; begin repeat writeln(‘Ввести додатне число'); read(n); until n > 0; ... { основний алгоритм } end. until n > 0; умова ВИХОДУ Особливості: тіло циклу завжди виконується хоча б один раз після слова until ("до тих пір, поки не…") ставиться умова ВИХОДУ із циклу

Скільки разів виконується цикл? a := 4; b := 6; repeat a := a + 1; until a > b; 3 рази a = 7 a := 4; b := 6; repeat a := a + b; until a > b; 1 раз a = 10 a := 4; b := 6; repeat a := a + b; until a < b; зациклення a := 4; b := 6; repeat b := a - b; until a < b; 2 рази b = 6 a := 4; b := 6; repeat a := a + 2; until a < b; зациклення

Програмування на мові Паскаль Частина II Тема 4. Масиви

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

Масиви A масив 3 15 НОМЕР елемента масиву (ІНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕННЯ елемента масиву A[2] НОМЕР (ІНДЕКС) елемента масиву: 2 ЗНАЧЕННЯ елемента масиву: 10 5 10 15 20 25 1 2 3 4 5

Оголошення масивів Для чого оголошувати? визначити ім’я масиву визначити тип масиву визначити кількість елементів виділити місце в пам’яті Масив цілих чисел: Розмір через константу: ім’я початковий індекс кінцевий індекс тип елементів var A: array[1.. ] of integer; const N=5; N var A : array[ 1 .. 5 ] of integer ;

Оголошення масивів Масиви інших типів: Інший діапазон індексів: Індекси інших типів: var X, Y: array [1..10] of real; C: array [1..20] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var A: array ['A'..'Z'] of real; B: array [False..True] of integer; ... A['C'] := 3.14259*A['B']; B[False] := B[False] + 1;

Що неправильно? var a: array[10..1] of integer; ... A[5] := 4.5; [1..10] var a: array ['z'..'a'] of integer; ... A['B'] := 15; A['b'] ['a'..'z'] var a: array [0..9] of integer; ... A[10] := 'X';

Масиви Оголошення: Введення з клавіатури: Поелементні операції: Виведення на екран: const N = 5; var a: array[1..N] of integer; i: integer; for i:=1 to N do begin write('a[', i, ']='); read ( a[i] ); end; a[1] = a[2] = a[3] = a[4] = a[5] = 5 12 34 56 13 for i:=1 to N do a[i]:=a[i]*2; writeln('Масив A:'); for i:=1 to N do write(a[i]:4); Масив A: 10 24 68 112 26

Завдання "4": Ввести з клавіатури масив з 5 елементів, знайти середнє арифметичне всіх елементів масиву. Приклад: Введіть п’ять чисел: 4 15 3 10 14 середнє арифметичне 9.200 "5": Ввести з клавіатури масив з 5 елементів, знайти мінімальний з них. Приклад: Введіть п’ять чисел: 4 15 3 10 14 мінімальний елемент 3

Максимальний елемент Задача: знайти в масиві максимальний елемент. Алгоритм: Псевдокод: { вважаємо, що перший елемент – максимальний } for i:=2 to N do if a[i] > { максимального } then { запам’ятати новий максимальний елемент a[i] }

Максимальний елемент max := a[1]; { вважаємо, що перший – максимальний } iMax := 1; for i:=2 to N do { перевіряємо всі решта } if a[i] > max then { знайшли новий максимальний } begin max := a[i]; { запам’ятати a[i] } iMax := i; { запам’ятати i } end; Додатково: як знайти номер максимального елемента? По номеру елемента iMax завжди можна знайти його значення a[iMax]. Тому всюди замінюємо max на a[iMax] і забираємо змінну max. a[iMax]

Програма program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln(‘Вихідний масив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { вважаємо, що перший – максимальний } for i:=2 to N do { перевіряємо всі решта } if a[i] > a[iMax] then { новий максимальний } iMax := i; { запам’ятати i } writeln; {перейти на новий рядок} writeln('Максимальний елемент a[', iMax, ']=', a[iMax]); end; випадкові числа в інтервалі [50,150) пошук максимального

Завдання "4": Заповнити масив з 10 елементів випадковими числами з інтервалу [-10..10] і знайти в ньому максимальний і мінімальний елементи та їх номери. Приклад: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 максимальний a[4]=10 мінімальний a[8]=-10 "5": Заповнити масив з 10 елементів випадковими числами з інтервалу [-10..10] і знайти в ньому два максимальних елементи та їх номери. Пример: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 максимальний a[4]=10, a[7]=8

Інверсія масиву Задача: переставити елементи масиву в зворотному порядку. Алгоритм: поміняти місцями A[1] і A[N], A[2] і A[N-1], … Псевдокод: for i:=1 to N do { поміняти місцями A[i] і A[N+1-i] } сума індексів N+1 N div 2 do 3 5 … 9 7 7 9 … 5 3 1 2 … N-1 N 1 2 … N-1 N

Як переставити елементи? 2 3 1 Задача: поміняти місцями вміст двох чашок. Задача: поміняти місцями вміст двох комірок пам’яті. 4 6 ? 4 6 4 x y c c := x; x := y; y := c; x := y; y := x; 3 2 1

Програма program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заповнити масив } { вивести вихідний масив } for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end; { вивести одержаний масив } end;

Завдання "4": Заповнити масив з 10 елементів випадковими числами з інтервалу [-10..10] і виконати інверсію окремо для 1-ї і 2-ї половини масиву. Приклад: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 Результат: -4 10 3 -5 4 0 1 -10 8 -6 "5": Заповнити масив з 12 елементів випадковими числами з інтервалу [-12..12] і виконати інверсію для кожної третини масиву. Приклад: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 5 7 Результат: 10 3 -5 4 -10 8 -6 -4 7 5 0 1

Циклічний зсув Задача: зсунути елементи масиву на 1 комірку, перший елемент стає на місце останнього. Алгоритм: A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N]; Цикл: for i:=1 to N-1 do A[i]:=A[i+1]; чому не N? 3 5 8 1 … 9 7 1 2 3 4 … N-1 N 5 8 1 … 9 7 3

Програма program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заповнити масив } { вивести вихідний масив } c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c; { вивести одержаний масив } end;

Завдання "4": Заповнити масив з 10 елементів випадковими числами з інтервалу [-10..10] і виконати циклічний зсув ВПРАВО. Приклад: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 Результат: 0 4 -5 3 10 -4 -6 8 -10 1 "5": Заповнити масив з 12 елементів випадковими числами з інтервалу [-12..12] і виконати циклічний зсув ВПРАВО на 4 елементи. Приклад: Вихідний масив: 4 -5 3 10 -4 -6 8 -10 1 0 5 7 Результат: -4 -6 8 -10 1 0 5 7 4 -5 3 10

Сортування Сортування – це розстановка елементів масиву в заданому порядку ( по зростанню, спаданню, останній цифрі, сумі дільників, …). Задача: переставити елементи масиву в порядку зростання. Алгоритми: прості і зрозумілі, проте неефективні для переважної більшості масивів метод бульбашки метод вибору складні, проте ефективні “швидке сортування" (Quick Sort) сортування “купою" (Heap Sort) сортування злиттям пірамідальне сортування складність O(N2) складність O(N·logN)

Метод бульбашки Ідея – бульбашка повітря в стакані води піднімається з дна вверх. Для масивів – самий маленький ("легкий") елемент переміщується вверх ("спливає"). починаємо знизу, порівнюємо два сусідніх елементи; вони стоять “неправильно”, міняємо їх місцями за 1 прохід по масиву один елемент (самий маленький) стає на своє місце 1-ий прохід 2-ий прохід 3-ій прохід Для сортування масиву з N елементів потрібен N-1 прохід (достатньо поставить на свої місця N-1 елемент). 5 2 1 3 5 2 1 3 5 1 2 3 1 5 2 3 1 5 2 3 1 5 2 3 1 2 5 3 1 2 5 3 1 2 3 5

Програма 1-ий прохід: порівнюються пари A[N-1] і A[N], A[N-2] і A[N-1] … A[1] і A[2] A[j] і A[j+1] 2-ий прохід for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 2 for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 1 i-ий прохід for j:=N-1 downto i do ... i 5 2 … 6 3 1 2 … N-1 N 1 5 … 3 6 1 2 … N-1 N

Програма program qq; const N = 10; var A: array[1..N] of integer; i, j, c: integer; begin { заповнити масив } { вивести вихідний масив } for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; end; { вивести одержаний масив } end; i елементи вище A[i] вже поставлені

Метод бульбашки з прапором Ідея – якщо при виконанні методу бульбашки не було обмінів, масив вже посортований і решта проходів не потрібні. Реалізація: змінна-прапор, показує, був чи ні обмін; якщо вона дорівнює False, то вихід. repeat flag := False; { скинути прапор } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { підняти прапор } end; until not flag; { вихід при flag=False } flag := False; flag := True; not flag; var flag: boolean; 2 1 4 3 1 2 3 4

Метод бульбашки з прапором i := 0; repeat i := i + 1; flag := False; { скинути прапор } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { підняти прапор } end; until not flag; { вихід при flag=False } i := 0; i i := i + 1;

Метод вибору Ідея: знайти мінімальний елемент і поставити на місце першого (помінять місцями з A[1]) із решти знайти мінімальний елемент і поставити на друге місце (поміняти місцями з A[2]), і т.д. 4 3 1 2 1 3 4 2 1 2 4 3 1 2 4 3

Метод вибору for i := 1 to N-1 do begin nMin = i ; for j:= i+1 to N do if A[j] < A[nMin] then nMin:=j; if nMin i then begin c:=A[i]; A[i]:=A[nMin]; A[nMin]:=c; end; end; N-1 N потрібен N-1 прохід пошук мінімального від A[i] до A[N] якщо потрібно, переставляємо i+1 i

Завдання "4": Заповнити масив з 10 елементів випадковими числами з інтервалу [0..100] і відсортувати його за останньою цифрою. Приклад: Вихідний масив: 14 25 13 30 76 58 32 11 41 97 Результат: 30 11 41 32 13 14 25 76 97 58 "5": Заповнити масив з 10 елементів випадковими числами з інтервалу [0..100] і відсортувати першу половину по зростанню, а другу – по спаданню. Приклад: Вихідний масив: 14 25 13 30 76 58 32 11 41 97 Результат: 13 14 25 30 76 97 58 41 32 11

Пошук в масиві Задача – знайти в масиві елемент, рівний X, або встановити, що його немає. Розв’язання: для довільного масиву: лінійний пошук (перебір) недостаток: низька швидкість Як спростити? – завчасно підготувати масив для пошуку як саме підготувати? як використовувати “підготовлений масив"?

Лінійний пошук nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; {вихід з циклу} end; nX := 0; { поки не знайшли ...} for i:=1 to N do { цикл по всіх елементах } if A[i] = X then { якщо знайшли, то ... } nX := i; { ... запам’ятати номер} if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); nX – номер потрібного елемента в масиві Покращення: після того, як знайшли X, виходимо з циклу. nX := 0; i := 1; while i

Двійковий пошук X = 7 X < 8 8 4 X > 4 6 X > 6 Вибрати середній елемент A[c] і порівняти з X. Якщо X = A[c], знайшли (вихід). Якщо X < A[c], шукати дальше в першій половині. Якщо X > A[c], шукати дальше в другій половині. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Двійковий пошук nX := 0; L := 1; R := N; {межі: шукаємо від A[1] до A[N] } while R >= L do begin c := (R + L) div 2; if X = A[c] then begin nX := c; R := L - 1; { break; } end; if x < A[c] then R := c - 1; if x > A[c] then L := c + 1; end; if nX < 1 then writeln(‘Не знайшли...') else writeln('A[', nX, ']=', X); номер середнього елемента знайшли вийти з циклу зсуваємо межі 1 L c R N

Порівняння методів пошуку Лінійний Двійковий підготовка ні відсортувати кількість кроків N = 2 2 2 N = 16 16 5 N = 1024 1024 11 N= 1048576 1048576 21 N ≤ N ≤ log2N+1

Завдання "4": Написати програму, яка сортує масив ПО СПАДАННЮ і шукає в ньому елемент, рівний X (це число вводиться з клавіатури). Використати двійковий пошук. "5": Написати програму, яка рахує середню кількість кроків в двійковому пошуку для масиву з 32 елементів з інтервалу [0,100]. Для пошуку використати 1000 випадкових чисел в цьому ж інтервалі.