Witam. Mam pewien problem. Zadanie jest związane z korelacją. Zadanie polega na tym, że wprowadzam liczby z klawiatury do listy. Lista np { 2,3,4,5,6} i wprowadzam np drugą listę mniejszą od tej pierwszej np [4,5] . I ma wyglądać to tak:
{2,3,4,5,6}
{4,5} -> w pętli przesuwam tą tablice o krok w prawo
Funkcja ma zwracać indeks najlepszego dopasowania liczb.. Czyli w tym wypadku zwróci indeks 2 jeżeli liczę od zera.
Ktoś ma jakiś pomysł jak się za to zabrać?
Obejrzeć kod strstr() powtórzyć go dla tablic liczbowych.
Czyli dowolny kontener a na nim kombinacja find i equal z <algorithm>
Propozycja algorytmu:
Niech {a_1, a_2, a_3, ...}, {b_1, b_2, b_3, ...} będą ciągami wejściowymi, s1, s2 odpowiednio ich długościami.
Niech h_1, h_2, h_3, ... będą haszami następujących podciągów ciągu {a_1, a_2, a_3, ...}:
h1 = hash(a_1, a_2, ..., a_s2)
h2 = hash(a_2, a_3, ..., a_{s2+1})
h3 = hash(a_3, a_4, ..., a_{s2+2})
tj te hasze są haszami odcinków początkowych {a_1, a_2, a_3, ...} długości s2.
Teraz wystarczy sprawdzić, czy hasz({b_1, b_2, b_3, ...}) == h_i dla pewnego i.
Algorytm może stać się liniowy, jeśli będziemy sprytnie liczyć hasze. To już zadanie dla Ciebie.
to ma działać tak długo aż tak lista mniejsza znajdzie taką samą wartość w tej większej liści i wtedy zwrócić indeks :
podaję jeszcze raz przykład bardziej opisany
wprowadzam pierwszą listę z klawiatury, która ma być sygnałem w formie liczb:
czyli np do tablicy wprowadzam takie liczby jak {1,2,3,4,5,6,7,8,9} i to jest moja pierwsza tablica.
następnie wprowadzam drugą tablice tylko, że krótszą od tej pierwszej bo to ma być ten sam sygnał tylko że przesunięty w czasie (korelacja)
czyli wprowadzam np {3,4} - gdzies te liczby musza sie pojawić w tej pierwszej tablicy bo to jest ten sam sygnał
no i teraz funkcja ma działać tak że zwróci mi indeks przesunięcia
przykład
{1,2,3,4,5,6,7,8,9}
{3,4}
porównuje 1,2 z 3,4 - nie zgadza się
przesunięcie
{1,2,3,4,5,6,7,8,9}
{3,4}
nie zgadza się
przesunięcie
{1,2,3,4,5,6,7,8,9}
{3,4}
zgadza i zwraca mi indeks tego przesunięcia czyli tam gdzie jest 3 w jednej i drugiej tablicy . Indeks będzie wynosił 2 bo 1 to indek zerowy 2 to indeks 1 , a 3 to indeks 2
Taka funkcja ma być uniwersalna nie zależnie ile wprowadze liczb do pierwszej tablicy i drugiej ( trzeba pamietać że ta tablica druga zawsze jest mniejsza)
@gogi000 podałem Ci rozwiązanie problemu (jak zresztą @_13th_Dragon). Czekasz na gotowy kod?