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. static int najmniejZamian(int[] tab) {
2.   int imin = tab.Length - 1, imax = 0;
3.   for (int i = 0; i < tab.Length; i++) {
4.     if (tab[i] >= tab[imax]) {
5.       imax = i;
6.     }
7.     if (tab[i] < tab[imin]) {
8.       imin = i;
9.     }
10.   }
11.   int wynik = imin + tab.Length - imax - 1;
12.   if (imin > imax)
13.     wynik--;
14.   return wynik;
15. }

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. static void Main(string[] args) {
2.   Console.WriteLine("Podaj tablice:");
3.   string[] dane = Console.ReadLine().Split(' ');
4.   int[] tab = new int[dane.Length];
5.   for (int i = 0; i < dane.Length; i++)
6.     tab[i] = Convert.ToInt32(dane[i]);
7.   int wynik = najmniejZamian(tab);
8.   Console.WriteLine("Potrzebnych zmian: {0}", wynik);
9.   Console.ReadKey();
10. }

• Kod źródłowy Implementacja