Задачи повышенной сложности. 1. Заданы два линейных массива с различным числом элементов и натуральное число к

1. Заданы два линейных массива с различным числом элементов и натуральное число к. Объединить их в один массив, включив второй массив между к-м и (к + 1)-м элементами первого, не используя дополнительный массив.

2. Даны две последовательности а_х < а₂ <... < а_п и Ъ_х< Ъ₂ <... < Ъ_т. Образовать из них новую последовательность чисел так, чтобы она тоже была неубывающей. Примечание. Дополнительный массив не использовать.

3. Сортировка обменами. Дана последовательность чисел а,, а₂,..., а_п. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа а, и а_[+ Если а_[ > а_1+ь то делается перестановка. Так продолжается до тех пор, пока все элементы не расположатся в порядке возрастания. Составить алго­ритм сортировки, подсчитывая при этом число перестановок.

4. Сортировка вставками. Дана последовательность чисел а_и а_ъ..., а_п. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть а_и а₂,..., а_{ — упорядоченная последовательность, т.е. а_{ < а₂ <... < а_г Берется следующее число а_1+х и вставляется в последовательность так, чтобы новая после­довательность была также возрастающей. Процесс производится до тех пор, пока все элементы от / + 1 до п не будут перебраны.

5. Сортировка Шелла. Дан массив п целых чисел. Требуется упорядочить его по возрастанию. Делается это следующим образом: сравниваются два соседних эле­мента Л/ и а₁₊₁. Если а, < а_/+1, то продвигаются на один элемент вперед. Если Я/> а_1+ь то производится перестановка и сдвигаются на один элемент назад. Со­ставить алгоритм этой сортировки.

6. Пусть даны неубывающая последовательность целых чисел а_х < а₂ <... < а_п и целые числа Ь_{< Ь₂<... < Ъ_т. Требуется указать те места, на которые надо вставлять элементы последовательности Ь_х < Ь₂<... < Ъ_т в первую последовательность так, чтобы новая последовательность оставалась возрастающей.

Р\ Рг Рп

1. Даны дроби ~~ (р₁ — целые, а: — натуральные). Составить про-

41 42 Чп

грамму, которая приводит эти дроби к общему знаменателю и упорядочивает их в порядке возрастания.

8. Алгоритм фон Неймана. Упорядочить массив а_и а_ъ..., а_п по неубыванию с помощью алгоритма сортировки слияниями:

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

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

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

9. Реализовать алгоритм быстрого поиска в отсортированном массиве. Если задан­ное число будет найдено, поместить по адресу 76 его адрес, иначе — число (— 1).

10. Разработать программу ввода и размещения в памяти двумерного массива. Решить следующие задачи (результат вывести на экран):

а) упорядочить элементы каждой строки по возрастанию;

б) упорядочить элементы каждого столбца по возрастанию;

в) элементы каждой строки с четным номером упорядочить по возраста­нию, с нечетным — по убыванию;

г) найти сумму элементов главной диагонали квадратной матрицы;

д) на месте каждого элемента записать частное от его деления на номер столбца, в котором он расположен;

е) на месте каждого элемента записать частное от его деления на минималь­ный элемент той строки, в которой он расположен;

ж) если сумма индексов максимального элемента массива четная, поместить по адресу 76 число 1, иначе — число —1;

3) каждый элемент массива увеличить на разность его первого и второго индекса;

и) все элементы квадратной матрицы, лежащие выше главной диагонали,

умножить на данное число к;

к) все элементы квадратной матрицы, лежащие ниже главной диагонали, заменить на нуль;

л) если выше главной диагонали лежит больше чисел, кратных заданному к, чем ниже главной диагонали, то поместить по адресу 76 число 1, если поровну — 0, если меньше — — 1; м) порядок квадратной матрицы нечетный. Поменять местами среднюю строку и средний столбец.

11. Разработать способ представления в памяти «Е97» действительных чисел. Написать следующие подпрограммы:

а) ввод действительного числа;

б) вывод действительного числа;

в) сложение двух действительных чисел;

г) вычитание двух действительных чисел;

д) умножение двух действительных чисел.

12. Разработать способ представления в памяти «Е97» четырехбайтовых целых чисел со знаком. Написать следующие подпрограммы:

а) ввод числа; б) вывод числа;

в) сложение двух чисел; г) вычитание двух чисел;

д) умножение двух чисел;

е) целочисленное деление двух чисел;

ж) нахождение остатка от деления одного числа на другое.

13. Разработать способ представления в памяти «Е97» величин типа «множе­ство». Написать следующие подпрограммы:

а) объединение множеств;

б) пересечение множеств;

в) разность множеств;

г) вхождение элемента в множество (результат ТКЕТЕ или РАЕ8Е).