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 ??:
Okręgi dzielą płaszczyznę
-
- 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ę
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ą
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