Линейная сортировка. Вычисление длины кривой

1. Линейная сортировка

Дана последовательность А из n целых чисел, которые находятся в диапазоне от некоторого min до некоторого max. Тогда алгоритм линейной сортировки состоит в следующем:

1. Определить значения min, max и определить диапазон значений m = max – min + 1.

2. Обнулить вспомогательную последовательность счетчиков B(m), где m – размер последовательности B.

2. Просматривая последовательность А, для каждого элемента a_i выполнить k = a_i – min и B[k] = B[k] + 1.

3. Просматривая последовательность В, для каждого элемента b_i занести в А последовательно b_i элементов со значением i.

На рисунке приведен пример сортировки последовательности из 10 элементов методом линейной сортировки.

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

2. Вычисление длины кривой

Вычислите длину кривой с точностью e в интервале [x₁, x₂], заданную функцией y = a*sin(b*x), путем аппроксимации кусочно-линейной функцией, где a, b – коэффициенты уравнения;

x₁, x₂– границы интервала для расчета значений функции;

e – точность, с которой осуществляется вычисление длины кривой.

Для достижения требуемой точности вычислений длины кривой шаг вычислений каждый раз должен уменьшаться в 2 раза, то есть интервал [x₁, x₂] должен делится сначала на 1 участок, затем на 2, 4, 8, 16, … участков.

Тестовые данные:

Исходные данные	Результат
a = 1.5 b = 2.5 x₁ = 0 x₂ = 1 e = 0.000001	L = 2.40656658209591
a = 1.5 b = 2.5 x₁ = 0 x₂ = 1 e = 0.000000001	L = 2.40656675314635
a = 1 b = 1 x₁ = 0 x₂ = 3.14 e = 0.000000001	L = 3.81794543708538
a = 1 b = 1 x₁ = 0 x₂ = 6.28 e = 0.000000001	L = 7.63589087703246

3. Поезд

Имеется состав из N плацкартных вагонов. Вагоны стандартные: по 54 места в каждом, места разделены на 9 купе. Расположение мест и вагонов показано на рисунке:

Необходимо разместить в поезде М человек так, чтобы расстояние между двумя самыми удалёнными друг от друга людьми было минимальным. Расстояние измеряется по прямой вдоль вагонов. Будем считать, что расстояние между местами в одном купе равно нулю. Например, расстояние между всеми местами 1, 2, 3, 4, 53 и 54 равно нулю. Между местами в соседних купе расстояние равно 1. Например, между местами 1 и 6, 53 и 7. Расстояние между вагонами равно 6. То есть расстояние между местом 33 первого вагона и местом 1 второго вагона равно 6.

Рассмотрим пример из одного вагона (первый тест):

Серым помечены занятые места, а белым – свободные. Нужно разместить 6 человек. Оптимально будет занять места (30, 32, 37, 38, 39, 40) или (30, 32, 39, 40, 41, 42). Наименьшее расстоянием будет равно 1.

Задание: разработать программу, которая для заданного числа вагонов n (1 £ n £ 3) и количества людей m (1 £ m £ 100) определяет расстояние их оптимального размещения в поезде или выдает сообщение “Пассажиров разместить невозможно”.

Каждый вагон представляется строкой по 54 символа (места в вагоне): 0 – место свободно, 1 – занято.

Тестовые данные:

Исходные данные	Результат
n = 1 m = 6 вагон 1 =
n = 2 m = 2 вагон 1 = вагон 2 =