Проблема:
Вы должны отсортировать массив в порядке возрастания (перестановка: числа от 1 до N в случайном порядке), используя серии перестановок. Каждый своп имеет свою цену, и существует 5 типов цен. Напишите программу, которая сортирует данный массив по наименьшей цене.
Существует два вида цен: priceByValue и priceByIndex . Все цены вида указаны в двух двумерных массивах N * N. Пример, как получить доступ к ценам:
Вы хотите поменять местами 2-й и 5-й элементы перестановки со значениями 4 и 7. Цена для этого свопа будет PriceByValue [4] [7] + priceByIndex [2] [5] .
Индексы всех массивов отсчитываются от 1 (а не от 0), чтобы иметь доступ ко всем ценам (значения элементов перестановки начинаются с 1): priceByIndex [2] [5] фактически будет PriceByIndex [ 1] [4] в коде. Более того, порядок индексов, по которым вы получаете доступ к ценам из двумерных массивов, не имеет значения: priceByIndex [i] [j] = priceByIndex [j] [i] и priceByIndex [i] [i] всегда равны 0. (priceByValue - то же самое)
Виды цен :
Цена [i] [j] = 0;
Цена [i] [j] = случайное число от 1 до 4 * N;
Цена [i] [j] = | i-j | * 6;
Цена [i] [j] = sqrt (| i-j |) * sqrt (N) * 15/4;
Цена [i] [j] = max (i, j) * 3;
При доступе к ценам по индексу i и j являются индексами элементов, которые вы хотите обменять из исходного массива; при доступе к ценам по значению i и j являются значениями элементов, которые вы хотите обменять из исходного массива. (И они всегда отсчитываются от 1)
Вещи даны:
N - целое число от 1 до 400 , смешанный массив, тип priceByIndex, матрица priceByIndex, тип priceByValue, матрица priceByValue. (все элементы матрицы относятся к данному типу)
Вещи, которые должны «появиться на экране»: количество свопов, все свопы (только по индексу - 2 5 означает, что вы поменяли 2-й и 3-й элементы) и цена.
Поскольку я все еще изучаю C ++, мне было интересно, каков наиболее эффективный способ сортировки массива, чтобы попытаться найти сортировку с наименьшими затратами.
Может быть способ получить доступ к серии перестановок, которые приводят к сортировке массива и посмотреть, какой из них имеет наименьшую цену, и мне нужно отсортировать массив, поменяв местами элементы, близкие по значению и индексу, но я не знаю, как это сделать. Буду очень признателен, если кто-нибудь подскажет, как найти самый дешевый сорт в коде . Заранее спасибо!
Подробнее: эта проблема может не иметь решения , я просто пытаюсь получить результат, близкий к идеальному.