Вопрос 1 Вариант 3. Тема 1 Двоичные деревья Задание. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска: поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений построчный вывод дерева в наглядном виде на основе процедур обхода: - в прямом порядке; - с помощью обратно-симметричного обхода; Рекомендации: 1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины. 2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений. 3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и обратно-симметричном порядке: Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины. Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна: проверить пустоту очередного поддерева вывести в цикле необходимое число пробелов в соответствии с уровнем вершины вывести информационную часть текущей вершины вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1 вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1 Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице Главная программа должна предоставлять следующие возможности: создание дерева с заданным числом вершин со случайными ключами добавление в дерево одной вершины с заданным пользователем значением ключа поиск в дереве вершины с заданным ключом построчный вывод дерева в наглядном виде Тема 2 Организация поиска в массиве данных при помощи специальных методов поиска. Задание. Реализовать программно метод хеш-поиска с разрешением конфликтов методом пустых ячеек. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле j = (( h (ключ) + i ) mod m ) + 1, где i = 0, 1, 2, . . . , m-2 Программа должна выполнять следующие действия: добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений вывод текущего состояния таблицы на экран После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска. Тема 3 Сортировка данных Задание 1 Реализовать программу, реализующую простейший метод сортировки массивов: сортировку выбором сортировку вставками Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и выводом этого массива на экран Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000) и провести сравнительный анализ эффективности рассматриваемых методов. Главная программа должна реализовать диалог с пользователем для выбора метода сортировки. Задание 2 Оформить программу, реализующую метод быстрой сортировки массивов. Метод реализуется в виде подпрограммы. Исходный массив должен обрабатываться подпрограммой сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Выполнить сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000). Требования к прохождению учебной практики: -небольшой теоретический обзор (анализ) по используемым структурам данных и методам – скриншоты результатов тестирования (запуска выполненных программ), отображающие набор выполненных по заданию основных действий – полный листинг программного кода по каждому заданию с комментариями;
Контрольная работа по delphi:
«учебная практика»
заказ № 1941123
Контрольная работа по delphi:
«учебная практика»
Мы напишем новую работу по этой или другой теме с уникальностью от 70%
Задание
Вопрос 1 Вариант 3.
Тема 1 Двоичные деревья
Задание. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска:
поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа
добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений
построчный вывод дерева в наглядном виде на основе процедур обхода:
- в прямом порядке;
- с помощью обратно-симметричного обхода;
Рекомендации:
1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины.
2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений.
3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и обратно-симметричном порядке:
Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины.
Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:
проверить пустоту очередного поддерева
вывести в цикле необходимое число пробелов в соответствии с уровнем вершины
вывести информационную часть текущей вершины
вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1
вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1
Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице
Главная программа должна предоставлять следующие возможности:
создание дерева с заданным числом вершин со случайными ключами
добавление в дерево одной вершины с заданным пользователем значением ключа
поиск в дереве вершины с заданным ключом
построчный вывод дерева в наглядном виде
Тема 2 Организация поиска в массиве данных при помощи специальных методов поиска.
Задание. Реализовать программно метод хеш-поиска с разрешением конфликтов методом пустых ячеек.
Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле
j = (( h (ключ) + i ) mod m ) + 1, где i = 0, 1, 2, . . . , m-2
Программа должна выполнять следующие действия:
добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
вывод текущего состояния таблицы на экран
После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска.
Тема 3 Сортировка данных
Задание 1 Реализовать программу, реализующую простейший метод сортировки массивов:
сортировку выбором
сортировку вставками
Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и выводом этого массива на экран
Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение.
После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000) и провести сравнительный анализ эффективности рассматриваемых методов.
Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.
Задание 2 Оформить программу, реализующую метод быстрой сортировки массивов.
Метод реализуется в виде подпрограммы. Исходный массив должен обрабатываться подпрограммой сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Выполнить сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000).
Требования к прохождению учебной практики:
-небольшой теоретический обзор (анализ) по используемым
структурам данных и методам
– скриншоты результатов тестирования (запуска выполненных
программ), отображающие набор выполненных по заданию основных
действий
– полный листинг программного кода по каждому заданию с
комментариями;
Алгоритм быстрой сортировки, известный также как Quicksort, разработал английский ученый Чарльз Хоар в 1960 году. Суть быстрой сортировки во многом аналогична методу сортировки слиянием. Выбирается элемент `q`, который называется барьерным, и массив делится на две части, при этом элементы переупо...
Читать дальше
Алгоритм Евклида
Определение 1Алгоритм Евклида — это традиционный метод для вычисления наибольшего общего делителя (НОД) двух целых чисел. Алгоритмы решения задачи Рассмотрим задачу нахождения НОД для двух натуральных чисел. Даны два натуральных числа `a` и `b`, и необходимо найти такое наибольшее число `d`, кото...
Читать дальше
Цикл while и его синтаксис
Цикл `while` ("пока") в Python выполняет заданный набор действий до того времени, пока истинно проверяемое условие. Замечание 1Условие указывается перед телом цикла и проверяется до начала его выполнения. Обычно цикл `while` применяется, когда заранее неизвестно точное количество итераций. Синтак...
Читать дальше
Списки и срезы списков
Методы создания и считывания списков (массивов) Большая часть программ работает с не одним элементом, а с коллекцией переменных. Пример 1Приложение может управлять информацией об учениках класса, считывая список учащихся либо с клавиатуры, либо из файла, при этом изменение числа участников в клас...