Strona 1 z 1
algorytm wybierania konkretnych par liczb
: 27 paź 2010, o 19:37
autor: 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
algorytm wybierania konkretnych par liczb
: 12 lis 2010, o 21:15
autor: 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
algorytm wybierania konkretnych par liczb
: 12 lis 2010, o 23:02
autor: 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})}\).
algorytm wybierania konkretnych par liczb
: 12 lis 2010, o 23:13
autor: 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.
algorytm wybierania konkretnych par liczb
: 13 lis 2010, o 10:51
autor: PMichalak
Istotnie.
algorytm wybierania konkretnych par liczb
: 13 lis 2010, o 17:25
autor: Piotr20
PMichalak pisze: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.
algorytm wybierania konkretnych par liczb
: 13 lis 2010, o 18:22
autor: abc666
Masz rację. Jednak lepiej przejść po pętli tak jak PMichalak i od razu przy znalezieniu pary wypisać obie permutacje