Бинарные деревья Оценки времени выполнения алгоритмов
- Реализуйте бинарное дерево для хранения выражения. Вычислите значение выражения
Вариант | Выражение |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | X+3xy+z2+6 |
10 | x2+3y+ z3 |
Возведение в степень ^.
2.Оценить время выполнения алгоритма, если алгоритм содержит 2 фрагмента с функциями роста времени в зависимости от роста объема данных t1(n) и t2(n). Считать, что фрагменты выполняются:
А) последовательно;
Б) вложены друг в друга;
Т.е. найти t1(n)+ t2(n) и t1(n)* t2(n)
Вариант | Задание |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 |
Задание 3. Оценить время выполнения следующих фрагментов программ.
Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, график отображения.
(Без вариантов)
Лабораторная №14
1.Создать модуль Stackman в котором реализованы все операторы стека(Pascal, C++)
- Создать хеш-функцию для хранения записей в файл в сортированном виде. Хеш функцию связать с кодами первых 3 символов Фамилии. Запись состоит из полей :Фамилия, Имя, Отчество.
- Создать кольцевой список, в котором хранятся целые числа.
- Создать отображение на основе линейного списка перечислением пар(x,y). Реализовать операторы: Инициализация отображения, добавление пары, удаление пары, просмотр элементов отображения, график отображения.
- Создать бинарное дерево-выражений в котором нужно хранить выражения :(a+b)*(c+d)/2*b. Представить выражение в постфиксном и префиксном формах.
|
|
Лабораторная №15
1. Сортировать файл целых чисел методом слияний.
2. Сортировать файл целых чисел следующим образом: Разбить файл на 2 вспомогательных : в первом вспомогательном файле собрать числа меньшие или равные среднему арифметическому, а втором – большие. Применить к каждому вспомогательному файлу какой либо алгоритм внутренней сортировки (например, пузырьковую сортировку). После присоединить к 1 файлу 2 файл. Вывести результат.
Лабораторная №16
- Создать бинарное дерево методом левых сыновей.
- Создать архиватор на основе алгоритма Хаффмана
- Создать сильноветвящееся дерево методом матрицы смежности.
- Сортировать массив с помощью дерева.
- Написать программу обхода двоичного дерева слева-направо, симметрично, справа –налево.
Лабораторная №17.Разработка алгоритмов
- Создать программу триангуляции выпуклого многоугольника.
- Программировать игру “Крестики - нолики” .Реализовать стратегию выигрыша. Игра с компьютером.
Лабораторная №18
|
|
- Программировать игру “Шашки”. Анализируйте стратегию выигрыша.
- Создать граф для отображения городов округа. Весами ребер являются расстояния. Определите кратчайшее расстояние из города А в город В.
Лабораторная №19
- Сортировать файл методом слияний.
- Создать очередь с приоритетами для хранения названий городов.
- Программировать игру Баше. Имеется куча камней. Два игрока последовательно могут забрать 1,2 или 3 камня. Проигрывает тот, который забирает оставшийся камень.
Лабораторная №20
1. Создать индексный файл для записей структуры Фио, оклад, премия по ключу ФИО.
2. Создайте Хеш-функцию по первому символу Фамилии. Коллизии разрешить с помощью вспомогательных файлов. Реализовать методы: добавить запись, просмотр записей, вывод хеш - кода.
3.Сортировать массив методом слияний.
Лабораторная №21-24
- Имеется файл записей следующей структуры: Фамилия, Имя, Отчество, курс, группа. Реализуйте следующие методы:
· Чтение записей в однонаправленный список и вывод списка на экран.
· Чтение записей в стек и вывод вершины стека.
|
|
· Чтение записей в очередь и вывод очереди на экран.
· Сортировку файла по полю Фамилия.
· Вывод списка однокурсников в массивы.
- Реализуйте циклический список, содержащий значение температуры в течение каждого часа суток. Организуйте хранение этих значений в файле tem.dat по истечению суток. Датчиками температуры можно взять генератор чисел из интервала (-50,40) или использовать поле для ввода данных.
- Имеется числовой файл, в котором хранится n строк по n чисел. Считайте эти числа в матрицу смежности и отобразите граф.
- Напишите программу анализатор арифметических операций с использованием стека. Выражение вводится в виде строки с клавиатуры. Вычислите значение выражения и представьте в виде бинарного дерева выражений.
- Пропишите все – возможные варианты следующей игры. На шахматной доске по краям установлены по 8 шашек(белые и черные). Двигать шашки можно только вперед или назад. Выигрывает тот, кто выполнит последний ход и закроет ходы другому. Программируйте игру с компьютером.
Дата добавления: 2020-01-07; просмотров: 229; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!