Witajcie, mam takie zadanko, które bardzo pragnąłbym zrozumieć jak je rozwiązać:
Na płaszczyźnie danych jest n okręgów. Jaka jest maksymalna liczba obszarów, na które
dzielą one płaszczyznę. Rozwiąż zadanie za pomocą odpowiedniej zależności rekurencyjnej.
jest to niezla zagadka umyslowa, byc moze ktos sie pokusi o rozwiazanie , w razie czego mozna pisac na priva: gg 4028917 - oferuje uscisk dloni prezesa oraz ewentualnie szesciopak bro. pozdrawiam
mlecik napisał(a)
Witajcie, mam takie zadanko, które bardzo pragnąłbym zrozumieć jak je rozwiązać:
Na płaszczyźnie danych jest n okręgów. Jaka jest maksymalna liczba obszarów, na które
dzielą one płaszczyznę. Rozwiąż zadanie za pomocą odpowiedniej zależności rekurencyjnej.
jest to niezla zagadka umyslowa, byc moze ktos sie pokusi o rozwiazanie , w razie czego mozna pisac na priva: gg 4028917 - oferuje uscisk dloni prezesa oraz ewentualnie szesciopak bro. pozdrawiam
tak sie zastanawiam czy to nie bedzie 2^n
Mysle, tez ze podawanie emaili czy gg mija sie z celem istnienia forum
oraz wydaje mi sie ze rozbicie 2^n (o ile to jest poprawne bo to moja pierwsza mysl po 3 sekundach od przeczytania) na rekurencje jest proste
ok, jesli ktos woli na forum prosze bardzo, jakby ktos jednak byl wstanie poswiecic troche czasu na dialog i wyjasnienie krok po kroku, to bedziemy wszyscy zadowoleni gwarantuje. :)
// tez stawialbym na 2^n ale to musze miec poparte i wyjasnione
F(1)=2; //dla 1 koła mamy obszar w kole i poza kołem
F(n)=F(n-1)+2n-2; //dowód jest prosty, opublikuję go wieczorem w wypadku gdzyby nikt nie dał rady, na razie nie chciał bym zupełnie psuć zabawy tym co lubią rodzaj takiej gimnastyki
ergo
F(n)=n*(n-1)+2
załóżmy że mamy na płaszczyźniej już n okręgów. Jeśli dodamy nowy okrąg tak, że będzie przecinał się z każdym innym okręgiem i dodatkowo w zadnym punkcie nie beda sie przecinac wiecej niz 2 okrego to otrzymamy 2 * więcej obszarów niż poprzednio.
Zostaje tylko pytanie czy można rozłożyć w taki sposób okręgi. Weźmy okręgi o promieniu równym jeden i rozstawiajmy je na prostej o długości 1. Pierwszy okrąg stawiamy na początku i każdy kolejny na prawo od niego. od 0 do 1 mamy nieskończenie wiele punktów na środki okręgów, co więcej taki obszar podzielony przez jakiś punkt nadal ma na prawo nieskończenie wiele punktów. W związku z tym zawsze możemy dokładać kolejne okręgi, które będą spełniały warunki o przecinaniu.
czekam dalej na dowod - podbijam stawke do szesciopaka DOWOLNEGO polskiego piwa :) [browar]
Jeśli mamy na płaszczyźnie n-1 okręgów to dodanie nowego okręgu dodaje ilość obszarów równą ilości przecięć tego okręgu z okręgami które już są na płaszczyźnie (pomijając sytuacje kiedy nie przecina żadnego okręgu, jest styczny z jakimś okręgiem lub stważa sytuację w której 3 okręgi przecinają się w tym samym punkcie, ale te działania nie zwiększą ilości obszarów także jezaniedbujemy), maksymalnie może z każdym okręgiem przeciąć się 2 razy także n-ty okręg dodaje nam maksymalnie 2(n-1) obszarów.
jest to sensowne: jednakze ktorego z tych wzorow uzyc konkretnie ? ktory bardziej rekurencyjny - wg mnei pierwszy...
i jeszcze jedno rzekomo dla okregow n=4 tych obszarow ma wyjsc 16 a wzory daja 14...
gg: 4028917 zapraszam
Dla 4 okregow wydaje mi sie, ze bedzie 14 obszarow, przynajmniej tak wynika z mojego rysunku - http://img97.imageshack.us/img97/4326/kolka.jpg
Rozumowanie @RFabianskiego nie jest dla mnie całkowicie przekonujące. "Dowód" @Thranda jest na pewno błędny: narysowałem cztery okręgi o promieniu 1 i środkach w punktach (0;0), (0;0.5), (0;0.75) oraz (0;0.95) i części jest 14 (a nie 16) http://atos.wmid.amu.edu.pl/~bogdan/images/circles.pdf
Da się 16:
Oczywiście wszystkie okręgi mają ten sam promień.
2n - 2 przecięć, 2n płaszczyzn ;]
edit:
albo i nie ;p
powyższy rysunek chyba przedstawia elipsy ;]
Ok to jeszcze prosze o wyjasnienie dlaczego rzekomo wzor F(n)=F(n-1)+2n-2 jest rownoazny z F(n)=n*(n-1)+2 ?
z czego to wynika?
PS. Takie zadanka to tylko na polibudzie poznanskiej moga byc hehe :)
Sorry, faktycznie są to elipsy. Kurde, rysowałem z shiftem, więc powinny wyjść idealne okręgi, ale teraz patrzę, że jednak nie - widocznie przez przypadek pod koniec rysowania nieświadomie puściłem. Jeszcze raz przepraszam za wprowadzenie w błąd.
F(n)-F(n-1)=n(n-1)+2-((n-1)(n-2)+2)=2n-2 => F(n)=F(n-1)+2n-2
@mlecik bzdura, każdy ma/miał takie zadania na dyskretnej :)
Co do drugiego pytania: rozwiąż to równanie rekurencyjne (jako niejednorodne równanie, albo funkcją tworzącą) po prostu i ci wyjdzie taka odpowiedź.
ps czyli jakie jest ostateczne rozwiązanie tego zadania ???
Shalom napisał(a)
(jako niejednorodne równanie, albo funkcją tworzącą)
Armata na zabicie muchy, przesumować po delta(F(i))=F(i)-F(i-1) i jest od razu w jednej linijce.
Shalom napisał(a)
@mlecik bzdura, każdy ma/miał takie zadania na dyskretnej :)
U niektórych nawet takich łatwych zadań się nie robiło.
