[Algorytmy] Znajdowanie par liczb

[malwina18]

Witajcie, mam takie zdanie, jak sobie z nim poradzic?
Zaproponuj algorytm, który dla danego ciągu \(\displaystyle{ A_1,...,A_n}\) różnych liczb naturalnych i danej liczby \(\displaystyle{ x}\), drukuje wszystkie pary liczb \(\displaystyle{ (p,q)}\), takie że \(\displaystyle{ A_p \cdot A_q = x}\)

-- 23 paź 2012, o 20:54 --

cos takiego ?

Kod: Zaznacz cały

int A[10] = {4,5,23,6,77,2,4,3,8,7};
int x =20;
for(int p=0; p<10; p++)
{	
	for(int q=0; q<10; q++)
	{
		if(A[p]*A[q]==x)
		        cout << "Pary liczb :" << p << " oraz " << q <<endl;
	}
}

[ksisquare]

W ten sposób odwiedzisz każdą parę dwukrotnie, a to grzech
Łatwo zaradzić, np. puszczając pętlę po "q" (ku) nie od zera ale od "p", a może od p+1 (bo czy w parze też mają być różne?)
Tak czy siak będzie kwadratowo, czyli ilość obliczeń jakoś proporcjonalna jest do kwadratu liczby danych.
(to też grzech
Ale, gdyby tak posortować (koszt N log N), później łatwo można zaniechać niepotrzebnej pracy (bo mniej już z pewnością nie da więcej)
Dziś jem orzeszki i piję wódkę, ale to chyba fajne (podchwytliwe) zadanko.
Popatrzę jutro (poniedziałek .-- 28 paź 2012, o 16:04 --

Kod: Zaznacz cały

	for(p=0, k=N-1; p<k; p++ ) {
		while( A[p] * A[k] > x )
			k--;
		if( A[p] * A[k] == x )
			printf("%d %d
", A[p], A[k] );}