Okręgi dzielą płaszczyznę

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mctl
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 2 lis 2006, o 21:33
Płeć: Mężczyzna
Lokalizacja: Inąd
Podziękował: 8 razy

Okręgi dzielą płaszczyznę

Post autor: mctl »

Na płaszczyźnie danych jest \(\displaystyle{ n}\) okręgów. Jaka jest maksymalna liczba obszarów na które dzielą one płaszczyznę? Wyprowadź rozwiązanie za pomocą odpowiedniej zależności rekurencyjnej.
Help

Edit:
Hm tutaj znalazłem coś: ... rcles.html
ale nie widze nigdzie zależności rekurencyjnej ??:
ampersand
Użytkownik
Użytkownik
Posty: 31
Rejestracja: 29 gru 2006, o 17:22
Płeć: Mężczyzna
Lokalizacja: Sleepy Hollow
Podziękował: 9 razy
Pomógł: 1 raz

Okręgi dzielą płaszczyznę

Post autor: ampersand »

Najpierw zobacz w ilu punktach przecinają się okręgi aby powstała maksymalna ilość podziałów.
Dla 1 okręgu - 0
Dla 2 okrógów - 2
Dla 3 okręgów - 4
Dla 4 okręgów - 6
...
Łatwo więc ustalić wzór na liczbę punktów przecięcia: 2n-2
Teraz jak liczba przecięc ma się do liczby podziałów:

Liczba okręgów Liczba przecięć Liczba podziałów
1 0 2
2 2 4
3 4 8
4 6 14
...
Tu już widać zależność rekurencyjną

Kod: Zaznacz cały

D(n) = { 2 dla n=1
           { 2n-2+D(n-1) dla n >= 2
ODPOWIEDZ