Бинарные деревья Оценки времени выполнения алгоритмов

1. Реализуйте бинарное дерево для хранения выражения. Вычислите значение выражения

Вариант	Выражение
1
2
3
4
5
6
7
8
9	X+3xy+z2+6
10	x2+3y+ z3

 

Возведение в степень ^.

 

2.Оценить время выполнения алгоритма, если алгоритм содержит 2 фрагмента с функциями роста времени в зависимости от роста объема данных t₁(n) и t₂(n). Считать, что фрагменты выполняются:

                   А) последовательно;

                   Б) вложены друг в друга;

Т.е. найти t₁(n)+ t₂(n) и t₁(n)* t₂(n)

 

Вариант	Задание
1
2
3
4
5
6
7
8
9
10

 

Задание 3. Оценить время выполнения следующих фрагментов программ.

 

 

Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, график отображения.

 

(Без вариантов)

 

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

1.Создать модуль Stackman в котором реализованы все операторы стека(Pascal, C++)

1. Создать хеш-функцию для хранения записей в файл в сортированном виде. Хеш функцию связать с кодами первых 3 символов Фамилии. Запись состоит из полей :Фамилия, Имя, Отчество.
2. Создать кольцевой список, в котором хранятся целые числа.
3. Создать отображение на основе линейного списка перечислением пар(x,y). Реализовать операторы: Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, график отображения.
4. Создать бинарное дерево-выражений в котором нужно хранить выражения :(a+b)*(c+d)/2*b. Представить выражение в постфиксном и префиксном формах.

 

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

1. Сортировать файл целых чисел методом слияний.

2. Сортировать файл целых чисел следующим образом: Разбить файл на 2 вспомогательных : в первом вспомогательном файле собрать числа меньшие или равные среднему арифметическому, а втором – большие. Применить к каждому вспомогательному файлу какой либо алгоритм внутренней сортировки (например, пузырьковую сортировку). После присоединить к 1 файлу 2 файл. Вывести результат.

 

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

1. Создать бинарное дерево методом левых сыновей.
2. Создать архиватор на основе алгоритма Хаффмана
3. Создать сильноветвящееся дерево методом матрицы смежности.
4. Сортировать массив с помощью дерева.
5. Написать программу обхода двоичного дерева слева-направо, симметрично, справа –налево.

 

Лабораторная №17.Разработка алгоритмов

1. Создать программу триангуляции выпуклого многоугольника.
2. Программировать игру “Крестики - нолики” .Реализовать стратегию выигрыша. Игра с компьютером.

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

1. Программировать игру “Шашки”. Анализируйте стратегию выигрыша.
2. Создать граф для отображения городов округа. Весами ребер являются расстояния. Определите кратчайшее расстояние из города А в город В.

 

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

1. Сортировать файл методом слияний.
2. Создать очередь с приоритетами для хранения названий городов.
3. Программировать игру Баше. Имеется куча камней. Два игрока последовательно могут забрать 1,2 или 3 камня. Проигрывает тот, который забирает оставшийся камень.

 

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

1. Создать индексный файл для записей структуры Фио, оклад, премия по ключу ФИО.

2. Создайте Хеш-функцию по первому символу Фамилии. Коллизии разрешить с помощью вспомогательных файлов. Реализовать методы: добавить запись, просмотр записей, вывод хеш - кода.

3.Сортировать массив методом слияний.

 

 Лабораторная №21-24

1. Имеется файл записей следующей структуры: Фамилия, Имя, Отчество, курс, группа. Реализуйте следующие методы:

· Чтение записей в однонаправленный список и вывод списка на экран.

· Чтение записей в стек и вывод вершины стека.

· Чтение записей в очередь и вывод очереди на экран.

· Сортировку файла по полю Фамилия.

· Вывод списка однокурсников в массивы.

1. Реализуйте циклический список, содержащий значение температуры в течение каждого часа суток. Организуйте хранение этих значений в файле tem.dat по истечению суток. Датчиками температуры можно взять генератор чисел из интервала (-50,40) или использовать поле для ввода данных.
2. Имеется числовой файл, в котором хранится n строк по n чисел. Считайте эти числа в матрицу смежности и отобразите граф.
3. Напишите программу анализатор арифметических операций с использованием стека. Выражение вводится в виде строки с клавиатуры. Вычислите значение выражения и представьте в виде бинарного дерева выражений.
4. Пропишите все – возможные варианты следующей игры. На шахматной доске по краям установлены по 8 шашек(белые и черные). Двигать шашки можно только вперед или назад. Выигрывает тот, кто выполнит последний ход и закроет ходы другому. Программируйте игру с компьютером.

 

 

---

Дата добавления: 2020-01-07; просмотров: 229; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!