Witam , muszę znaleźć sposób na przekształcenie wektora inwersji permutacji w orginalny ciąg przy pomocy drzewa przedziałowego. Potrzebuje jakiegoś hinta , wskazówki, zupełnie nie mam pomysłu na to .
Dziękuję za wszystkie sensowne odpowiedzi -- 29 cze 2012, o 13:30 --A więc rozwiązałem już problem, napisze pewne wskazówki dla tych którzy kiedyś będą jeszcze mieli podobny problem.
Algorytm będzie konstruował oryginalny ciąg "od końca" czyli najpierw ostatni element, potem przedostatni itp. Spróbuj odpowiedzieć na następujące 3 pytania:
1) Jak mając dany wektor inwersji wyznaczyć ostatni element ciągu oryginalnego?
2) Załóżmy że udało Ci się obliczyć pewien sufiks ciągu oryginalnego, i chcesz policzyć kolejny element w kolejności "od końca". Załóżmy też że przechowujesz jakoś informacje o zbiorze liczb których jeszcze nie użyłeś. Którą liczbę z tego zbioru chcesz teraz użyć?
3) Jak użyć drzewa przedziałowego tak, by efektywnie przechowywać informacje o zbiorze liczb jeszcze nie użytych i w kolejnych krokach szybko uzyskać liczbę której szukasz?
[Algorytmy] Przekształcenie wektora inwersji permutacji
-
- Użytkownik
- Posty: 22
- Rejestracja: 6 sty 2012, o 13:50
- Płeć: Mężczyzna
- Lokalizacja: Mszczonów
- Podziękował: 1 raz
- Pomógł: 1 raz
[Algorytmy] Przekształcenie wektora inwersji permutacji
Ostatnio zmieniony 27 cze 2012, o 17:25 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.