Помощь - Поиск - Пользователи - Календарь
Полная версия: Перестановки
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
gamordzhoba
2.12.2005 1:36
Дана перестановка. Наименьшее число обменов, чтобы ее отсортировать.

Входные данные
Число N (1 <= N <= 10000), затем перестановка.

Выходные данные
Выведите ответ.

Пример

Ввод

5
1 4 3 5 2


Вывод

2

Что то не получается.
klem4
2.12.2005 13:57
провести сортировку и подсчитать кол-во перестановок ? Если массив менять не надо то просто сдлать ф-ю, параметром которой будет массив, а возвращать она будет кол-во перестановок, ну а в ней уже использовать например метод пузырька ... а как интересно еще можно подсчитать число перестановок ?!
virt
2.12.2005 15:44
немного не то :

массив 4 3 2 1 можно отсортировать за 2 операции обмена ,а пузырек отсортирует за 6. Аналогично и для любой другой сортировки можно составить подобный тест.

Задачи решается динамически (не путать с динамической памятью) ,только сейчас не знаю как.

ЗЫ
можно и перебором ,но это очень долго.
volvo
2.12.2005 16:03
Нашел вот такой алгоритм (на форуме AlgoList-а) :
Цитата
Объясню алгоритм на примере: нам дано 5 чисел (перестановка)
4 3 2 5 1
Чтобы 1 оказалось на своем месте, нужно куда-то деть 4. Лучше деть 4 на ее место. Но тогда нужно деть куда-то 5. А 5 нужно деть туда, где 1!

Поэтому требуется найти все такие цепочки чисел a1,a2,..ak, где a1 стоит на месте a2, a2 стоит на мете a3 и т.д., ak стоит на месте a1. В этом примере будут такие цепочки:
4 1 5
3 2
А наименьшее количество таких перемещений, за которое можно это дело отсортировать, есть сумма длин всех таких цепочек. То есть эта сумма равна количеству элементов, которые не совпадают с номером своего места.
Поэтому когда у нас не перестановка, а просто набор чисел, нужно сначала подсчитать порядковую статистику каждого элемента (O(n*log(n)), если использовать быструю сортировку), а потом подсчитать количество элементов, которые стоят "не на своем месте". Это количество и есть минимальное возможное число перемещений.
Atos
2.12.2005 16:39
Цитата
А наименьшее количество таких перемещений, за которое можно это дело отсортировать, есть сумма длин всех таких цепочек.
А вот и неточность, правильно сумма уменьшенных на единицу длин цепочек. Ведь, например, для цепочки из двух элементов мы можем вернуть их на свои места за один обмен.
Но в общем идея ясна, достаточно простой линейный алгоритм получается...
gamordzhoba
4.12.2005 2:33
нифига парни не получается. мож я вас не так понял, но я делаю и не получается.
volvo
4.12.2005 3:05
Покажи, как делаешь...
roma
4.12.2005 3:59
Вот недавно делал похожую прогу, вот что из нее получилось:

var
  mas:array[1..100000] of longint;
  c:array [1..100000] of boolean;
  k,sum,d,i,n:integer;

begin
  ReadLn(N);
  for i:=1 to N do
  begin
   Read(k);
   mas[k]:=i;
  end;
  sum:=0;
  i:=1;
  repeat
   while (c[i]) and (i<=n) do inc(i);
   if i>n then break else c[i]:=true;
   k:=mas[i];
   c[k]:=true;
   d:=1;
   while i<>k do
   begin
    inc(d);
    c[k]:=true;
    k:=mas[k];
   end;
   sum:=sum+d-1;
  until false;
  Writeln(sum);
end.

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.