Задача 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} упорядкована. У протилежному випадку алгоритм працює неправильно.
