Файл: Структуры лабы.doc

1.

const n=31;

var x: array [1..n] of integer;

p: integer; k: 1..n; found: boolean;

Простыми вставками упорядочить элементы массива х по убыванию. Для числа р проверить: если р входит в массив х, то found присвоить TRUE, а к – номер элемента равного р, и found присвоить FALSE иначе.

2.

var x: array [1..20] of 1..21;

y: 1..21;

Пусть все элементы массива х различны. Расположить их по возрастанию методом бинарных вставок и, найти y – то единственное целое є [1..21], которого нет в этом массиве.

3.

var x: array [1..20] of real;

Упорядочить массив по возрастанию, используя сортировку обменом (метод «пузырька»). Учесть в программе, что если при очередном просмотре не было ни одного обмена (перестановки), то массив уже упорядочен, и процесс необходимо завершить с выводом полученной упорядоченной последовательности.

4.

const n=20;

var x: array [1..n] of real;

Упорядочить массив х по неубыванию, используя сортировку простыми вставками (сравнение в обратном направлении: от (i -1) до 1) и модифицировать алгоритм для просмотра готового массива (в методе простых вставок) в прямом направлении (от 1-го до (i -1)-го элемента).

5.

var x: array [1..20] of 1..21;

y: 1..21;

Пусть все элементы массива х различны. Расположить их по убыванию методом прямого выбора и, используя бинарный поиск, найти y – то единственное целое число є [1..21], которого нет в этом массиве.

6.

var x: array [1..20] of real;

Упорядочить массив по убыванию, используя сортировку методом «пузырька». Если при очередном просмотре массива не было ни одного обмена, то массив уже упорядочен, и процесс необходимо завершить. Выдать на печать отсортированный массив и число фактически совершенных просмотров массива в ходе сортировки.

7.

var x: array [1..20] of real;

Упорядочить массив по возрастанию, используя метод «пузырька» с чередованием направлений последовательных просмотров – метод «шейкерной» сортировки. Проанализировать в сравнении пузырьковую и шейкерную сортировки.

8.

const n=20;

var x: array [1..n] of integer; // сортируемый массив

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

var Mno: set of 0..255;

Для широкого диапазона ключей использовать гипермножество – массив множеств:

Type MasMno=array of set of 0..22;

9.

Даны натуральные числа а₁,..а_n. Пусть а₁,..а_n – перестановка чисел 1,.. n. Написать программу для получения натуральных r_1,..,r_n таких, что r_ai=i для i=1,..,n.

1.

var x: array [1..1000] of real;

Применив алгоритм сортировки Шелла (сортировка с помощью включений с уменьшающимися расстояниями), отсортировать массив х в порядке неубывания. При выборе расстояний пользоваться следующими рекомендациями (Кнут Д. «Искусство программирования для ЭВМ» т.1): h_k-1=2*h_k-1 (…9,5,3,1), h_t=1, t=[log₂n] +1

2.

Используя сдвигающий алгоритм построения пирамиды Флойда, для заданного массива целочисленных ключей построить пирамиду, распечатать ключи получившегося бинарного дерева (например, в виде массива, для которого должно выполняться правило: для любого i: j=2*i или j=2*i+1, h_i≤h_j) и распечатать минимальный элемент массива.

3.

Пусть построена пирамида Флойда:

06

рис. 1

Ввести ключи этой пирамиды в ОП в виде массива, элементы которого подчиняются правилу задания бинарного дерева. Написать процедуру сдвига алгоритма Флойда и, используя ее, отсортировать ключи пирамиды в порядке убывания.

4.

Ввести ключи бинарного дерева (рис. 1) в ОП. Запрограммировать сдвигающий алгоритм Флойда для упорядочения заданного массива ключей в порядке возрастания (пирамидальная сортировка).

5.

Сформировать массив псевдослучайных целых чисел в диапазоне

[-100…100]. Количество элементов задавать с клавиатуры. Используя рекурсивный алгоритм сортировки с помощью разделения (сортировка Хоара  QuickSort) упорядочить сформированный массив по неубыванию его элементов. Результат сортировки вывести в объект класса TMemo.

6.

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

var stack: array [1..30] of record

Left, Right: integer;

end;

7.

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

8.

Сформировать массив целых псевдослучайных чисел в диапазоне [-20..20]. Отсортировать массив в порядке возрастания, используя алгоритм сортировки последовательностей прямым слиянием (алгоритм Боуза и Нельсона). Структурировать программу, организовав рекурсивную процедуру для слияния списков (частей массива) равного размера.

1.

Смоделировать (т.е. объявить тип структуры и описать библиотеку UNIT1 статических процедур для работы со структурой) линейную очередь как массив из n компонент типа real, в котором элементы очереди занимают группу соседних компонент; индексы первой и последней компоненты запоминаются; когда очередь достигает правого края, все ее элементы сдвигаются к левому краю:

1 2 н-1 н н+1 к к+1

В библиотеку UNIT1 должны войти процедуры:

Ochistka (Q) – создать пустую очередь (очистить очередь)

PustOch (Q) – выдает истину, если очередь пустая

InOchered (Q, x) – добавить элемент в конец очереди

OutOchered (Q, x) – удалить из очереди первый элемент, присвоив его

параметру x

Oshibka (k) – выдает к- номер ошибки, если операция с очередью невыполнима:

к=1 – очередь переполнена

к=2 – очередь исчерпана

Написать вызывающую программу, в которой подключается модуль UNIT1, для демонстрации работы линейной очереди.

2.

Смоделировать очередь, описанную в вар.1 и, используя процедуры модуля UNIT1, решить задачу:

type FR = file of real;

За один просмотр файла f типа FR вывести на экран его элементы в следующем порядке: сначала все числа меньше а, потом все числа из отрезка [а;b], потом - все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (а и b задаются с клавиатуры, а < b). Использовать две очереди: Q₁ – для элементов [а; b], Q₂ – для остальных.

3.

Смоделировать очередь, описанную в вар. 1 и, используя процедуры модуля UNIT1, решить задачу: содержимое текстового файла f , разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (для запоминания цифр организовать линейную очередь), с сохранением исходного взаимного порядка как среди цифр, так и среди остальных символов строки.

4.

Смоделировать работу линейного стека - объявить тип структуры и описать статическую библиотеку UNIT2 (процедур и функций для работы с ним). Под стек отвести массив из n компонент типа real, в начале которого располагаются элементы стека, при этом запоминается индекс компоненты массива, занятой последним элементом стека:

В библиотеку UNIT2 должны войти процедуры:

Ochistka (S) – создать пустой стек (очистить стек)

PustSteck (S) – выдает истину, если стек пуст

InSteck (S, x) – добавить элемент x в конец стека S

OutSteck (S, x) – удалить из стека S последний элемент, присвоив его параметру x

Oshibka (k) – выдает к- номер ошибки, если операция невыполнима:

к = 1 – переполнение стека

к = 2 – исчерпание стека

Написать вызывающую программу, в которой подключается модуль UNIT2, для демонстрации работы линейного стека.

5.

Смоделировать линейный стек в соответствии с описанием вар. 4 и, используя процедуры модуля UNIT2, решить задачу: вывести на экран содержимое текстового файла t, выписывая символы каждой его строки в обратном порядке. Передачу символов строки организовать с помощью линейного стека.

6.

Организовать кольцевую очередь в виде статического массива:

const n = 50;

var z: array [1..n] of integer; i, j: integer;

{начало и конец очереди}

Записать в очередь 20 псевдослучайных чисел, а затем всякий раз, добавляя в конец новое число (в процедуре InOut), будем исключать из, головы очереди все числа, которые меньше. Здесь возможны 2 исхода: очередь пустеет (одно из новых чисел больше всех) или переполняется (в очереди оказалось такое число, которое не было превзойдено добавляемыми числами).

Замечание: для кольцевой очереди должен быть переход по кольцу на начало, если индекс конца, вышел за границу массива:

7.

Реализуйте кольцевой стек на базе статического массива, фиксируя голову стека. Занесите в стек 10 псевдослучайных целых чисел, не превосходящих 100, причем суммируйте их в процессе генерации; затем, выталкивая их из стека, снова просуммируйте и убедитесь в совпадении сумм. Сформировать процедуры занесения элемента в кольцевой стек и выталкивания элемента из стека.

8.

Ввести с клавиатуры две неубывающих строки символов – Byte-чисел > 0 и сохранить их в структурах типа Pchar. Слить их в единую структуру типа Pchar, сохранив при этом общий порядок неубывания.

9.

Смоделировать стек, описанный в вар. 4. Используя стек, решить задачу:

type FC = file of char;

Проверить, сбалансировано ли содержимое файла t типа FC относительно круглых скобок. Файл читать один раз, а последовательности позиций скобок сохранять в стеке. При нарушении баланса распечатывать несбалансированную последовательность скобок в виде: пары позиций сбалансированных скобок, затем – номера позиций скобок без пар. Например, для текста:

А+(45-F(x)*(B-C)))

Вывод: 12 16

8. 10

3. 17

18