algorytm wybierania konkretnych par liczb

[baracuda2]

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


witam prosze o pomoc z algorytmem

[Piotr20]

Kod: Zaznacz cały

for(int i=0; i< (sizeof(A)/sizeof(int)); i++)
		for(int j=0; j<(sizeof(A)/sizeof(int)); j++)
			if(A[i]*A[j] == x)
				cout << "A[" << i+1 << "] * [A" << j+1 << "] = " << x << endl;

Pozdrawiam

[PMichalak]

Twój algorytm wykonuje niepotrzebnie \(\displaystyle{ O(n^{2})}\) dzieleń... i wypisuje możliwe pary dwa razy, poniżej poprawiona nieznacznie wersja:

Kod: Zaznacz cały

for(int i=0; i< A.size(); i++)
      for(int j=i; j<A.size(); j++)
         if(A[i]*A[j] == x)
            cout << "A[" << i+1 << "] * [A" << j+1 << "] = " << x << endl;

Da się to jednak zrobić lepiej:
1. Posortować ciąg.
2. Dla każdego elementu \(\displaystyle{ p}\) wyszukać binarnie element \(\displaystyle{ q}\) taki, że \(\displaystyle{ pq = x}\).

Dzięki temu otrzymasz złożoność \(\displaystyle{ O(nlogn)}\) zamiast \(\displaystyle{ O(n^{2})}\).

[abc666]

PMichalak, można posortować ciąg a potem w czasie liniowym znaleźć wszystkie te pary, przesuwając się z końców. Jeżeli dla danego \(\displaystyle{ p}\) znaleźliśmy \(\displaystyle{ q}\) to dla większego \(\displaystyle{ p'}\) nasze \(\displaystyle{ q'}\) nie może być większe niż \(\displaystyle{ q}\).

I tak pozostaje złożoność sortowania ale nie trzeba pisać szukania binarnego.

[PMichalak]

Istotnie.

[Piotr20]

Twój algorytm wykonuje niepotrzebnie \(\displaystyle{ O(n^{2})}\) dzieleń... i wypisuje możliwe pary dwa razy...

Gdyby każdą możliwą parę A(p) * A(q) potraktować osobno to:

\(\displaystyle{ A(1) * A(2)

bo p=1 \wedge q=2

A(2) * A(1)

bo p=2 \wedge q=1}\)

Z tego względu mój algorytm wypisywał wszystkie możliwe pary.

[abc666]

Masz rację. Jednak lepiej przejść po pętli tak jak PMichalak i od razu przy znalezieniu pary wypisać obie permutacje