Szukanie Przedziału Liczb

Zadanie

Przesuń w tablicy wartość minimalną na początek tablicy, a maksymalną wartość na koniec. Wykonaj to w jak najmniejszej liczbie kroków. W jednym kroku można zamieniać tylko sąsiednie elementy tablicy.

Przykład

Przykładowo z tablicy [4, 5, 1, 2, 3] chcemy uzyskać tablicę [1, 4, 2, 3, 5]. Możliwe jest to poprzez wykonanie 4 zamian:

Analiza

Zauważmy, że nie istnieje potrzeba symulowania uzyskania tablicy końcowej, ale trzeba wyznaczyć elementy, które mają trafić na początek i na koniec listy. Minimum będzie to pierwsza najmniejsza wartość od lewej strony. Jest to ważne zastrzeżenie, ponieważ elementy w tablicy mogą się powtarzać, więc możliwe, że minimalny element wystąpi więcej niż jeden raz. Podobnie z maksimum, ale tym razem szukamy maksymalnej wartości pierwszej od prawej strony.

Wiedząc, że element jest na pozycji x to wiadomo, że potrzeba x przesunięć, aby znalazł się na początku i n - x, aby na końcu, gdzie n to długość tablicy. Przyjmując, że minimum ma pozycję imin, a maksimum imaks to potrzeba imin + imaks przesunięć, ale wartość tą trzeba pomniejszyć o 1 jeśli imin > imaks, ponieważ wtedy zamiana przesuwanych, dwóch wartości zostałaby policzona podwójnie.

W przedstawionym wcześniej przykładzie wiemy, że imin = 3 (wartość 1), a imaks = 2 (wartość 5), a długość tablicy to n = 5. Wtedy imin + imaks - 1 = 3 + 2 - 1 = 4.

Implementacja

Poniżej został przedstawiony przykładowy kod funkcji ileZamian(), która zwraca ile potrzeba zamian, aby na końcach znalazły się wartości krańcowe. Jako argument przyjmuję tablicę, którą ma przeanalizować.

1. def najmniejZamian(tab):
2.   imin, imax = len(tab) - 1, 0;
3.   for i in range(len(tab)):
4.     if (tab[i] >= tab[imax]):
5.       imax = i
6.     if (tab[i] < tab[imin]):
7.       imin = i
8.   wynik = imin + len(tab) - imax - 1;
9.   if (imin > imax):
10.     wynik -= 1
11.   return wynik

Do znaleziania indeksów wartości miminalnej i maksymalnej wystarczy jedno przejście. W każdej iteracji trzeba sprawdzić dwa warunki. W celu znalezienia wartości maksymalnej korzystamy z porównania większa bądź równa co gwarantuje, że znajdziemy ostatnią, największą wartość w tablicy, a dla minimum nierówność jest ostra, bo chcemy znaleźć pierwszą minimalną wartość. Podczas obliczania końcowego wyniku należy pamiętać, aby zawsze odjąć 1 od wyniku, ponieważ elementy tablicy są indeksowane od 0, a nie 1!

Testowanie funkcji

Działanie funkcji można przetestować przy pomocy poniższego kodu. Wystarczy wprowadzić tablicę i odczytać wynik.

1. print("Podaj tablice:")
2. tab = [int(x) for x in input().split()]
3. wynik = najmniejZamian(tab)
4. print("Potrzebnych zamian:", wynik)

• Kod źródłowy Implementacja