Mamy ciąg np
<1,2,3,4,5,6>
<5,6,4,2,3,1>
Chcę znaleźć permutację tego ciągu od wartości najwyższej do najniższej, czyli
<2,1,3,5,4,6>
<6,5,4,3,2,1>
Proszę o pomoc. Choćby algorytm w pseudokodzie. Program piszę w delphi.
Mamy ciąg np
<1,2,3,4,5,6>
<5,6,4,2,3,1>
Chcę znaleźć permutację tego ciągu od wartości najwyższej do najniższej, czyli
<2,1,3,5,4,6>
<6,5,4,3,2,1>
Proszę o pomoc. Choćby algorytm w pseudokodzie. Program piszę w delphi.
chcę znaleźć permutację tego ciągu od wartości najwyższej do najniższej
E... czyli po prostu chcesz go posortować, tak?
Właśnie chcę posortować tablicę, tylko żeby nie mieć w tej tablicy jako wartości - wartości ciągu, a miejsca w ciągu.
Najprościej będzie posortować tablicę i porównać, który element gdzie się znajduje po posortowaniu.
Z tego co widzę, to są to dwa ciągi, a nie jeden. Dodatkowo, miejsce w ciągu górnym odpowiada miejscu w ciągu dolnym – jeśli przesuniemy w pierszym ciągu pierwszy element, to w dolnym też musimy, tak aby zachować pary według ”kolumn”.
W takim razie wystarczy prosta tablica, w której każda komórka przechowuje dwie liczby – jedna z górnego ciągu i jedna z dolnego:
type
TValuePairs = array of record
A, B: UInt8
end;
Teraz wystarczy zadeklarować zmienną tego typu, pobrać liczbę elementów w ciągu, ustawić rozmiar tablicy za pomocą SetLength
i wczytać liczby do tablicy. Na koniec przeprowadzić dowolne sortowanie (możesz zacząć od bąbelkowego), które za warunek swapa przyjmie porównanie dwóch sąsiednich elementów dolnego ciągu.
Podczas swapa – zamiast zamieniać miejscami liczby – zamień miejscami całe rekordy. Dzięki temu pary liczb zawsze będą trzymać się razem (to zapewnia zgrupowanie par liczb w strukturze).
Zastosowałem sortowanie bąbelkowe, a następnie odwróciłem tablicę od końca do początku.
Ale wiesz, że równie dobrze mogłeś po prostu zastosować sortowanie bąbelkowe i zmienić dosłownie jeden operator tak, aby sortowało malejąco? :-P
Racja. Ale gafa:)