Внутрішній цикл здійснює пошук мінімального елемента. Після виконання оператора If має місце співвідношення
Min = Min(a[i], a[i+1], ... , a[j]),
а після завершення циклу
Min = Min(a[i], a[i+1], ... , a[n]).
Після перестановки маємо
a[i] = Min(a[i], a[i+1], ... , a[n]).
Зовнішній цикл керує довжиною частини масиву, що переглядається. Після виконання тіла зовнішнього циклу початок масиву вже відсортований:
a[1] £ a[2] £ .... £ a[i]
Після завершення зовнішнього циклу отримаємо:
a[1] £ a[2] £ ... £ a[n-1], a[n-1] = Min(a[n-1], a[n]),
тобто масив відсортований.
Зовнішній цикл виконався n-1 разів. Внутрішній цикл виконується і-1 разів (i = n-1, n-2, ...,1). Кожне виконання тіла внутрішнього циклу складається в одному порівнянні. Тому
C(n) = 1 + 2 + ... + n - 1 = n(n - 1)/2,
Перестановка елементів здійснюється у зовнішньому циклі. Тому
M(n) = 3(n - 1)
Як і алгоритм сортування обмінами, цей алгоритм є стійким. Дійсно, блок пошуку мінімального елемента в хвості масиву шукає мінімальний елемент з найменшим індексом, тому перестановки будуть стійкими. Можна зробити висновок, що просте сортування вибором ефективніше сортування простими обмінами за критерієм M(n). Якщо послідовність, що сортується, складається з даних великого розміру, цей критерій може мати вирішальне значення.
7.13. Задачі і вправи
І.Скласти програму табулювання функції z = f(x, y) у прямокутнику [a, b]*[c, d] з кроком табуляції h і точністю e
|
| Функція z = f(x,y)
| [a, b]
| [c, d]
| h
| e
|
|
| z = ln(1 + x2 + y2)
| [ -2, 3 ]
| [ -1, 3 ]
| 0.1
| 10-5
|
|
| z = sin2(2x+y)
| [ -p, p/2 ]
| [ -2p, p ]
| 0.2
| 10-6
|
|
| z = exp(x2+y2)
| [ -2, 2 ]
| [ -2, 2 ]
| 0.1
| 10-5
|
|
| z = 1/(tg2(x+y)+1)
| [ -p/2, p/2 ]
| [ -p, p ]
| 0.2
| 10-4
|
|
| z = ln(x+sqrt(x2+y2))
| [ -2, 3 ]
| [ -2, 3 ]
| 0.1
| 10-5
|
1. Розробити програму, яка за даним натуральним числом N обчислює N! (0!=1, 1! = 1, при N > 1 N! = 1*2*...*N). Ваша програма повинна контролювати діапазон цілих чисел, для яких вона працює правильно.
2. Послідовність Фібоначчі визначається таким чином: f(0)= 0, f(1) = 1, f(k) = f(k-1) + f(k-2) при k >=2. Розробити програму, яка за даним натуральним числом N обчислює f(N). Ваша програма повинна контролювати діапазон цілих чисел, для яких вона працює правильно.
3. Розробити програму, яка за даним натуральним числом N та дійсним числом x обчислює суму S(N, x) = 1/0! + x/1! + ... + xN/N!. Треба, щоб кількість операцій (виконаних команд присвоєння) була б не більшою ніж C*n для деякої константи С.
4. Розробити програму, яка за даним натуральним числом N та дійсним числом x в єдиному арифметичному циклі обчислює суми
C(N, x) = 1/0! - x2/2! + x4 /4! ... + (-1)N* x 2N/(2N)!.
S(N, x) = x/1! - x3/3! + x5 /5! ... + (-1)N* x 2N+1/(2N+1)!.
Треба, щоб кількість операцій (виконаних команд присвоєння) була б не більшою ніж C*n для деякої константи С.
5. Розробити програму пошуку наближених найбільшого та найменшого значень функції
y = (1/Pi)*Sin(x2/Pi)
на інтервалі [a, b] методом послідовного обчислення значень цієї функції на даному інтервалі з кроком h зміни значень змінної x.
6. Розробити програму наближеного обчислення визначеного інтеграла òf(x)dx на відрізку [a, b] за формулою середніх прямокутників при фіксованому числі N розбиття відрізку інтегрування [a, b] на N рівних частин.
7. Розробити програму, яка за даним додатнім дійсним числом R, даним додатнім натуральним числом p < 10, даним додатнім натуральним числом N обчислює запис R в p-ічній системі числення з точністю 1/pN . Результат потрібно вивести на екран у вигляді
R = a1 a2 ... ak , b1 b2 ... bN (p),
де a1 a2 ... ak - ціла частина, b1 b2 ... bN - дробова частина запису R в p-ічній системі числення з потрібною точністю.
8. Розробити програму, яка за даним натуральним числом N = a1 a2 ... ak формує число M = ak ak-1 ... a1 (число M складається з цифр числа N, розташованими у зворотному порядку). Числа N та M визначте в програмі як дані типу LongInt.
ІІ. Скласти програму розв’язування задачі і оцінити її складність:
9. Дано числовий масив А[1..n]. Знайти суму всіх елементів A, що стоять між A[1] і A[n].
10. Дано числовий масив А[1..n]. Підрахувати середнє арифметичне всіх від’ємних і всіх додатних його елементів.
11. Дано числовий масив А[1..n]. Знайти всі його елементи, менші, ніж всі попередні.
12. Дано числовий масив A[1..n]. Знайти в цьому масиві найбільшу за кількістю елементів зростаючу підпослідовність елементів, що йдуть підряд.
13. Дано числовий масив A[1..n], що складається з непарного (n = 2k+1) числа попарно нерівних елементів. Знайти середній за величиною елемент у масиві.
14. Дано масиви А[1..n] і В[1..m]. Знайти всі елементи масиву A, що не входять у В.
15. Дано масиви А[1..n] і В[1..m]. Знайти всі елементи масиву A, що входять у В.
16. Дано числовий масив A[1..n]. Величину Sij визначимо наступним чином:
Sii = A[i],
Sij = A[i] + A[i+1] + ... + A[j] при i < j
Sij = Sji при i > j
Знайти Max Sij при 1 £ i, j £ n
17. Дано масив А[1..n], елементами якого є цілі числа. Розробити програму пошуку всіх його елементів, менших, ніж всі попередні (іншими словами, потрібно знайти та роздрукувати всі такі індекси j, для яких справедлива умова: для будь-якого i < j A[i] < A[j]).
18. Дано масив A[1..n], елементами якого є дійсні числа. Розробити програму, яка знаходить в цьому масиві найбільшу за кількістю елементів зростаючу підпослідовність елементів, розташованих підряд: a[i] < a[i+1] < . . . < a[j].
19. Дано числовий масив A[1..n], який містить непарну (n = 2k+1) кількість попарно нерівних елементів. Розробити програму, яка шукає середній за величиною елемент в цьому масиві.
20. Дано масив A[1..n], складений з дійсних чисел. Розробити програму, яка шукає в цьому масиві найменше додатне число.
21. Послідовність з n точок площини задана масивами Х[1..n] та Y[1..n] координат цих точок. Розробити програму, яка шукає в цій послідовності точку, наймеш віддалену від початку координат.
22. Елемент A[i] числового масиву A[1..n] називається бар’єрним, якщо
A[j] <= A[i] при j < i та A[j] >= A[i] при j > i.
Розробити програму, яка шукає всі бар’єрні елементи масиву А.
ІІІ. Скласти програму розв’язування задачі і оцінити її складність:
23. Дано числовий масив А[1..n, 1..m]. Знайти сідлову точку масиву або встановити її відсутність. (Елемент двомірного масиву називається сідловою точкою, якщо він максимальний у своєму стовпці і мінімальний у своєму рядку.)
24. Дано числовий масив А[1..n, 1..m]. Знайти стовпець, сума квадратів елементів якого мінімальна.
25. Дано числовий масив А[1..n, 1..m]. Знайти всі елементи А менші, ніж усі сусідні. (Сусідніми називаються елементи, індекси яких відрізняються на 1).
8. ІТЕРАЦІЙНІ ЦИКЛИ
8.1. Оператори повторення While і Repeat
У попередньому параграфі ми вивчили оператор повторення з параметром (For).
Цей оператор використовується лише у випадку, коли заздалегідь відома кількість повторень тіла циклу. У більш загальному випадку, коли кількість повторень заздалегідь невідома, а задана деяка умова закінчення (або продовження) циклу, у мові Pascal використовують інші оператори повторення: оператор циклу з передумовою While і оператор циклу з постумовою Repeat.
Оператор циклу з передумовою визначений діаграмою:
