русс | укр

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

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


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


Задачі для самостійного розв’яування


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


Задача 16. Змінити алгоритм GivenItemOrd3 таким чином, щоб він шукав те місце в множині A = {a1, a2, a3} , куди потрібно вставити елемент b так, щоб вона залишилася упорядкованою: A1 = A È {b} .

Задача 17. Скласти алгоритм вибору елемента, рівного даному, в упорядкованій множині з 7-и елементів. Скільки кроків порівняння виконує Ваш алгоритм?

 

6.6. Задачі упорядкування

6.6.1. Упорядкування елементів

Задача 18. Дано два елементи a і b. У задачі потрібно упорядкувати їх за зростанням, тобто скласти алгоритм, що виконує «одночасно» дві дії: a := Min(a, b), b := Max(a, b).

Розв’язання оформимо у вигляді процедури

 

Procedure OrdPair(var a, b : Real);

Var

temp : Real;

Begin

If a > b

Then begin

temp := a;

a := b;

b := temp

end

End;

Змінна temp у цьому алгоритмі відіграє роль тимчасового сховища для значення змінної a. Перестановка двох елементів часто використовується в алгоритмах сортування. Для позначення відповідної процедури використовується ім'я Swap.

 

Procedure Swap(var a, b : Real);

Var

temp : Real;

Begin

temp := a;

a := b;

b := temp

End;

 

Процедура OrdPair тепер може бути записана більш компактно

 

Procedure OrdPair(var a, b : Real);

Begin

If a > b

Then Swap(a, b)

End;

 

Задача 19. Упорядкувати три елементи a, b, c за зростанням.

Розв’язання . Використовуємо алгоритм упорядкування двох елементів.

 

Procedure OrdTriple(var a, b, c : Real);

Begin

{1} OrdPair(a, b); {2} OrdPair(b, c);

{3} OrdPair(a, b);

End;

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

Після виконання першого оператора OrdPair(a, b) a <= b. Після виконання другого оператора OrdPair(b, c) b <= c. Тому с – максимальний з трьох елементів. Ці два оператори «виштовхують» найбільший елемент у змінну с.

У результаті виконання третього оператора OrdPair(a, b) a <= b. Тому b – максимальний з елементів a, b. Цей оператор «виштовхує» другий по величині елемент у змінну b. Найменший з трьох елементів став значенням a.

 

Задача 20. Упорядкувати чотири елементи a1, a2, a3, a4 за зростанням.

Розв’язання. Використовуємо той самий метод, що і при упорядкуванні трьох елементів.

 

Procedure OrdQuadriple(var a1, a2, a3, a4 : Real);

Begin

{1} OrdPair(a1, a2); OrdPair(a2, a3); OrdPair(a3, a4);

{2} OrdPair(a1, a2); OrdPair(a2, a3);

{3} OrdPair(a1, a2);

End;

 

Питання для аналізу алгоритму

Що відбудеться в результаті виконання дій, записаних у першому рядку алгоритму?

Що відбудеться в результаті виконання дій, записаних у другому рядку алгоритму?

Що відбудеться в результаті виконання дії, яка записана в третьому рядку алгоритму?

Скільки порівнянь виконує алгоритм?

Скільки перестановок виконує алгоритм?

Якими повинні бути вихідні значення змінних а1, а2, а3, а4 для того, щоб кількість перестановок була максимальною?

Як змінити алгоритм для того, щоб він упорядковував 5 елементів?

6.6.2. Порівняння, перестановки і пересилання

Кількість порівнянь, які виконує алгоритм у гіршому випадку, позначається функцією С(n). Аргументом цієї функції є кількість вихідних даних, що оброблюються алгоритмом.

Так, в алгоритмі OrdQuadriple n = 4, a C(4) = 6.

В алгоритмі Middle пошуку середнього за величиною з трьох елементів n = 3. Величина С залежить від варіанта взаємного розташування даних: у варіантах 3 і 5 потрібні 2 порівняння а в інших – 3. Таким чином, С(3) = 3.

У задачах упорядкування (сортування) ефективність алгоритмів за часом оцінюється не тільки за кількістю порівнянь, але і за кількістю пересилань. Пересиланням називають дію, яка виконується оператором присвоювання a := b. Так, процедура Swap виконує три пересилання. Оскільки алгоритм упорядкування трьох елементів OrdTriple у гіршому випадку виконує три перестановки, у цьому випадку виконується 9 пересилань. Кількість пересилань, що виконує алгоритм у гіршому випадку, позначається функцією М(n). Аргументом цієї функції також є кількість вихідних даних, які оброблюються алгоритмом.

Звичайно в алгоритмах упорядкування всі дії виконуються «на місці». Це означає, що допоміжні змінні алгоритму відіграють роль тимчасового сховища (як змінна Temp в алгоритмі Swap). У цьому випадку функція М(n) може позначати кількість перестановок.


<== попередня лекція | наступна лекція ==>
Задачі для самостійного розв’язування. | Задачі для самостійного розв’язування


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