Algorytm dla ciągu

[remplay]

Witam, mam problem z napisaniem poniższych algorytmóm; nie wiem jak się za to zabrać.

Treść:

Zaproponuj algorytm, który dla danego ciągu A(1),...,A(m) różnych liczb naturalnych i danej liczby x, drukuje wszystkie pary liczb (p,q), takie że A(p) * A(q) = x :
(a) gdy ciąg jest dowolny
(b) gdy ciąg jest uporządkowany i oszacuj koszt zaproponowanych algorytmów.

Będę wdzięczny za każdą pomoc z tym zadaniem :>

[argv]

To co przychodzi mi do głowy ad hoc:

- (1) możemy zapuścić sortowanie w czasie \(\displaystyle{ O(nlogn)}\) i mamy (2)
- (2) skoro mamy ciąg posortowany możemy wyszukiwać binarnie. Dla każdego elementu \(\displaystyle{ y}\)
szukamy więc binarnie elementu \(\displaystyle{ z}\) t. że \(\displaystyle{ a[y] \cdot a[z] = x}\)
Mamy n elementów, dla każdego binsearch \(\displaystyle{ O(logn)}\), co razem daje koszt \(\displaystyle{ O(nlogn)}\)

[paladin]

Dla uporządkowanego ciągu można zrobić to w czasie liniowym. Ustawić jeden wskaźnik na początek, drugi na koniec, i dopóki się nie spotkają, przesuwać jeden z nich - dolny jeśli iloczyn jest za mały, górny jeśli za duży.

[Inkwizytor]

Po posortowaniu (bez straty ogólności załóżmy że niemalejąco):

Kod: Zaznacz cały

Dla p=1 do m rób
    i=p
    dopóki "i mniejsza lub równe m" rób
          Jesli A[p]*A[i]=x to wypisz (p,i) oraz (i,p) \ obie pary gdy kolejność ma znaczenie
          i=i+1

- krok \(\displaystyle{ i=p}\) powoduje że przeszukujesz trójkąt z przekątną macierzy "m na m"
- przed wykonaniem iloczynu można by sprawdzić czy kolejny wzięty element nie jest równy elementowi wziętemu krok wcześniej, ale pytanie czy krok sprawdzający nie bedzie nas wiecej kosztował niż prosty warunek z iloczynem?
- mozna najpierw pokusić się o rozkład x na czynniki -> wszystkie możliwe pary czynników i sprawdzać czy takie pary istnieją. Przy ciągu uporządkowanym nie bedzie to trudne.

[abc666]

Inkwizytor, zastanów się nad złożonością twojego rozwiązania.