1. Оценить временную сложность алгоритма вычисления факториала целого положительного числа, принимая каждую операцию за единицу сложности.
Function F(x: integer): integer;
Var m, i: integer;
Begin m:=1;
For i:=2 to x do m:=m*i;
F:=m;
End;
Сравните полученную оценку временной сложности с временной сложностью рекурсивного алгоритма вычисления факториала и сделайте вывод.
2. Составьте алгоритм вывода на экран всех трехзначных чисел, в записи которых нет ни одной одинаковой цифры. Оцените временную сложность составленного алгоритма.
3.Составьте алгоритм нахождения выражения и оцените его временную сложность.
4. Составьте алгоритм «перевертывания» целого положительного числа n и вычислите его временную сложность, принимая каждую операцию за единицу сложности.
Function Pal(n:Longint):Longint;
Var x:Longint;
Begin
x:=0;
While n<>0 do begin
x:= x*10+n mod 10;
n:= n div 10;
end;
pal:=x;
end;
5. Требуется упорядочить по весу в возрастающем порядке n предметов, имея в своем распоряжении только чашечные весы без гирь. Напишите наиболее эффективный алгоритм решения этой задачи
|
|
Содержание отчета:
Название, цель работы, в тетради должны быть записаны алгоритмы и оценка их сложности, вывод., ответ на вопрос «Какие правила оценки сложности алгоритмы были использованы при решении задач»
Критерии оценок:
«5» - выполнено 5 пунктов
«4» - выполнено 4 пункта
«3» - выполнено 3 пункта
«2» - выполнено менее 3 пунктов.
Литература.
1. Семакин, И.Г. Основы алгоритмизации и программирования. Практикум [Текст]: учеб. пособие / И.Г. Семакин, А.П. Шестаков. - М.:Изд. центр «Академия», 2013-144с.
2. Википедия https://ru.wikipedia.org