GoldenLine
Zaloguj się

konto usunięte

Temat: algorytm wyszukiwania

Witam, jest w stanie ktoś mi pomóc w rozwiązaniu problemu ?
mianowicie muszę napisać program wyszukujący w czasie liniowym O(n) w tablicy jednowymiarowej parę liczb i przypisanie ich do zmienych pozA oraz pozB.
np,

z tablicy 2,1,2,4,5,5,6,4
ma mi zapisać dla wartości 2 do zmiennej pozA=1 , pozB=3
następnie dla wartości 5 pozA=5, pozB=6
i tak w pętli dalej.

Ktoś podsunie pomysł jakiegoś algorytmu pseudokodu cokolwiek ?
Dzięki z góry !
Link do wypowiedziLink

konto usunięte

Temat: algorytm wyszukiwania

Dzień dobry,

można prosić o jakieś szczegóły?
1. jaka to para?
2. ile tych par szukamy? jednej konkretnej czy wielu?
3. tablica z jakich liczb się składa, co właściwie reprezentuje?

Na podstawie Twojego opisu trudno mi podać jakieś szczególne rozwiązanie. Dla mnie jest zbyt ogólny.
Link do wypowiedziLink

konto usunięte

Temat: algorytm wyszukiwania

oczywiście że można :)
1. Jest to dowolna para liczb, taka sama czyli np. dwie trójki, dwie czwórki, dwie piątki itd.
2. Szukamy wszystkich par tzn. jeśli występuje w tablicy 1,2,3,4,5,0,1,2,3,4,5,6,7
to muszę wyszukać pozycję na których się liczby powtarzają czyli np.
dla wartości 1 : pozA=0, pozB=6, enter i dla wartości 2: pozA=1 a pozB=7 itd.
3. tablica składa się z intów - tylko i wyłącznie

i muszę wypisać wszystkie te pozycję jedna pod drugą w których te liczby się powtarzają.
no i najważniejsze musi być to złożoność O(n).
czyli pewnie należy wykorzystać jakąś dodatkową tablicę do tego
Link do wypowiedziLink

konto usunięte

Temat: algorytm wyszukiwania

Tak na szybko to bym zrobiła tak:

utworzyła drugą tablicę, dokładniej mi chodzi o tablicę list. Oznaczmy tą tablicę jako T. i-ty element tablicy T wskazuje na listę. Początkowo to będzie null.

Dane:
tablica początkowa Tp
tablica list T
lista pozycji elementu L

dla każdego elementu Tp
T[element] -> L.dodaj(pozycje elementu)

Zapis bardzo profesjonalny nie jest ale mam nadzieję, że ideę przekazałam.

Wady. Trzeba utworzyć tablicę list. Tablica musi zawierać wszystkie możliwe elementy. Jeśli jest dużo elementów, to lokujemy miejsce dla bardzo dużej tablicy. Jeśli się zdarzy dodatkowo, że dane nie są rozłożone równomiernie, to możemy otrzymać coś w rodzaju macierzy rzadkiej (metody numeryczne). Zatem potrzebna jest optymalizacja.
Link do wypowiedziLink

konto usunięte

Temat: algorytm wyszukiwania

Dziękuję Ci.
Postaram się to przerobić w kod :)
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Szybki algorytm wyszukiwani...




Wyślij zaproszenie do
Anuluj