Ostatnio pracowałem nad następującym problemem:

Mamy zadany obszar, będący nieskończenie długą taśmą o zadanej szerokości.
Ponadto znamy promienie pewnej skończonej liczby okręgów.
Zadanie polega na wyszukaniu takiego ułożenia okręgów, aby
wysokość ograniczająca najwyższy okrąg była jak najniżej.

Naturalnie, okręgi nie mogą na siebie nawzajem zachodzić, ani też wystawać poza obszar.

Wygląda to więc odrobinę jak wsypywanie różnej wielkości kul do wiaderka, tak aby wysokość usypanego stosu była jak najmniejsza. (tylko w dwóch wymiarach).

Jestem niezwykle ciekaw jaką ogólną metodę rozwiązania byście zaproponowali,
jakie spostrzeżenia i jakie ograniczenia poczynicie?

Ponadto jeżeli ktoś jest szczególnie zainteresowany przykładową implementacją, rozpisałem to w javie i mogę przesłać kod.

zrozumialem ze mam rysowak kolka po jakims obszarze ale w nieskonczonej szerokosci i o skonczonej wysokosci (aby kolka mialy wymiar :)

czyli:
wysokosc := 100;
promien := 100div2-1;
srodek_okregu := 100div2-1;

lewa_do_sordka_okregu: promien*i

petla do nieskonoczonsci i:=0 to xxx
i2:=0 to 360
rysujemy okrag w pteli z sinusami i cosinusami

jak cos nie spieprzylem to wszystko dziala dobrze

gdyby cosik moge to napsiac w delphi i tu umiescic :)

[cisza]
lolek

ZIOMBER napisał:
zrozumialem ze mam rysowak kolka po jakims obszarze ale w nieskonczonej szerokosci i o skonczonej wysokosci (aby kolka mialy wymiar :)

Jak na moj gust to zle zrozumiales ;))). Nie chodzi o to jak rysowac kolka, mozna ich wcale nie rysowac, chodzi o to w jakiej kolejnosci je ulozyc zeby wypelniajac obszar od dolu wypelnialy go do jak najmniejszej wysokosci.--Pawel {Delphi 6 Personal}

Po pierwsze: naciśnij F1

Niestety całkowicie niezrozumiałeś.

Jest to taśma o zadanej szerokości, ma swój początek, ale nie ma końca. Umownie ustawmy ją pionowo:

| |
| |
| |
| |
| |
| |
|_____|

znamy jej szerokość. (Wpisuje ją użytkownik). Następnie użytkownik wprowadza listę okręgów wpisując kolejno ich promienie.

Rozwiązaniem jest podanie takiego ułożenia okręgów (podając ich współrzędne w układzie współrzędnych), ażeby wysokość najwyższego z nich była możliwie najniżej.

Przykładowe dane:
szerokość = 4
promienie = 2, 1, 0.5

Odpowiedź
okrąg o promieniu 2 umieść w punkcie 2, 2
okrąg o promieniu 1 umieść w punkcie 3, 4.83
okrąg o promieniu .5 umieść w punkcie 0.5, 4
wysokość ograniczająca podane ułożenie = 5.83

Jednocześnie powtarzam, że nie chodzi mi o przykład implementacji (mój kod ma 500 linii, więc nie oczekuję pisania kodu), chodzi natomiast o ogólne uproszczenia i założenia dotyczące układaniu kół, które pozwolą w ogóle rozwiązać ten problem.

Proszę uwolnić się na chwilę od programowania i spojrzeć na zadanie z innej perspektywy, perspektywy metody, która w skończonej liczbie elementarnych kroków doprowadzi nas do rozwiązania.

Pozdrawiam i czekam na jakiekolwiek pomysły.

Kapustka napisał:
Wygląda to więc odrobinę jak wsypywanie różnej wielkości kul do wiaderka, tak aby wysokość usypanego stosu była jak najmniejsza. (tylko w dwóch wymiarach).

Sprawdzenie wszystkiech możliwości nie wchodzi w grę? W takim razie tylko dynamicznie - ale jak?? Trudno!!

Ponadto jeżeli ktoś jest szczególnie zainteresowany przykładową implementacją, rozpisałem to w javie i mogę przesłać kod.

[email protected] :) będę wdzięczny [mam nadzieje, że z opisem :-) ]--Vogel [Delphi 6 PE]

Life is just a dream, you know...
[Cowboy Bebop]

ZIOMBER napisał:
zrozumialem ze mam rysowak kolka po jakims obszarze ale w nieskonczonej szerokosci i o skonczonej wysokosci (aby kolka mialy wymiar :)
...
jak cos nie spieprzylem to wszystko dziala dobrze

Obawiam się, że tu chodziło o coś innego.

Zadanie typu: masz studnię i ileś piłek. Jak umieścić w niej piłki, by zajęły jak najmniej miejsca.
Teraz tylko trzeba wziąć to na płaszczyźnie (coś jak przekrój studni).

A teraz moje spostrzeżenia:
Na początku wrzucałbym największe piłki. Jeżeli istniałaby możliwość wetknąć piłki w wolne miejsca poniżej tych dużych (trzeba sprawdzać odległości). Jeżeli nie można wetknąć to wrzucamy na górę.
Jedyny problem to pozostaje wyliczać odległości, czy jest wolne miejsce.--Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.

pq - to jest już jakiś punkt zaczepienia,

1. jaką kolejność byś zaproponował.
2. czy raz wstawione koło może zostać potem, w trakcie dostawiania, zmodyfikowane.
3. w jakich miejscach próbowałbyś dostawić nowe koła

Jedno spostrzeżenie wydaje się prawdziwe - koła należy wpisywać od dołu (innej, sensownej możliwości po prostu nie ma).

Vogel napisał:
Sprawdzenie wszystkiech możliwości nie wchodzi w grę? W takim razie tylko dynamicznie - ale jak?? Trudno

Jest jeden problem - tych możliwości jest nieskończenie wiele, trzeba narzucić pewne uproszczenia aby ich ilość była liczbą skończoną.

Dryobates wspomniał o zaczynaniu od jak największych piłek, pytanie brzmi: Czy wynajdując koła w kolejności malejących promieni może się zdarzyć, że odrzucimy dobre rozwiązanie?

Inaczej to formułując: Czy istnieją takie zadane promienie i szerokość, że przyjmując porządek "najpierw największe" nie trafimy na najlepsze rozwiązanie.

Kapustka zapytaŁ: "Czy istnieją takie zadane promienie i szerokosć ,że przyjmując porządek "najpierw
największe" nie trafimy na najlepsze rozwiazanie."

Owszem istnieją. Wyobraźmy sobie ,ze mamy studnię o promieniu wewnętrznym R (czyli szerokość naszej
wstęgi jest 2R) , dwie duże kule też o promieniu R (czyli mieszczące sie na styk w studni) oraz jedna małą
kulkę o promieniu r. Wyobraźmy sobie dwie sytauacje:

1. Wrzucamy dwie duże kule a następnie małą
2. Wrzucamy kulę dużą ,później małą a na końcu znów dużą.
   Jeśli promień kuli małej (r) jest mniejszy lub równy 0,1715 R (a dokładnie r&lt (V2 -1)/(V2 1)) to obie
   sytuacje dadzą wynik równoważny.
   Natomiast jeśli 0.1715R&ltr&lt0.25R to sytuacja 2 da wynik korzystniejszy. Fizycznie wyglada to tak że dla r
   mniejszego od 0.1715R mała kulka mieści się niejako przy ścianie studni i jej góra nie wystaje ponad
   czubek dużej kuli zajmującej całe światło studni. Jesli promień ten bedzie większy to czubek małej kuli
   będzie wystawał ponad wierzchołek dużej i sumaryczny stos - duza kula duża kula kawałeczek małej
   kuli będzie wyższy niż dwie leżące na sobie duże kule. Natomiast jeśli wrzucimy kulę dużą , póżniej małą i
   znów dużą to mała kula wejdzie w puste miejsce przy obrzeżu , pomiędzy dwiema dużymi i stos nie
   wzrośnie - cały czas będzie równy 4R. Graniczna wartoscią promienia małej kuli jest 0.25R - wtedy to
   wszystkie trzy kule będą się stykać - powiększanie małej kuli spowoduje już unoszenie kuli górnej.
   Przepraszam ,że tak skomplikowanie opisuję rzeczy proste ale niemożność umieszczania rysunków bardzo
   utrudnia wyjaśnianie.
   Przy okazji - przez V2 oznaczam pierwiastek z dwóch.
   --Pzdr.
   W.

gavi napisał:
Owszem istnieją. Wyobraźmy sobie ,ze mamy studnię o promieniu wewnętrznym R (czyli szerokość naszej wstęgi jest 2R) , dwie duże kule też o promieniu R (czyli mieszczące sie na styk w studni) oraz jedna małą
kulkę o promieniu r. Wyobraźmy sobie dwie sytauacje:

1. Wrzucamy dwie duże kule a następnie małą
2. Wrzucamy kulę dużą ,później małą a na końcu znów dużą.

Chyba trochę źle mnie zrozumiałeś.
Po pierwsze to na płaszczyźnie (ale to nie istotne).
Po drugie: małą kulę (koło) wciskamy na sam dół pomiędzy te dwie kule.
Jeżeli mamy studnię o promieniu 2R i w niej dwie duże kule o promieniu R obok siebie, na samym dnie, to bez problemu możemy wetknąć tam każdą kulkę o promieniu &lt=R/4 i wysokość będzie wynosić 2R (czyli wysokość dużych kul).
Jeżeli natomiast kula mała ma większy promień, to umieszczamy ją na górze (w "dołku" pomiędzy dużymi kulami). Wówczas wysokośc wyniesie:
H1 = R + r + Sqrt(r*(2*R + r)) ;

Jeżeli natomias umieścimy kule tak, że najpierw duża, potem mała na dno i na koniec duża na górę to wysokość wyniesie:
H2 = R + r + Sqrt(R*(R + 2*r)) ;

Ponieważ R&gtr i r&gtR/4 ( inaczej możnaby wepchnąć na dno) to H1 &lt H2.
Czyli przy układaniu w ten sposób nie zawsze mniejszy rozmiar będzie jeżeli najpierw wrzucimy duże.

Teraz twój przypadek, kiedy mamy miejsce tylko dla jednej dużej na dnie:
Promień studni R, duże kule tak jak poprzedni o promieniu R.
Jeżeli wrzucimy dwie duże kule, to jedna będzie stać na drugiej. Wysokość wyniesie 2R.
Jeżeli dorzucimy małą kulę o r &lt= (3 - Sqrt(2))R (to ten sam wynik co z twoim V2 tylko uproszczone) to będziemy mogli ją wetknąć pomiędzy kulę na samym dole, a dnem.
Dalej. Jeżeli kula ma rozmiar większy od tej wartości, ale mniejszy od R/4 to możemy umieścić kulę pomiędzy dwiema dużymi przy ściance.
Jeżeli r&gtR/4 to umieszczamy małą kulę na górze, przy ściance. Wysokość stosu wyniesie:
H1 = r + 3R + 2Sqrt(Rr) ;

Teraz jeżeli najpierw wrzucilibyśmy kulę małą, a na nią dwie duże to rozmiar stosu wzrośnie o taką samą wartość H1 (to jest jedynie odwrócenie sytuacji. Duża kula będzie "wisieć" w powietrzu. Oprze się jedynie o małą).
Jeżeli natomiast wrzucimy kulę dużą, potem małą przy ściance, a następnie dużą to wysokość wyniesie:
H2 = 2R + 4Sqrt(R*r) ;

Tu już ewidentnie widać, że H2 &gt H1.

Czyli jest to jak na razie najbardziej optymalny sposób umieszczania. Oczywiście najlepiej umieszczać kule od największej do najmniejszej, a kule wtykać w pierwszej kolejności w najmniejsze dziury, tak, by zostało jak najwięcej wolnej przestrzeni do wstawienia następnych.

To jest tak jak z owocami i cukrem. Wrzucasz owoce, sypiesz cukier i potrząsasz, by na dno spadł cukier i najmniejsze owoce, które się przecisną. Oczywiście tu mamy większą możliwość. Możemy wybrać kolejność wrzucania owoców i wpychać je nawet w szczeliny "od boku", tak, że nie muszą przeciskać się pomiędzy innymi :-) --Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.

Sorry nie dogadaliśmy się, mój post był odpowiedzią nie na Twoje stwierdzenie a na pytanie Kapustki ,
zadane w kolejnym liście " Czy istnieją takie zadane promienie i szerokość ,ze przyjmując porządek
'najpierw największe' nie trafimy na najlepsze rozwiązanie"
Pomyślałem ,że taka definicja jednoznacznie określa,że istotna jest kolejność ustawiania elementów, stąd
nie można najpierw umieścić dwóch dużych a potem w dziury utknać mniejszą mimo pustego miejsca.
Ale rzeczywiście można to rozumieć inaczej,że kolejność nie jest istotna ,a jedynym kryterium jest
wielkość dostępnego miejsca. Zmyliło mnie czyjeś wcześniejsze porównanie do studni (cały czas mówimy o
przekroju - modelu płaskim).
Pytanie więc należałoby postawić inaczej:
Czy istnieje taka kombinacja zadanych promieni, że wstawienie paru mniejszych okręgów jest
korzystniejsze niż jednego większego, mieszczącego się w dostępnej "dziurze"?
--Pzdr.
W.

Sorry nie dogadaliśmy się, mój post był odpowiedzią nie na Twoje stwierdzenie a na pytanie Kapustki , zadane w kolejnym liście " Czy istnieją takie zadane promienie i szerokość ,ze przyjmując porządek 'najpierw największe' nie trafimy na najlepsze rozwiązanie"
Pomyślałem ,że taka definicja jednoznacznie określa,że istotna jest kolejność ustawiania elementów, stąd nie można najpierw umieścić dwóch dużych a potem w dziury utknać mniejszą mimo pustego miejsca.
Ale rzeczywiście można to rozumieć inaczej,że kolejność nie jest istotna ,a jedynym kryterium jest wielkość dostępnego miejsca. Zmyliło mnie czyjeś wcześniejsze porównanie do studni (cały czas mówimy o przekroju - modelu płaskim).
Pytanie więc należałoby postawić inaczej:
Czy istnieje taka kombinacja zadanych promieni, że wstawienie paru mniejszych okręgów jest korzystniejsze niż jednego większego, mieszczącego się w dostępnej "dziurze"?

Prawidłowe sformułowanie problemu jest kluczem do rozwiązania go ;-)

Ja po prostu zrozumiałem to tak, jakbyśmy mieli wstążkę i na niej przypinali okręgi. Porównanie do studni ma unaocznić problem (nie chodzi o rysowanie tak jak to pojął Ziomber).

Kapusta: Pytanie do Ciebie.

1. Jak szybki jest twój program?
2. Czy uwzględnia możliwość wstawiania okręgów w "dziury"? (tzn. czy istotna jest kolejność)--Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.

Muszę przyznać, że stopień zaciekawienia tym tematem przeszedł moje oczekiwania.

W tym stosunkowo długim poście:

1. Odpowiadam na kierowane do mnie pytania.
2. Zamykam dyskusję związaną z pytaniem "Czy obranie drogi najpierw największy może być przyczyną, dla której nie podamy prawidłowej odpowiedzi?".
3. Podsumowuję wszystko co zostało do tej pory powiedziane i rozpisuję to w postaci formalnego algorytmu.
4. Napominam o zagadnieniach złożoności obliczeniowej.
5. Wskazuję na odmienne podejście do tego problemu.

Zanim przejdę do meritum muszę przyznać, że przesyłanie rozpisanego przeze mnie kodu do tego problemu (o który często prosicie w mailach)drogą doczepiania go jako załącznika do indywidualnych listów jest kłopotliwe. Czy istnieje możliwość umieszczenia tego kodu w sieci, skąd każdy mógłby go pobierać do woli?

Wpierw przytoczę ponownie treść problemu:

Mamy zadany obszar, będący nieskończenie długą taśmą o zadanej szerokości.
Ponadto znamy promienie pewnej skończonej liczby okręgów.
Zadanie polega na wyszukaniu takiego ułożenia okręgów, aby
wysokość ograniczająca najwyższy okrąg była jak najniżej.

Odnoszę wrażenie że wiele osób nie potrafi tego poprawnie odczytać i prawdopodbnie jest to moja wina. Dlatego z góry przepraszam i zwracam uwagę na to że:

-problem dotyczy płaszczyzny a nie przestrzeni, mamy więc doczynienia z kołami (a nie kulami), a sugerowane (całkiem słusznie) porównanie do przekroju studni nie oznacza że mamy trzy wymiary.
-taśma jest nieskończona, ale ma swój początek, który umówiliśmy się umieszczać na dole.

Dryobates: Jeżeli chodzi o szybkość mojego kodu, to może być ona różna, w zależności od stopnia dokładności jaka nas interesuje, w najszybszym wariancie jest ona wielomianowa, w najwolniejszym podwójnie wykładnicza (czyli dla 10 okręgów trwa to wieczność).
Odpowiadając na drugie twoje pytanie powiem, że owszem sprawdza możliwość wprowadzania okręgów w dziury (co jest bezpośrednim powodem tak wielkiej złożoności obliczeniowej). Przesyłam Tobie ten kod ze szczególnymi podziękowaniami za zaangażowanie.
Ponadto sprawdziłem Twoje wyprowadzenia matematyczne, które reprezentują szczególnie eleganckie podejście do tematu, niestety nie są one poprawne (upewniałem się przez 1,5 godziny, żeby mieć pewność),
np.wzór H1 (pierwszy który podajesz)
zamiast H1 = R + r + Sqrt(r*(2R + r)) powinno być:
H1=R+r+Sqrt((R+r)(R+r)-4(R-Sqrt(Rr)(R-Sqrt(R*r))). co zaskakujące (i nie potrafię doprawdy powiedzieć dlaczego) twoje wzory dają zaledwie odrobinę zawyżony wynik (np dla R=8,r=3). Twój wzór daje 21.58 a powinno być 20.08, lecz nawet gdyby były one poprawne nie mają one wymaganej siły dowodowej, co w dosyć prosty sposób wykażę w następnej części listu.

"Czy obranie drogi najpierw największy może być przyczyną, dla której nie podamy prawidłowej odpowiedzi?".
Otóż niestety może być. Wiadomo, aby obalić jakiekolwiek twierdzenie wystarczy podać chociaż jedną sytuację w której jest ono fałszywe, oto ona:
Mamy obszar o długości 2R, jedno koło o wielkości R (zajmuje ono całą szerokość) oraz cztery koła o promieniach r=0.3R (nie zmieszczą się one w skrawku pomiędzy dużym kołem a narożnikiem obszaru, swoją drogą największy jaki się zmieści ma promień R*(3-2Sqrt(2))=około 0.17R). Jakie jest optymalne ułożenie? Dwa małe o promieniach r w narożnikach, następnie jeden duży R spoczywa na nich i na nim kładziemy styczne do ścian dwa pozostałe o promieniach r. A jakie rozwiązanie znajdziemy idąc od największego? Największy na dole, a potem cztery mniejsze nad nim. Na rysunku od razu widać że
tracimy w ten sposób rozwiązanie.
Zresztą możemy je stracić także i w takiej sytuacji: Szerokość 6R, Jeden okrąg o promieniu 2R, dwa o promieniach 1.5R. Ta sytuacja jest nieco odmienna. Oczywiście można dojść do rozwiązania zaczynając od największego, ale trzeba go umieścić w środku szerokości, a nie w narożniku. Naprawdę nie sposób pokryć tego algorytmicznie.

Okazuje się więc że zaczynając od największych, możemy w pewnych sytuacjach utracić dobre ułożenie.

Dlatego kolejne otwarte pytanie brzmi: Czy istnieje jakiś sposób aby obejść ten problem? Przyznam się, że sam na tym etapie jeszcze tego nie wiem.

Zapomnijmy na chwilę o tym że czasami możemy utracić dobre rozwiązanie z racji tego, że zaczynamy od największych okręgów. Nadeszła chwila aby zaproponować pierwszy algorytm.

Dane wejściowe: Liczba rzeczywista dodatnia D (szerokość), skończony ciąg n liczb rzeczywistych dodatnich r[n] (promienie).
0. Start.

1. Posortuj r[n] malejąco.
2. Powtarzaj co następuje n razy:
   2.1 Pobierz kolejny promień R
   2.2 Wypisz wszystkie położenia w które mógłbyś wstawić koło o promieniu R, biorać pod uwagę wstawienie go: (w narożnik obszaru) lub (tak aby był on styczny do wcześniej naniesionych kół i do ścian obszaru jednocześnie) lub (tak aby był on jednocześnie styczny do dowolnych dwóch kół naniesionych wcześniej).
   2.3 Z wypisanych położeń wybierz najniższe, wprowadź tam koło i wróć do punktu 2
3. Stop

Ważne pytanie stawiane przy pisaniu programów to: Powiedzmy że jeżeli dane będą zawierały podanych siedem kół, to program będzie znajdzie ich położenie w czasie t (np.dwie minuty), Więc o więcej czasu będzie trwało wykonanie programu, gdy wprowadzone dane będą o jedną dłuższe (czyli osiem kół)?. Jeżeli wydłuży się dwukrotnie to mówimy że złożoność obliczeniowa danego algorytmu jest wykładnicza.
Zaproponowany wyżej algorytm nie jest wykładniczy, dla każdego kolejnego koła musi sprawdzić pewną ilość możliwości, która jest większa od ilości możliwych ułożeń dla poprzedniego koła o pewną wartość wyrażoną wielomianem (w tym wypadku chyba 6+2n). Niemniej nie zapominajmy, że nasz algorytm czasami gubi poprawną odpowiedź.

Może więc całkowicie zmienić sposób patrzenia na nasz problem? Zamiast "Spróbuj upchnąć koło tu, a potem tam..." umieśćmy pierwsze koło w narożniku. Nasz obszar właśnie podzielił się na dwa podobszary (w jednym szczególnym przypadku na trzy). Teraz obliczmy jakie największe koło zmieściłoby się w tym nowym obszarze i przypiszmy tą liczbę do niego. Teraz bierzemy drugi okrąg i jeżeli jest on mniejszy lub równy tej liczbie, wstawiamy go do tego podobszaru, jeżeli nie, wyrzucamy go na górę (oczywiście w miarę najniżej), nasze nowe koło właśnie dokonało dalszego podziału obszaru, dla każdego z tych podobszarów (jest ich teraz cztery w pewnej szczególnej sytuacji) obliczmy promień dla największego koła które hipotetycznie zmieściło by się w takim obszarze i przypisujemy tą liczbę do niego, i tak dalej.
Jak zwykle czekam na wasze obserwacje, szczególnie dotyczące właśnie zaproponowanej metody.

Gorąco pozdrawiam.

Muszę przyznać, że stopień zaciekawienia tym tematem przeszedł moje oczekiwania.

Bo i problem bardzo ciekawy.

Czy istnieje możliwość umieszczenia tego kodu w sieci, skąd każdy mógłby go pobierać do woli?

Możesz dodać do działu Kody. Na stronie głównej serwisu jest link.

Ponadto sprawdziłem Twoje wyprowadzenia matematyczne, które reprezentują szczególnie eleganckie podejście do tematu, niestety nie są one poprawne (upewniałem się przez 1,5 godziny, żeby mieć pewność)

A ja to liczyłem 10 minut w biegu do szkoły :-) Dlatego pewnie gdzieś się walnąłem.

Mamy obszar o długości 2R, jedno koło o wielkości R (zajmuje ono całą szerokość) oraz cztery koła o promieniach r=0.3R (nie zmieszczą się one w skrawku pomiędzy dużym kołem a narożnikiem obszaru, swoją drogą największy jaki się zmieści ma promień R*(3-2Sqrt(2))=około 0.17R). Jakie jest optymalne ułożenie? Dwa małe o promieniach r w narożnikach, następnie jeden duży R spoczywa na nich i na nim kładziemy styczne do ścian dwa pozostałe o promieniach r. A jakie rozwiązanie znajdziemy idąc od największego? Największy na dole, a potem cztery mniejsze nad nim. Na rysunku od razu widać że tracimy w ten sposób rozwiązanie.

To nasunęło mi inny pomysł. Dlaczegoby nie stworzyć "studni bez dna". Tzn tak, żeby można było umieszczać elementy z jedej i z drugiej strony. Tak jakby dolepiać nowe okręgi z każdej strony (uważając przy tym, by łączna szerokość nie przekroczyła szerokości taśmy. Na koniec jedynie postawić z jednej strony granicę :) W ten sposób unikniemy tego problemu.

Dlatego kolejne otwarte pytanie brzmi: Czy istnieje jakiś sposób aby obejść ten problem? Przyznam się, że sam na tym etapie jeszcze tego nie wiem.

Tylko, czy znowu to co podałem na 100% poprawne?

Może więc całkowicie zmienić sposób patrzenia na nasz problem? Zamiast \"Spróbuj upchnąć koło tu, a potem tam...\" umieśćmy pierwsze koło w narożniku. Nasz obszar właśnie podzielił się na dwa podobszary (w jednym szczególnym przypadku na trzy). Teraz obliczmy jakie największe koło zmieściłoby się w tym nowym obszarze i przypiszmy tą liczbę do niego. Teraz bierzemy drugi okrąg i jeżeli jest on mniejszy lub równy tej liczbie, wstawiamy go do tego podobszaru, jeżeli nie, wyrzucamy go na górę (oczywiście w miarę najniżej), nasze nowe koło właśnie dokonało dalszego podziału obszaru, dla każdego z tych podobszarów (jest ich teraz cztery w pewnej szczególnej sytuacji) obliczmy promień dla największego koła które hipotetycznie zmieściło by się w takim obszarze i przypisujemy tą liczbę do niego, i tak dalej.
Jak zwykle czekam na wasze obserwacje, szczególnie dotyczące właśnie zaproponowanej metody.

Jak już napisałeś: Aby obalić ten sposób, wystarczy przedstawić taką kombinację, żeby wypełniając Twoim sposobem zajmowało więcej, niż jakimś alternatywnym.

Wobec tego:
D = 8R (szerokość taśmy)
Okręgi:
R1 = R2 = 3R
R3 = 1,5R
Umieszczamy twoim sposobem:
Duży okrąg najbadziej z prawej w dolny róg. Otrzymujemy dwa obszary: mały (do którego żadnego z pozostałych okręgów nie wepchniemy) i duży (w którym mieszczą się obydwa)
Bierzemy kolejny duży okrąg i wstawiamy go zgodnie z zaleceniami do dużego obszaru jak najniżej (czyli styczny do pierwszego okręgu i do ściany do której nie jest styczny ten pierwszy czyli lewej). Tak na oko mamy wysokość stosu 11,5R. Dalej pozostają nam 3 obszary:
1 ten, który powstał na samym początku (tu nie wsadzimy najmniejszego okręgu)
2 nowo powstały mniejszy (niżej leżący) obszar, do którego też nie uda nam się wstawić ostatniego okręgu
3 ten nieograniczony. Czyli wrzucamy na górę, styczny do R2 i prawej ścianki (tak by był jak najniżej). Na oko mamy wysokość 13R.

Teraz alternatywny sposób ułożenia. Pierwszy okrąg tak jak był. Drugi duży na tym pierwszym okręgu, styczny do niego i do [b]prawej[/b] ścianki (wysokość wynosi wówczas 12R więcej, niż przy dwóch okręgach wcześniejszą metodą). Trzeci najmniejszy okrąg wstawmy styczny do obydwu dużych okręgów i do lewej ścianki (zmieści się tam). Wysokość stosu nie zmieni się już nam. Zostaje 12R. Mniej nież poprzednią metodą.

Wniosek: szukajmy dalej.

--
Jest jeszcze jeden błąd ... :)

Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.

Świetnie, wrzuciłem wspomniany kod do działu "kody źródłowe::Java", teraz każdy może pobrać ten plik (kola.zip).

Pomysł z taśmą dwukierunkową daje do myślenia.

Pozdrawiam.

Mam głupi pomysł :) Skoro można dać taśmę dwukierunkową, to lepiej dajmy jej na początku szerokość równą sumie średnc okręgów a potem zmniejszajmy powoli, przesuwając nieznacznie okręgi po skosie. Najlepsze IMHO poczatkowe ułożenie jest takie: na środku największy, po bokach coraz mniejsze.

--
Vogel [Delphi 6 PE]

Life is just a dream, you know...
[Cowboy Bebop]

Podejrzewam że nadszedł czas aby zamknąć ten temat i podsumować wszystko co tu zostało powiedziane, jak się za chwilę okaże doprowadzi nas to do kolejnego problemu, którym rozpoczynam następny temat.

Postawiony tu problem na pewno leży w klasie problemów o trudnej rozwiązywanlności.

Powyższa dyskusja nie wykazała nawet czy jest to problem rozwiązywalny, wiemy jedynie, że można przy pewnych uproszczeniach uzyskać dla większości przypadków przyzwoite wyniki (kod do ściągnięcia z serwisu, java::okręgi.zip).

Wprowadzenie zaskakującego pomysłu z dwukierunkową taśmą (moje gratulacje) rozwiązuje część problemów, niestety to nie wystarczy aby sobie poradzić chociażby z takimi (wspomnianymi już wcześniej) danymi wejściowymi: Szerokość 6R, Jeden okrąg o promieniu 2R, dwa o promieniach 1.5R. Jedynym słusznym rozwiązaniem w tym wypadku wydaje się wypełnianie obszaru w innej kolejności (wpierw dwa małe).

Dopiero połączenie dwukierunkowej taśmy i sprawdzenie wszystkich możliwych kolejności wypełniania obszaru zdaje się doprowadzać do poprawnego wyniku. Niestety okupione to będzie wielkim obciążeniem obliczeniowym i prawdopodobnie sprawdzenie wszystkich możliwych ułożeń dla zaledwie 8 okręgów będzie trwało wieki.

Tu dochodzimy do kolejnego problemu: W jaki sposób wypisać wszystkie możliwe warianty ciągu n-elementowego (promieni). Zagadnieniu temu dedykuję nową dyskusję: [algorytmika] Permutacje.

To pokombinujmy jeszcze trochę (jakikolwiek sensowny algorytm rozwiązania tego).
Może trzeba ściągnąć trochę od kryształów?

1. Sortujemy okręgi od największego do najmniejszego
2. Spośród okręgów o takich samych promieniach wybieramy tyle, żeby suma ich średnic była równa szerokości studni. Jeżeli znajdziemy takie to umieszczamy je na dnie. W przeciwnym wypadku przechodzimy do 3.
   2a. Szukamy kolejnych takich samych okręgów w liczbie n-1 (o jeden mniej niż wcześniej ułożonych) i o mniejszych bądź równych promieniach. Jeżeli znajdziemy to umieszczamy je na poprzednich okręgach w "szczelinach", które powstały. Przechodzimy do 2.
   2b. Szukamy n-1 okręgów o rozmiarach jak najbardziej zbliżonych rozmiarami do siebie, ale mniejszych od poprzednich i umieszczamy w "szczelinach".
3. Szukamy okręgów, jak najbardziej zbliżonych rozmiarami do siebie, o sumie średnic równej szerokości studni. Jeżeli znajdziemy to kładziemy je na ostatnie (uporządkowane według rozmiarów) i szukamy następne (ale kładąc w kolejności odwrotnej do ostatniej, żeby wyrównać "schodki")
4. Wbieramy po kolei pozostałe okręgi i staramy się wepchnąć w dziury. Jeżeli nie da się, to wrzucamy na górę.

Oczywiście pewnie jeszcze pewne zmiany trzeba tu dodać, ale zawsze to coś.

--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667

Obawiam się że dla danych wejściowych:
szerokość 2,
promienie: 1, 0.3, 0.3, 0.3, 0.3
twój nowy algorytm nie znajdzie optymalnego ułożenia.

może się powtarzam, ale niezmiennie twierdzę że dopiero połączenie dwukierunkowej taśmy i sprawdzenie wszystkich możliwych kolejności wypełniania obszaru (czyli sprawdzenie wszystkich permutacji wejściowego ciągu promieni okręgów) zdaje się doprowadzać do poprawnego wyniku.