Теория алгоритмов. Лабораторная работа № 1. Разработка алгоритмов. Лабораторная работа № 2. Разработка эффективных алгоритмов

Теория алгоритмов

Лабораторная работа № 1

Разработка алгоритмов

Разработать линейные, ветвящиеся и циклические алгоритмы вычисления заданных функций и записать их в виде блок-схем.

1. Разработать алгоритм вычисления функции v = f(x, y, z) в виде последовательности элементарных действий

Элементарными считать вычислительные операции +, –, ´, / и операцию сравнения двух чисел.

2. Вычислить таблицу значений функции y = f(a, b, x)

Параметры x и а пробегают интервалы N £ x £ M и M £ a £ T с шагом h.

3. Сгенерировать первые k членов ряда Фибоначчи, рекуррентная формула которого n_i = n_i_-1 + n_i_-2 и два первых члена равны n₀ = 0, n₁ = 1.

4. Для заданных значений k и x вычислить функцию y = при 1 £ k £ 5 и x > 1.

5. Вычислить значения функции P(x) для заданного x, при 0 £ n £ N с шагом 1. P_n(x) задано формулой

6. Вычислить функцию

7. Вычислить функцию

8. Определить количество и сумму десятичных разрядов в числе n, не превышающем числа 2⁶⁴.

Лабораторная работа № 2

Разработка эффективных алгоритмов

Разработать алгоритмы решения задач с заданными параметрами эффективности.

1. Найти минимум и максимум двух натуральных чисел без использования операции сравнения c временной сложностью t = O(4). Например, если a = 4, b = 5, то в результате работы алгоритма должно быть max = 5, min = 4.

2. Даны две числовые переменные a и b. Необходимо поменять местами их значения без использования других переменных и операции сравнения c временной сложностью t = O(5). Например, если a = 4, b = 5, то в результате работы алгоритма должно быть a = 5, b = 4.

3. Для вводимой последовательности из n (5 £ n £ 50) чисел разработайте алгоритм вычисления суммы положительных чисел и суммы отрицательных чисел с временной сложностью t = O(n) и емкостной сложностью e = O(5).

4. Для вводимого натурального числа n (n < 2⁶⁴) разработайте алгоритм вычисления суммы и произведения его десятичных разрядов с временной сложностью t = O(k) и емкостной сложностью e = O(4).

5. Разработайте алгоритм преобразования натурального числа n из i позиционной системы счисления в j позиционную систему счисления с промежуточным преобразованием числа в десятичную систему счисления.

6. Разработайте алгоритм вычисления суммы членов натурального ряда в интервале от k₁ до k₂ c временной сложностью t = O(5) и емкостной сложностью e = O(3).

7. Разработайте алгоритм, определяющий, является ли автобусный билет счастливым, т.е. равны ли суммы старших и младших трех цифр шестизначного числа, c временной сложностью t = O(5) и емкостной сложностью e = O(3).

8. Разработайте алгоритм решения квадратного уравнения ax² + bx + c = 0, используя наиболее эффективные способы вычисления корней в частных случаях (учитываемые случаи: общий случай, a = 0, a = 1, b – четное, с = 0). Определите временную и емкостную сложности для всех случаев решения уравнения.