Статья Автор: Лебедев Дмитрий

TUZ_5-05 Подсчет количества раундов обработки чисел в порядке возрастания

TUZ_5-05 Подсчет количества раундов обработки чисел в порядке возрастания

TUZ_5-05 Подсчет количества раундов обработки чисел в порядке возрастания
5.5. Подсчет количества раундов обработки чисел в порядке возрастания
В этом задании дается массив чисел, возможно несортированный. Массив заполнен числами от 0 до n – 1.
Цель этого задания – подсчитать количество раундов перестановки чисел, необходимых для упорядочения их в порядке возрастания.
В первом раунде обрабатываются числа в порядке возрастания.
В последующих раундах обрабатываются числа, которые не были обработаны в предыдущих раундах,
и снова в порядке возрастания.
Этот процесс повторяется до тех пор, пока не будут обработаны все числа в порядке возрастания.
Для примера рассмотрим список L = [0, 4, 3, 5, 2, 1].
В первом раунде обрабатываются числа 3, 2 и 1 в порядке возрастания,
          [0, 4, 3, 5, 2, 1] -> [0, 3, 4, 5, 2, 1] -> [0, 3, 4, 2, 5, 1]-> [0, 3,  4,  2, 1, 5]
во втором раунде – только 2 и 1 , 
        [0, 3,  4,  2, 1, 5] ->  [0, 3,  2,  4, 1, 5] ->  [0, 3,  2,  1, 4, 5]
в третьем раунде – тоже 2 и 1,
        [0, 3,  2,  1, 4, 5] -> [0, 2,  3,  1, 4, 5] -> [0, 2,  1,  3, 4, 5]
и в четвертом раунде – 1:   [0, 1,  2,  3, 4, 5]
Следовательно, для обработки данного списка L в порядке возрастания требуется четыре раунда.
Ваша задача: написать функцию, которая принимает перестановку чисел от 0 до n – 1 и возвращает количество раундов.
В табл. 5.5 показаны ожидаемые результаты для некоторых входных данных.
Таблица 5.5. Некоторые ожидаемые результаты для задачи подсчета раундов обработки чисел в порядке возрастания 
Perm Ожидаемый результат
0, 1, 5, 4, 2, 3 3
0, 1, 2, 4, 3, 5 2
4, 11, 2, 8, 6, 9, 5, 3, 0, 10, 1, 12, 7 6
0, 1, 4, 3, 2 3

Алгоритм
Для решения этой задачи используется метод обратной перестановки.
Пусть perm – исходный массив, а inverseperm – массив того же размера, что и perm, заполненный нулями.
Массив inverseperm используется для инверсии заданной перестановки.
Для каждого i в perm инструкция inverseperm [perm [i]] = i инвертирует перестановки.
Для подсчета числа раундов определяется счетчик rounds.
Первоначально переменной rounds присваивается значение 1,
так как всегда существует последовательность чисел в порядке возрастания, мощность которой равна хотя бы единице.
Пусть n – мощность inverseperm, для k = от 1 до n, если inverseperm [k] < inverseperm [k – 1], это означает,
что k находится слева от k – 1 и количество раундов должно быть увеличено на единицу.
Для примера рассмотрим список L = [0, 4, 3, 5, 2, 1].
         Обратная перестановка будет иметь вид L-1=[0, 5, 4, 2, 1, 3]
         пары с "нарушением порядка":  (5,4); (4,2); (2,1) - их 3, значит ответ равен 1+3=4
 


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать