русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Аналіз алгоритму сортування вибором


Дата додавання: 2014-11-27; переглядів: 1073.


Внутрішній цикл здійснює пошук мінімального елемента. Після виконання оператора 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.

Оператор циклу з передумовою визначений діаграмою:


<== попередня лекція | наступна лекція ==>
Розділ міток | З передумовою


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн