Основы программирования на C++, PASCAL

... ≤ х[р], у[1] ≤ ... ≤ y[q], z[1] ≤ ... ≤ z[r]. Найти одно из таких чисел или сообщить о его отсутствии.

16. Дана целочисленная таблица А[п]. Найти наименьшее число K элементов, которые можно выкинуть из данной последовательности, так чтобы осталась возрастающая подпоследовательность.

17. Разделить массив на две части, поместив в первую элементы, большие среднего арифметического их суммы, а во вторую — меньшие (части не сортировать).

Сортировка массивов

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

2. Даны две последовательности a1 ≤ a2 ≤ ... ≤ an, и b1 ≤ b2 ≤ ... ≤ bm.Образовать из них новую последовательность чисел так, чтобы она тоже была неубывающей. Примечание. Дополнительный массив не использовать.

3. Сортировка выбором. Дана последовательность чисел а1, а2,..., аn. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый — на место наибольшего. Затем, начиная со второго, эта процедура повторяется. Написать алгоритм сортировки выбором.

4. Сортировка обменами. Дана последовательность чисел а1, а2,..., аn. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа ai и ai+1. Если аi > ai+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не станут расположены в порядке возрастания. Составить алгоритм сортировки, подсчитывая при этом количества перестановок.

5. Сортировка вставками. Дана последовательность чисел а1, а2,..., аn. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть а1, а2,..., аi — упорядоченная последовательность, т.е. а1 ≤ a2 ≤ ... ≤ аi. Берется следующее число ai+1 и вставляется в последовательность так, чтобы новая последовательность была тоже возрастающей. Процесс производится до тех пор, пока все элементы от i +1 до n не будут перебраны. Примечание. Место помещения очередного элемента в отсортированную часть производить с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции.

6. Сортировка Шелла. Дан массив п действительных чисел. Требуется упорядочить его по возрастанию. Делается это следующим образом: сравниваются два соседних элемента аi и ai+1. Если аi ≤ ai+1, то продвигаются на один элемент вперед. Если аi > ai+1, то производится перестановка и сдвигаются на один элемент назад. Составить алгоритм этой сортировки.

7. Пусть даны две неубывающие последовательности действительных чисел a1 ≤ a2 ≤ ... ≤ аn и b1 ≤ b2 ≤ ... ≤ bm. Требуется указать те места, на которые нужно вставлять элементы последовательности b1, b2, ..., bm в первую последовательность так, чтобы новая последовательность оставалась возрастающей.

8. Даны дроби

,
, ...,
 (рi, qi — натуральные). Составить программу, которая приводит эти дроби к общему знаменателю и упорядочивает их в порядке возрастания.

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

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

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

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

10. Сортировка подсчетом. Выходной массив заполняется значениями —1. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений —1. После этого оставшиеся в выходном массиве позиции со значением —1 заполняются копией предыдущего значения.

11. «Хитрая» сортировка. Из массива путем однократного просмотра выбирается последовательность элементов, расположенных в порядке возрастания, переносится в выходной массив и заменяется во входном на —1. Затем оставшиеся элементы включаются в полученную упорядоченную последовательность методом «погружения», когда очередной элемент путем ряда обменов «погружается» до требуемой позиции в уже упорядоченную часть массива.