[Algorytmy] Wyznacz pary spełniające równanie

akinom164
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 5 lut 2011, o 18:50
Płeć: Kobieta
Lokalizacja: warszawa

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: akinom164 »

Zaproponuj algorytm, który dla danego ciągu \(\displaystyle{ A[1],\ldots, A[n]}\) różnych liczb naturalnych i danej liczby \(\displaystyle{ x}\), wyznacza wszystkie pary liczb \(\displaystyle{ (p,q)}\), takie, że \(\displaystyle{ A[p]\cdot A[q] = x}\).

Mam taki problem jak napisać specyfikację do takiego zadania i sprawdzić poprawność tego algorytmu wzgledem podanej specyfikacji. Pomocy do poniedziału muszę odaddać to zadanie
Ostatnio zmieniony 12 lis 2011, o 12:30 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Awatar użytkownika
Konikov
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 13 mar 2008, o 18:56
Płeć: Mężczyzna
Lokalizacja: z całki tego świata
Podziękował: 66 razy
Pomógł: 44 razy

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: Konikov »

Specyfikacja == algorytm na kartce?

Najprostszy algorytm:
1. bierzesz 2 wskaźniki, nazwijmy je \(\displaystyle{ pierwszy}\) i \(\displaystyle{ drugi}\)
2. \(\displaystyle{ pierwszy}\) ustawiasz na \(\displaystyle{ 1}\), \(\displaystyle{ drugi}\) na \(\displaystyle{ 2}\)
3. sprawdzasz, czy \(\displaystyle{ A[pierwszy] * A[drugi] == x}\). Jeśli tak - robisz z tym cokolwiek masz robić (np. wypisywać)
4. dodajesz jedynkę do \(\displaystyle{ drugi}\)ego, by go przesunąć o jedno pole
5. jeśli \(\displaystyle{ drugi <= n}\), wracasz do punktu (2.). Jeśli nie, to dodajesz \(\displaystyle{ 1}\) do \(\displaystyle{ pierwszego}\)
6. jeśli \(\displaystyle{ pierwszy < n}\), ustawiasz \(\displaystyle{ drugi}\) na \(\displaystyle{ pierwszy+1}\) i wracasz do (2.)
7. skończone.

Oczywiście zgrabniej wyglądałoby to napisane kodem, ale nie wiem, czy dla Ciebie byłoby to obecnie czytelne.
abc666

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: abc666 »

Już było to kiedyś, ale nie mogę znaleźć. Lepiej posortować ten ciąg (zachować oryginalne klucze gdzieś). Potem ustawić jeden wskaźnika na początek a drugi na koniec. Jeśli iloczyn jest za duży to zmniejszamy pozycję tego drugiego, jeśli za mały to zwiększamy pierwszego. Jeśli jest równy to dowolną z tych operacji wykonujemy. Kończymy gdy wskaźniki się spotkają. Samo wyszukiwanie robimy w czasie liniowym bo w każdym kroku się przesuwamy. Pozostaje złożoność sortowania.
akinom164
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 5 lut 2011, o 18:50
Płeć: Kobieta
Lokalizacja: warszawa

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: akinom164 »

Algorytm ma być na kartce i wole jak to jest napisane słownie niż kodem
Wielkie dzięki za pomoc. A jak zprawdzić poprawność tego algorymu (najlepej prze indukcje) i jaki bedze koszt linowy czy liniowo logarytmiczny? Jeszcze raz wielkie dzięki za pomoc:) , bo ja tego niegdy nie zrozumiem chyba:|
abc666

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: abc666 »

Jeśli zrobisz tak jak napisałem to masz kosz koszt sortowania czyli najlepiej \(\displaystyle{ n\log n}\). Przykład jak to wygląda. Powiedzmy, że już mamy posortowany ciąg taki

\(\displaystyle{ (1,3,5,8,13,15,22)}\)
oraz \(\displaystyle{ x=15}\)

Czerwonym będę oznaczał pierwszy indeks, niebieskim drugi
\(\displaystyle{ ({\color{red}1},3,5,8,13,15,{\color{blue}22})\\
1\cdot 22=22 >15\\
({\color{red}1},3,5,8,13,{\color{blue}15},22)\\
1\cdot 15=15 \text{ zapisujemy gdzie znaleźliśmy} \\
({\color{red}1},3,5,8,{\color{blue}13},15,22)\\
1\cdot 13=13<15\\
(1,{\color{red}3},5,8,{\color{blue}13},15,22)\\
3\cdot 13=39>15\\
(1,{\color{red}3},5,{\color{blue}8},13,15,22)\\
3\cdot 8=24>15\\
(1,{\color{red}3},{\color{blue}5},8,13,15,22)\\
3\cdot 5=15 \text{ zapisujemy gdzie znaleźliśmy}}\)

koniec bo wskaźniki się spotkały

Pamiętaj o zachowaniu oryginalnych kluczy dla ciągu.
akinom164
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 5 lut 2011, o 18:50
Płeć: Kobieta
Lokalizacja: warszawa

[Algorytmy] Wyznacz pary spełniające równanie

Post autor: akinom164 »

Ok dzięki wielkie za pomoc:)-- 13 lis 2011, o 21:28 --A jeszcze jak sprawdzić poprawnośc tego algorytmu??
ODPOWIEDZ