zadanie 30.1-7. z Cormena:
Rozważmy dwa zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\), każdy zawierajacy po \(\displaystyle{ n}\) liczb naturalnych z przedzialu od \(\displaystyle{ 0}\) do \(\displaystyle{ 10n}\). Chcemy obliczyć sumę kartezjańską zbiorów \(\displaystyle{ A}\) i \(\displaystyle{ B}\) zdefiniowaną następująco:
\(\displaystyle{ C=\{x+y: x \in A \ i \ y \in B \}}\).
Zauwazmy ze liczby ze zbioru \(\displaystyle{ C}\) sa z przedzialu od \(\displaystyle{ 0}\) do \(\displaystyle{ 20n}\). Chcemy znaleźć wszystkie elementy zbioru \(\displaystyle{ C}\) i określić, na ile sposobów każdy z nich daje się zapisać jako suma elementów z \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Wykaż, że problem ten można rozwiązać w czasie \(\displaystyle{ O(n \ lgn)}\) (Wskazówka: Potraktuj \(\displaystyle{ A}\) i \(\displaystyle{ B}\) jako wielomiany stopnia co najwyżej \(\displaystyle{ 10n}\))
z góry dzięki za pomoc
suma kartezjańska zbiorów (Cormen)
-
argv
- Użytkownik
- Posty: 569
- Rejestracja: 27 maja 2009, o 01:27
- Płeć: Mężczyzna
- Podziękował: 51 razy
- Pomógł: 66 razy
suma kartezjańska zbiorów (Cormen)
Przypadkiem odkopałem to zadanie przeszukując forum.
Powiedzmy że mamy dwa zbiory:
\(\displaystyle{ A = \{1,5,6\}}\)
\(\displaystyle{ B =\{0,1,4\}}\)
"Traktujemy" je jako wielomiany biorąc elementy zbiorów jako współczynniki:
\(\displaystyle{ A(x) = x^{1}+x^{5}+x^{6}}\)
\(\displaystyle{ B(x) = x^{0}+x^{1}+x^{4}}\)
mnożymy oba wielomiany dostając wielomian \(\displaystyle{ C(x) = A(x)*B(x)}\).
C[k] mówi nam na ile sposobów można uzyskać sumę k, czyli w powyższym przypadku
uzyskamy wielomian:
\(\displaystyle{ x^{1}+x^{2}+2x^{5}+2x^{6}+x^{7}+x^{9}+x^{10}}\) czyli np. 10 uzyskamy raz (biorac 6,4), 6 uzyskamy dwa razy (5,1), (6,0) a sumy trzy nie uzyskamy ani razu.
Ponieważ wielomiany potrafimy mnożyć za pomocą FFT w \(\displaystyle{ \theta(nlogn)}\) stąd uzyskujemy szukaną złożoność
Uzasadnienie: \(\displaystyle{ C[k]}\) = \(\displaystyle{ \sum_{i=0}^{k} A \cdot B[k-i]}\) a ten iloczyn pod sumą jest równy \(\displaystyle{ 1}\) wtw gdy \(\displaystyle{ A=1}\) i \(\displaystyle{ B[k-i]=1}\) czyli gdy \(\displaystyle{ i \in A}\) oraz \(\displaystyle{ k-i \in B}\)
Powiedzmy że mamy dwa zbiory:
\(\displaystyle{ A = \{1,5,6\}}\)
\(\displaystyle{ B =\{0,1,4\}}\)
"Traktujemy" je jako wielomiany biorąc elementy zbiorów jako współczynniki:
\(\displaystyle{ A(x) = x^{1}+x^{5}+x^{6}}\)
\(\displaystyle{ B(x) = x^{0}+x^{1}+x^{4}}\)
mnożymy oba wielomiany dostając wielomian \(\displaystyle{ C(x) = A(x)*B(x)}\).
C[k] mówi nam na ile sposobów można uzyskać sumę k, czyli w powyższym przypadku
uzyskamy wielomian:
\(\displaystyle{ x^{1}+x^{2}+2x^{5}+2x^{6}+x^{7}+x^{9}+x^{10}}\) czyli np. 10 uzyskamy raz (biorac 6,4), 6 uzyskamy dwa razy (5,1), (6,0) a sumy trzy nie uzyskamy ani razu.
Ponieważ wielomiany potrafimy mnożyć za pomocą FFT w \(\displaystyle{ \theta(nlogn)}\) stąd uzyskujemy szukaną złożoność
Uzasadnienie: \(\displaystyle{ C[k]}\) = \(\displaystyle{ \sum_{i=0}^{k} A \cdot B[k-i]}\) a ten iloczyn pod sumą jest równy \(\displaystyle{ 1}\) wtw gdy \(\displaystyle{ A=1}\) i \(\displaystyle{ B[k-i]=1}\) czyli gdy \(\displaystyle{ i \in A}\) oraz \(\displaystyle{ k-i \in B}\)