РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ

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

По дисциплине

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

РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ

Выполнил студент группы:20кп01

Климочкин Д.Ю.

Проверил: к.т.н., доцент, доцент каф. ИВС

Дрождин В. В.

Пенза, 2021
Содержание

Введение

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

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

1. Задания на лабораторную работу

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

2) Даны две числовые переменные a и b. Необходимо поменять местами их значения без использования других переменных и операции сравнения с временной сложностью 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₂, с временной сложностью t = O(5) и емкостной сложностью e = O(3).

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

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

2. Формальные решения задач

1) Вводятся две переменные – a и b. Переменная максимума (max), определяется по формуле: (a + b + |a – b|)/2. Переменная минимума (min), определяется по формуле: (a + b - |a – b|)/2. После чего на экран выводится значение переменной максимума и переменной минимума

2) Вводятся две переменные – a и b. Переменной a присваивается значение переменной a увеличенной на b. Переменной b присваивается значение разности переменных a и b. Переменной a присваивается значение разности переменных a и b. После чего на экран выводится значения переменных.

3) Вводится переменная n. Определяются две переменных суммы положительных и отрицательных членов и присваивается значение нуля. Начинается цикл, число повторений которого ровно переменной n. В цикле вводится переменная х – элемент последовательности чисел. С помощью оператора сравнения, происходит сравнение введенного элемента с нулем, в зависимости от чего суммируются переменные счетчики. Цикл заканчивается, а на экран выводится значение сумм положительных и отрицательных элементов последовательности чисел.

4) Вводится переменная n. Определяется переменная произведения и переменная суммы чисел. Начинается цикл, пока n не равен 0. Переменной sum прибавляется значение остатка от деления n на 10. Переменная pr умножается на значение остатка от деления n на 10. Переменной n присваивается значения целой части от деления на 10. Цикл заканчивает работу, а на экран выводятся значения переменных суммы и произведения.

5) Вводятся переменные n, i и j. Определяется промежуточная переменная в десятичной системе счисления. Переменной k присваивается значение длины числа n. Начинается цикл от p=1 до k. В теле цикла, переменной sum прибавляется значение предыдущего элемента n, умноженный на i в степени k. Цикл заканчивает свою работу. На экран выводится значение переменной в десятичной системе счисления. Переменная s обнуляется. Начинается цикл Б, с условием пока sum = 0. Переменная s увеличивается на значение остатка от деления переменной sum на j. Переменная sum делится нацело на j. Цикл заканчивается, а на экран выводится значение переменной s.

6) Вводится значение переменных интервала k1 и k2. Переменной s присваивается значение суммы переменных k1 и k2, поделенных на 2, умноженное на разницу переменных k2 и k1, увеличенное на единицу, после чего значение s, выводится на экран.

7) Вводится переменная a. Переменной b1 присваивается значение (a делить нацело на 100000) + (а делить нацело 10000 остаток от деления на 10) + (а делить нацело на 1000, остаток от деления на 10). Переменной b2 присваивается значение (a делить нацело на 100 остаток от деления на 10) + (а делить нацело 10 остаток от деления на 10) + (а остаток от деления на 10). Если переменные равны, говорим что билет счастливый, иначе – не счастливый.

8) Вводятся переменные a, b и c - квадратного уравнения. Проверяем случаи: если а = 0, находим x=-c/b, и выводим на экран (t = O(4), e = O(4)). Если a=1, находим дискриминант, избавляясь от переменной a, после чего находим корни, избавившись от переменной а (t = O(7), e = O(6)). Если b четное, находим дискриминант по другой формуле, деля b на 2. В нахождении корней х, избавляемся от деления на 2 (t = O(8), e = O(6)). Если с = 0, дискриминант становится равным b², а в нахождении корней ничего не меняется (t = O(9), e = O(6)). В общем случае, находим дискриминант и корни (t = O(10), e = O(6)). Ответы выводим на экран.

3. Алгоритмы решения задач

На основе рассмотренных методов разработаем алгоритмы решения задач и представим их в виде блок-схем, приведенных на рисунках 1-8.

Рисунок 1 – Блок схема

Рисунок 2 – Блок схема

Рисунок 3 – Блок схема

Рисунок 4 – Блок схема

Рисунок 5 – Блок схема

Рисунок 6 – Блок схема

Рисунок 7 – Блок схема

Рисунок 8 – Блок схема

Заключение

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