Задание №4 Цель работы

Используя технологию модульного программирования разработать программу обработки данных, содержащихся в заранее подготовленном файле, в соответствии с индивидуальным заданием. Применить динамическую структуру указанного в задании вида: стек, очередь или дек. Программа должна включать модуль, содержащий набор всех необходимых средств (типов, подпрограмм и т.д.) для решения поставленной задачи.

Вариант 12

Дан файл из целых чисел. Используя дек, за один просмотр файла напечатать сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе.

Ход работы

Реализация дека на Python:

class Deque:

    def __init__(self):

        self.items = []

    def add_front(self, item):

        self.items.append(item)

    def add_rear(self, item):

        self.items.insert(0,item)

    def remove_front(self):

        return self.items.pop()

    def remove_rear(self):

        return self.items.pop(0)

    def size(self):

        return len(self.items)

Ниже представлен основной код программы. Чтобы сохранить исходный порядок чисел в каждой группе, было решено разделить поток на 2 очереди.

def split_file(file):

    with open(file) as f:

        positive_d = Deque()

        negative_d = Deque()

        for line in f:

            num = int(line.strip())

            if num < 0:

                negative_d.add_front(num)

            else:

                positive_d.add_rear(num)

        while positive_d.size() > 0:

            print(positive_d.remove_front())

        while negative_d.size() > 0:

            print(negative_d.remove_rear())

def main():

    split_file('lab4.txt')

if __name__ == '__main__':

    main()

Результат выполнения кода:

Изначальный порядок расположения чисел:

Вывод

Используя технологию модульного программирования, была разработана программа обработки данных. Она считывает файл из целых чисел. За тем, используя два потока, за один просмотр файла выводит на экран сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе.

Задание №5

Цель работы

Реализовать генерацию заданного типа фрактала с применением рекурсивных функций. Добавить возможность задания глубины фрактала. Оценить глубину рекурсии. Построить таблицу зависимости времени построения от глубины фрактала.

Вариант 12

Дерево Пифагора.

Ход работы

Глубина 3:

Глубина 5:

Глубина 7:

Код программы

import turtle

import colorsys

import time

import math

print('Введите глубину дерева:')

depthLimit = int(input())

count = 0

def drawTree(t, size, depth):

    global count

    count = count + 1

    drawSquare(t, size, color(count))

    if depth + 1 <= depthLimit :

        t.left(90)

        t.forward(size)

        t.right(45)

        drawTree(t, abs(math.cos(-math.pi/4) * size), depth + 1)

        t.forward(abs(math.cos(-math.pi/4) * size))

        t.right(90)

        drawTree(t, abs(math.cos(-math.pi/4) * size), depth + 1)

        t.left(90)

        t.backward(abs(math.cos(-math.pi/4) * size))

        t.left(45)

        t.backward(size)

        t.right(90)

def drawSquare(t, sideLength, color):

    t.down()

    t.begin_fill()

    t.fillcolor(color)

    for i in range(4):

        t.forward(sideLength)

        t.left(90)

    t.end_fill()

    t.up()

def color(count):

    hue = count * 0.02

    saturation = 1

    brightness = 1

    r, g, b = colorsys.hsv_to_rgb(hue, saturation, brightness)

    r, g, b = int(r * 255), int(g * 255), int(b * 255)

    return '#{0:02X}{1:02X}{2:02X}'.format(r, g, b)

def main():

    t = turtle.Pen()

    t.up()

    t.goto(-100, -200)

   

    start = time.perf_counter()

    drawTree(t, 100.0, 0)

    end = time.perf_counter()

    print(f"Время выполнения: {(end-start):.3f} с")

    print(f"Кол-во вызовов функции: {count}")

    turtle.mainloop()

if __name__ == '__main__':

    main()

Результат работы:

Глубина фрактала	1	3	5	7
Время выполнения, с	5.923	32.775	123.188	375.513
Кол-во вызовов функции	3	15	63	255

Вывод

Исходя из полученных данных увеличение глубины дерева, ведет к экспоненциальному увеличению количества вызовов функции. Также увеличение глубины значительно замедляет скорость выполнения программы. Это связано с тем, что каждый новый уровень рекурсии вызывает дополнительные операции рисования на холсте. При этом, увеличение глубины дерева приводит к более сложным и детализированным фракталам.

Список литературы

1. Структуры и алгоритмы обработки данных. 2021г, Л. А. Павлов , Н. В. Первова;

2. Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. 2009г, Дж. Макконелл;

3. Алгоритмы. Построение и анализ. 2013г, Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн;

4. Фрактальная геометрия природы.2002г, Б. Мандельброт;

5. Фракталы и хаос в динамических системах. 2006г. Ричард М. Кроновер.