Liczenie po chińsku ...okiem programisty

17.08.2009 - Agata Murawska
TrudnośćTrudność

W poprzedniej części artykułu udało nam się rozwiązać zadanie o defiladzie policjantów. Czy przypominasz sobie, jaką metodą rozwiązywaliśmy tamtą zagadkę? Teraz postaramy się zrobić to szybciej i lepiej. Dlaczego? Poniższe zadanie jest bardzo podobne do Wrocławskich policjantów, ale danych jest więcej (choć nie wszystkie są istotne).

Wyspa zagadkowa(*) eksportuje znakomite owoce, spotykane tylko na Wyspie. Pewnego dnia w pakowalni owoców zaszedł interesujący wypadek. Gdy chciano pakować owoce w paczki po 10 sztuk (w każdą paczkę pakowano zawsze tę samą liczbę owoców), zostawało ich 9, gdy pakowano po 9,  to zostawało po 8, gdy pakowano po 8, to zostawało 7. Próbowano pakować coraz mniejszą liczbę owoców do jednej paczki, lecz zawsze zostawało o jeden mniej niż znajdowało się w paczce. Gdy próbowano wreszcie pakować po dwa owoce, został jeden.
Ile owoców przeznaczonych było do wysyłki na eksport?

Żeby je rozwiązać "starą" metodą wykreślania, musielibyśmy sprawdzać wszystkie liczby od $ 1 $ do $ \mathrm{NWW}(2, 3, 4, 5, 6, 7, 8, 9, 10) $. Ta ostatnia liczba nie należy do małych. Wynosi ona 2520. Jeśli najmniejszą wspólną wielokrotnością k danych jest N, to złożoność pamięciowa to także $ \mathrm{O}(N) $, zaś czasowa$ \mathrm{O}(k*N) $.

Drobna modyfikacja pozwala uzyskać poprawę złożoności pamięciowej do $ \mathrm{O}(1) $ - zamiast wykreślać liczby z tabelki po prostu sprawdzamy dla każdej wartości między $ 1 $ a $ N $ reszty z dzielenia. Nadal jednak musimy (pesymistycznie) sprawdzać $ k $ reszt dla każdej z $ N $ możliwości. Nawet dla małych danych wejściowych, $ N $ może być bardzo dużą liczbą.

Jak policzyć to szybciej? O tym za chwilę. Na razie powiedzmy trochę więcej o tej ciekawej własności liczb, mówiącej, że rozwiązanie naszej zagadki istnieje. Nazwaliśmy ją ostatnio chińskim twierdzeniem o resztach. Brzmi ona tak:

Niech $ n_1, n_2, .. n_k $ będą liczbami naturalnymi dodatnimi. Jeśli są one parami względnie pierwsze (będziemy to oznaczać, dla danych $ a, b $$ a \perp b $), to dla dowolnych $ m_1, m_2, .., m_k $ istnieje dokładnie jedna liczba naturalna $ N $ mniejsza od $ n_1*n_2*..*n_k $ taka, że spełnione są równania modulo(**):

$ N \equiv_{n_1} m_1 $
$ N \equiv_{n_2} m_2 $
          ...
$ N \equiv_{n_k} m_k $

Dowód przebiega podobnie, jak gdy pokazywaliśmy, że zadanie o policjantach ma jedno rozwiązanie.

 


(*) Zadanie pochodzi z książki „Łamigłówki logiczne, tom 1” autorstwa L. Bogusza, P. Zarzyckiego i J. Zielińskiego

(**) Oczywiście pod warunkiem, że taki układ nie jest sprzeczny. Na przykład układ: $ N \equiv_4 2 $, $ N \equiv_2 1 $ nie ma rozwiązania.

3.5
Twoja ocena: Brak Ocena: 3.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com