Лабораторная работа по «Алгоритмам и анализу сложности»

ОТЧЕТ

Лабораторной работы №5

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

«Алгоритмы и анализ сложности»

Выполнил студент 2 курса очной формы обучения направления 02.03.02  «Фундаментальная информатика и информационные технологии»

Гаряев Артен Алексеевич

«__»_________2020г.

Преподаватель: Милошенко А.П.

Задание

Реализовать следующие алгоритмы, определить  базовую операцию.

Для заданий 1-2 найти наименьшее n, при котором F(n) не помещается в ячейку памяти, выделенную под переменную типа:

          а) int (231-1)                  б) long (263-1)

1. Вычислить n-ый элемент последовательности чисел Фибоначчи

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...)

   F(n)=F(n-1)+F(n-2)

   F(0)=0; F(1)=1)

2. Вычисление функции факториала F(n)=n!

3. Вычисление суммы элементов одномерного массива с помощью рекурсии.

Задание №1

Вычислить n-ый элемент последовательности чисел Фибоначчи

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...)

   F(n)=F(n-1)+F(n-2)

   F(0)=0; F(1)=1)

1. Основная часть программы. (В этой части происходит выполнение поставленной задачи)

[pic 1]

При вызове функции F для вычисления n-го числа последовательности Фибоначчи аргумент функции равен n-1. Так как если аргумент будет равен n тогда вычисляется не n-ый элемент последовательности, а (n+1)-ый.

Результат выполнения программы, при аргументе функции равном n-1.

[pic 2]

Результат выполнения программы, при аргументе функции равном n.

[pic 3]

Для выяснения какой аргумент функции необходимо использовать используем онлайн калькулятор. (https://www.rapidus.ru/fibonacci-numbers.html)

[pic 4]

Исходя из этих результатов, правильное вычисление обеспечит аргумент равный n-1.

Алгоритм вычисления n-го элемента последовательности Фибоначчи из интернета.

[pic 5]

Он заключается в вызове функции n-1 раз в цикле while. Этот способ необходим для вывода всех чисел Фибоначчи до заданного n-го. Однако цикл продолжается пока i не станет равным n, и когда i будет равно n цикл прерывается и выполняется остальная часть программы. А это значит что индекс последнего вычисленного числа будет равен i=n-1.

1. Часть в которой пользователю предоставляется выбор: продолжить выполнение программы или же завершить выполнение программы.

[pic 6]

1. Примеры выполнения программы

[pic 7]

[pic 8]

Задание№2

Вычисление функции факториала F(n)=n!

1. Основная часть программы. (В этой части происходит выполнение поставленной задачи)

[pic 9]

1. Часть в которой пользователю предоставляется выбор: продолжить выполнение программы или же завершить выполнение программы.

[pic 10]

1. Примеры выполнения программы

[pic 11]

Задание №3

Вычисление суммы элементов одномерного массива с помощью рекурсии.

1. Функция вычисления суммы

[pic 12]

1. Главная функция

[pic 13]

В главной функции реализованы 2 способа заполнения массива А числами: 1) Случайным образом, 2)Ввод с клавиатуры. Также пользователю предоставляется возможность выбрать один из двух способов на свое усмотрение.

1. Часть в которой пользователю предоставляется выбор: продолжить выполнение программы или же завершить выполнение программы.

[pic 14]

1. Примеры выполнения программы

[pic 15]

[pic 16]

Определить базовые операции

В задании №1 базовыми операциями является операция сравнения(<,>,=) и сложения(+).