  |
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
|
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
 |
Matma / Pmocy |
| . 1 . 2 . >> |
| Autor | Wiadomość |
| Posted: 24 Mar 2001 11:07:28 Dzięki że zdecydowałeś się na przeczytanie mojej wiadomości. Z grup dyskusyjnych zacząłem korzystać całkiem niedawno i mam nadzieję, że grupa pomorze mi w moich problemach. Po pierwsze chce się zapytać o symbole jakie są używane w grupie np. co oznacza ^ A właśnie... z drugim już jest trochę gorzej. Otóż za nic w świecie nie mogę sobie poradzić z pewnym zadaniem. Jest to zadanie, którego nikt w mojej klasie ani ze znajomych nie umie rozwiązać. Problem polega na tym: Mamy n punktów w układzie współrzędnych o współrzędnych (x1,y1), (x2,y2), ..., (xn,yn). Należy znaleźć promień najmniejszego okręgu, w którym będą zawarte wszystkie te punkty. Z grubsza wygląda to na proste zadanie, ale nie jest to jednak takie łatwe. W moich przemyśleniach doszedłem do tego, że znajdujemy punkty skrajne tzn. najdalej wysunięty do góry, najdalej na dół, w prawo i w lewo. Następnie kreślimy proste przechodzące przez te punkty, które są zarazem równoległe do odpowiedniej osi układu współrzędnych. Powstaje nam prostokąt, w którym zawarte są wszystkie punkty, ale co dalej? Przypominam, że ma to być najmniejszy promień, więc nie zawsze będzie to połowa przekątnej lub połowa długości prostokąta. Proszę o pomoc. Będę bardzo wdzięczy. |
|
| Qoooba
|
Posted: 24 Mar 2001 11:18:24 A jesli wezmiesz najdalej oddalone i odlegosc podzielisz przez 2, to nie bedzie dobrze ? ;-) ? Kuba Problem polega na tym:
Mamy n punktów w układzie współrzędnych o współrzędnych (x1,y1), (x2,y2), ..., (xn,yn). Należy znaleźć promień najmniejszego okręgu, w którym będą zawart
e wszystkie te punkty.
|
| Jakub Wroblewski
|
Posted: 24 Mar 2001 12:24:46 Witam, A jesli wezmiesz najdalej oddalone i odlegosc podzielisz przez 2,
to nie bedzie dobrze ? ;-) Wyobraz sobie trojkat prostokatny o podstawie sqrt(2) i ramionach 1 (rownoramienny). Najbardziej oddalone sa konce przeciwprostokatnej. Kolo o promieniu sqrt(2) / 2 jest w stanie objac caly trojkat, ale trzeci wierzcholek rowniez lezy na jego krawedzi - a wiec minimalne wydluzenie przyprostokatnych (trojkat przestanie byc prostokatny) spowoduje, ze wierzcholkow nie uda sie pokryc takim kolem (mimo, ze najwieksza odleglosc to nadal sqrt(2) ). Dla trzech punktow rozwiazaniem jest kolo opisane na trojkacie, ale dla wiecej - nie wiem. Pozdrawiam, Jakub Wroblewski |
| Andrzej Komisarski
|
Posted: 24 Mar 2001 12:41:38 Witam,
A jesli wezmiesz najdalej oddalone i odlegosc podzielisz przez 2,
to nie bedzie dobrze ? ;-) Wyobraz sobie trojkat prostokatny o podstawie sqrt(2) i ramionach 1 (rownoramienny). Najbardziej oddalone sa konce przeciwprostokatnej. Kolo o promieniu sqrt(2) / 2 jest w stanie objac caly trojkat, ale trzeci wierzcholek rowniez lezy na jego krawedzi - a wiec minimalne wydluzenie przyprostokatnych (trojkat przestanie byc prostokatny) spowoduje, ze wierzcholkow nie uda sie pokryc takim kolem (mimo, ze najwieksza odleglosc to nadal sqrt(2) ). Dla trzech punktow rozwiazaniem jest kolo opisane na trojkacie, ale dla wiecej - nie wiem. Jest twierdzenie (nie pamiętam szczegółów, kojarzy mi się Young, ale nie jestem pewien, nie pamiętam też, jak się przenosi na wyższe wymiary, ani jak się go dowodziło, choć było to na pewno na poziomie liceum lub prostsze), które mówi, że każdy zbiór na płaszczyźnie o średnicy d daje się przykryć kołem o promieniu d/sqrt(3). |
| Andrzej Komisarski
|
Posted: 24 Mar 2001 15:15:12 Mamy n punktów w układzie współrzędnych o współrzędnych (x1,y1), (x2,y2), ...,
(xn,yn). Należy znaleźć promień najmniejszego okręgu, w którym będą zawarte wszystkie te punkty. Masz n2 punktów A1,A2,...,An. Rozważasz wszystkie n(n-1)(n-2)/6 trzyelementowe zbiory {Ai,Aj,Ak} i dla każdgo takiego zbioru rozważasz trójkąt (może być zdegenerowany) AiAjAk i liczbę Kijk określoną następująco: a) gdy trójkąt AiAjAk jest rozwartokątny Kijk jest połową najdłuższego boku trójkąta b) gdy trójkąt AiAjAk nie jest rozwartokątny Kijk jest promieniem okręgu opisanego na trójkącie AiAjAk. Szukana liczba jest największą z liczb Kijk. Algorytm ten ma złożoność O(n^3), co nie powala na kolana. |
| Marian Jakszto
|
Posted: 24 Mar 2001 17:53:43 Jest twierdzenie (nie pamiętam szczegółów, kojarzy mi się Young,
ale nie jestem pewien, nie pamiętam też, jak się przenosi na wyższe wymiary, ani jak się go dowodziło, choć było to na pewno na poziomie liceum lub prostsze), które mówi, że każdy zbiór na płaszczyźnie o średnicy d daje się przykryć kołem o promieniu d/sqrt(3). Twierdzenie Junga. Zob. http://br.crashed.net/~akrowne/crc/math/j/j085.htm http://www.gallup.unm.edu/~smarandache/jung.htm Marian Jakszto |
| Marian Jakszto
|
Posted: 24 Mar 2001 18:22:29 I jeszcze coś. nie pamiętam też, jak się przenosi na wyższe
wymiary W dwóch wymiarach współczynnik przy d wynosi 1/sqrt(3) - promień koła opisanego na trójkącie równobocznym o boku 1; w trzech wymiarach współczynnik przy d wynosi sqrt(6)/4 - promień kuli opisanej na czworościanie foremnym o krawędzi 1, zob. http://www.gallup.unm.edu/~smarandache/jung.htm . Można przypuścić, że ogólnie współczynnik przy d jest równy promieniowi kuli opisanej na sympleksie foremnym o krawędzi 1 (jest coś takiego?). Ile by to mogło wynosić? Marian Jakszto |
| . 1 . 2 . >> |