Помогите, решить, или подсказать где искать решение задачки, условие распространенное, но нигде не могу найти:(

           "Определите, какое наименьшее количество операций обмена между парами элементов нужно сделать для данного начальго расположения, чтобы отсортировать числа в элементах памяти по возврастанию
            Формат входных данных:
            Первая строка файла SORT.DAT содержит натуральное число N (1=<N=<30000).
            Вторая строка файла содержит N попарно разных чисел, которые расположены соответственно в первом, втором, ...,  N элементе памяти в начале сортировки. Все числа находятся в интервале от 0 до 30000 включительно.
           Формат выходных данных:
           Файл SORT.SOL должен содержать одно число M - наименьшее возможное количество операций обмена между парами элементов памяти для достижения расположения чисел в порядке возврастания.

Например:
 ----------------SORT.DAT--------   --------SORT.SOL--------
-------------------------------------   ----------------------------
5                                                --               6           ---
1          6        5      9         8       --                            --- 
-------------------------------------    ---------------------------

Для данного примера числе можно предложить такие обмены:

1) 16598->61598,
2)           61598->51698,
3)                    51698->15698,
4)                               15698->95618,
5)                                        95618->85619,
6)                                                 85619->15689.

Нужно срочно, времени почти нет, сдавать нужно, а выучить за день не смогу, книги купил, литературы хватает, помогите пожалуйста!

Это не наименьшее количество обменов... Наименьшее (без каких-либо дополнительных условий, так, как это написано в задании) = 2 (6 <-> 5  и 9 <-> 8)... После второго обмена числа будут уже расположены в порядке возрастания. Так что ты сначала условие в порядок приведи, а потом решить пытайся...

Ах, так оно еще и дубликат: http://forum.vingrad.ru/forum/topic-236609.html ? Закрыто...

Это сообщение отредактировал(а) volvo877 - 18.11.2008, 01:30