русс | укр

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

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


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


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


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


Задача 9. Дано три однакові на зовнішній вигляд монети. Відомо, що серед них є одна фальшива, котра трохи відрізняється за вагою від справжніх. Знайти за допомогою чашкових терезів фальшиву монету, якщо невідомо, легше вона, ніж справжні, або важче.

Задача 10. Дано чотири однакові на зовнішній вигляд монети. Відомо, що серед них є одна фальшива, яка трохи відрізняється за вагою від справжніх. Знайти за допомогою чашкових терезів фальшиву монету, якщо

відомо, що вона легше, ніж справжні.

невідомо, легше вона, ніж справжні, або важче.

Задача 11. Дано 8 однакових на зовнішній вигляд монет. Відомо, що серед них є одна фальшива, яка легше, ніж справжні. Знайти за допомогою чашкових терезів фальшиву монету.

Задача 12. Дано 12 однакових на зовнішній вигляд монет. Відомо, що серед них є одна фальшива, яка трохи відрізняється за вагою від справжніх. Знайти за допомогою чашкових терезів фальшиву монету, якщо невідомо, легше вона, ніж справжні, або важче.

6.5.4. Ефективність алгоритму як кількість його кроків

Важливу роль при визначенні якості комп'ютерної програми грає час її виконання. Час виконання комп'ютерної програми залежить від багатьох факторів, які можна розділити на дві основні групи: технічні характеристики обчислювальної системи (комп'ютера і системного програмного забезпечення) і технічні характеристики власне прикладної комп'ютерної програми. Оскільки кожна прикладна програма є реалізацією алгоритму, на час її виконання впливає в першу чергу кількість кроків її алгоритму.

Алгоритм розв’язування прикладної задачі називають ефективним за часом, якщо він розв’язує цю задачу за найменшу можливу кількість кроків.

В алгоритмах вибору кроком є порівняння. Тому мірою ефективності алгоритму вибору є кількість порівнянь, які виконуються в ньому. Як ми бачили при розв’язуванні задачі 7, ця величина залежить не тільки від алгоритму, але і від того варіанта вихідних даних, що обробляє алгоритм у даному випадку. При визначенні ефективності алгоритму часто використовують кількість його кроків у гіршому випадку, тобто при найбільш несприятливому варіанті виборі вихідних даних.

6.5.5. Вибір даного елемента

Один з розповсюджених варіантів задачі вибору – вибір одного (даного) елемента з декількох.

Нехай A = {a1, a2, . . ., ak} – деяка множина елементів і b – даний елемент. У задачі потрібно дізнатися, чи знаходиться в множині A елемент, рівний b чи ні. Якщо в множині A такий елемент знайдеться, алгоритм повинен знайти його місце.

Розглянемо розв’язання цієї задачі для множини з 3-х елементів.

 

Задача 13. Вибір останнього елемента, рівного даному, у множині з трьох елементів.

Текст процедури мовою Паскаль:

 

Procedure LastGivenItems3 ( a1, a2, a3, b: Real; Var Found: Boolean;
Var Location: Integer);

Begin

Found := False;

If a1 = b

then begin

Location = 1;

Found := True

end;

If a2 = b then begin

Location = 2;

Found := True

end;

If a3 = b then begin

Location = 3;

Found := True

end;

End;

Цей варіант алгоритму вибирає останнє входження елемента b у множину {a1, a1, a3}. У другому варіанті – алгоритмі FirstGivenItem3 шукається тільки одне – перше входження b у {a1, a1, a3}.

 

Задача 14. Вибір першого елемента, рівного даному, у наборі з трьох елементів.

Текст процедури мовою Паскаль:

 

Procedure FirstGivenItem3 ( a1, a2, a3, b: Real; Var Found: Boolean;
Var Location: Integer);

Begin

Found := False;

If a1 = b

then begin

Location = 1;

Found := True

end

else If a2 = b

then begin

Location = 2;

Found := True

end

else If a3 = b

then begin

Location = 3;

Found := True

end;

End;

 

Якщо перший алгоритм завжди виконує 3 кроки порівнянь, другий – один, два або три в залежності від результату вибору на попередніх кроках. Тому другий алгоритм «у середньому» працює швидше.

На закінчення розглянемо варіант задачі вибору даного з трьох елементів у випадку, коли a1 < a2 < a3. Виявляється, що в цьому випадку зручно застосувати функцію Сompare(a, b), причому починати порівняння потрібно із середнього елемента.

 

Задача 15. Вибір елемента, рівного даному, в упорядкованій множині з трьох елементів {a1 < a2 < a3}.

Текст процедури мовою Паскаль:

 

Procedure GivenItemOrd3 (a1, a2, a3, b: Real; Var Found: Boolean;
Var Location: Integer);

Begin

Case Compare(a2, b) + 1 of

0 : case Compare(a1, b) + 1 of

0, 2: Found := False;

1: begin

Found := True;

Location := 1

end;

end;

1: begin

Found := True;

Location := 2

end;

2: case Compare(a3, b) + 1 of

0, 2: Found := False;

1: begin

Found := True;

Location := 3

end;

end;

end

End;

 

Неважко переконатися в тому, що цей алгоритм завжди виконує 2 кроки порівняння, причому це стало можливим тільки тому, що множина A = {a1, a2, a3} упорядкована. У протилежному випадку алгоритм працює неправильно.


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


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