Из сборника Введение в информатику. Лабораторные работы. Ч. II / Авт.-сост. А.П. Шестаков; Перм. ун-т. — Пермь, 1999. — 71 с.

E97: Задачи повышенной сложности

В настоящей лабораторной работе представлены задачи, относящиеся к различным разделам программирования. Трудности при их решении могут быть вызваны сложным алгоритмом либо разработкой собственного способа представления данных в памяти ЭВМ.

Пример. Сортировка выбором. Упорядочить элементы массива в порядке возрастания.

Напомним алгоритм. Если часть массива отсортирована, то просматривается оставшаяся часть, где выбирается минимальный элемент. Затем производится обмен текущего и минимального элементов. Первоначально отсортированный массив состоит из нулевого количества элементов.

План решения

1. i := 1                  	 	9. Сравнить a[j] с a[min]
2. Сравнить i c n	   		10. Если a[j] < a[min], то min := j
3. Если i > n, переход к п. 16		11. Переход к п. 6
4. j := i				12. vsp := a[i]
5. min := i				13. a[i] := a[min]
6. Сравнить j с n			14. a[min] := b
7. Если j = n, переход к п. 12		15. Переход к п. 2
8. j := j + 1				16. Стоп

Распределение памяти

R0	R1	R2	R3
адрес a[i], a[j]	i, j	адрес a[min]	n

Программа

Адрес Команда  Действие                                 Замечания
0000	0E6D	FE => SP				установка SP
0002	00FE
0004	2111	1 => R1					i:=1
0006	0413	сравнить R1 с R3			сравнить i с n (n-i)
0008	3D26	если <0, переход			переход, если i>n
000A	0E21	R1 => стек				i => стек
000C	0E20	R0 => стек				адрес a[i] => стек
000E	0102	R0 => R2				a[min] := a[i] (запоминаем адрес a[i])
0010	0413	сравнить R1 с R3			сравнить j с n (n-j)
0012	5D0C	если =0, переход			переход, если j = n
0014	2211	R1 + 1 => R1				j := j + 1
0016	2220	R0 + 2 => R0				адрес a[j]
0018	0446	сравнить (R0) с (R2)			сравнить a[j] с a[min] (a[min]-a[j])
001A	6D02	если <=0, переход			к переходу на сравнение j с n
001C	0102	R0 => R2				a[min] := a[j] (запоминаем адрес a[j])
001E	1DF0	безусловный переход			к сравнению j с n
0020	0E30	стек => R0				адрес a[i] из стека в R0
0022	0E31	стек => R1				i из стека в R1
0024	0E26	(R2) => стек				запоминаем a[min]
0026	0146	(R0) => (R2)				a[min] := a[i]
0028	0E34	стек => (R0)				a[i] := a[min] (из стека)
002A	2211	R1 + 1 => R1				i := i + 1
002C	2220	R0 + 2 => R0				адрес a[i]
002E	1DD6	безусловный переход			к сравнению i с n
0030	0F00	стоп

Задачи для самостоятельного решения

1. Заданы два линейных массива с различным количеством элементов и натуральное число k. Объединить их в один массив, включив второй массив между k-м и (k+1)-м элементами первого, не используя дополнительный массив.
2. Даны две неубывающие последовательности. Образовать из них новую последовательность чисел так, чтобы она тоже была неубывающей. Примечание. Дополнительный массив не использовать.
3. Сортировка обменами. Дана последовательность чисел. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа a_i и a_i+1. Если a_i>a_i+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не станут расположены в порядке возрастания. Составить алгоритм сортировки, подсчитывая при этом количества перестановок.
4. Сортировка вставками. Дана последовательность чисел. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть элементы по a_i включительно образуют упорядоченную по возрастанию последовательность. Берется следующее число a_i+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны.
5. Сортировка Шелла. Дан массив действительных чисел. Требуется упорядочить его по возрастанию. Делается это следующим образом: сравниваются два соседних элемента a_i и a_i+1. Если a_i <= a_i+1, то продвигаются на один элемент вперед. Если a_i > a_i+1, то производится перестановка и сдвигаются на один элемент назад. Составить алгоритм этой сортировки.
6. Пусть даны неубывающая последовательность действительных чисел и произвольная последовательность действительных чисел. Требуется указать те места, на которые нужно вставлять элементы второй последовательности в первую последовательность так, чтобы новая последовательность оставалась возрастающей.
7. Даны дроби Составить программу, которая приводит эти дроби к общему знаменателю и упорядочивает их в порядке возрастания.
8. Алгоритм фон Неймана. Упорядочить массив по неубыванию с помощью алгоритма сортировки слияниями:

   1) каждая пара соседних элементов сливается в одну группу из двух элементов (последняя группа может состоять из одного элемента);

   2) каждая пара соседних двухэлементных групп сливается в одну четырехэлементную группу и т.д.

   При каждом слиянии новая укрупненная группа упорядочивается.

9. Реализовать алгоритм двоичного (бинарного) поиска в отсортированном массиве. Если заданное число будет найдено, поместить по адресу 76 его адрес, иначе — -1.
10. Разработать программу ввода и размещения в памяти двумерного массива. Решить следующие задачи, результат вывести на экран:
    • упорядочить элементы каждой строки по возрастанию;
    • упорядочить элементы каждого столбца по возрастанию;
    • элементы каждой строки с четным номером упорядочить по возрастанию, с нечетным — по убыванию;
    • найти сумму элементов главной диагонали квадратной матрицы;
    • на месте каждого элемента записать частное от его деления на номер столбца, в котором он расположен;
    • на месте каждого элемента записать частное от его деления на минимальный элемент той строки, в которой он расположен;
    • если сумма индексов максимального элемента массива четная, поместить по адресу 76 число 1, иначе — число -1;
    • каждый элемент массива увеличить на разность его первого и второго индекса;
    • все элементы квадратной матрицы, лежащие выше главной диагонали, умножить на данное число k;
    • все элементы квадратной матрицы, лежащие ниже главной диагонали, заменить на нуль;
    • если выше главной диагонали лежит больше чисел, кратных заданному k, чем ниже главной диагонали, то поместить по адресу 76 число 1, если поровну — 0, если меньше — -1;
    • порядок квадратной матрицы нечетный. Поменять местами среднюю строку и средний столбец.
11. Разработать способ представления в памяти E97 действительных чисел. Написать следующие подпрограммы:
    • ввод действительного числа;
    • вывод действительного числа;
    • сложение двух действительных чисел;
    • вычитание двух действительных чисел;
    • умножение двух действительных чисел.
12. Разработать способ представления в памяти E97 четырехбайтовых целых чисел со знаком. Написать следующие подпрограммы:
    • ввод числа;
    • вывод числа;
    • сложение двух чисел;
    • вычитание двух чисел;
    • умножение двух чисел;
    • целочисленное деление двух чисел;
    • нахождение остатка от деления одного числа на другое.
13. Разработать способ представления в памяти E97 величин типа "множество". Написать следующие подпрограммы:
    • объединение множеств;
    • пересечение множеств;
    • разность множеств;
    • вхождение элемента в множество (результат TRUE или FALSE).

---

---