На вход подаётся числовой массив A из n элементов. Требуется найти число инверсий в массиве, т. е. пар индексов (i, j), таких что i<j и a[i] > a[j]. Указание. Модифицируйте алгоритм сортировки слиянием задан 3 Мар '20 3:32 Buba |
На вход подаётся числовой массив A из n элементов. Требуется найти число инверсий в массиве, т. е. пар индексов (i, j), таких что i<j и a[i] > a[j]. Указание. Модифицируйте алгоритм сортировки слиянием задан 3 Мар '20 3:32 Buba |
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
3 Мар '20 3:32
показан
186 раз
обновлен
3 Мар '20 4:10
Найти число инверсий можно многими способами. Например, для каждого элемента найти число меньших, ему предшествующих, а потом всё сложить. Это если подходить "бесхитростно". А можно сортировать, следя за числом перестановок двух элементов.