W dniu 2013-05-20 15:56, Michal Kleczek pisze:
> On 2013-05-20 15:50, bartekltg wrote:
>> W dniu 2013-05-20 15:20, Michal Kleczek pisze:
>>> On 2013-05-20 14:54, bartekltg wrote:
>>>> W dniu 2013-05-20 14:03, Michal Kleczek pisze:
>>>>> On 2013-05-20 13:47, Michal Kleczek wrote:
>>>>>> On 2013-05-20 13:15, bartekltg wrote:
>>>>>>> W dniu 2013-05-20 08:36, Wojciech "Spook" Sura pisze:
>>>>>>>> W dniu 19.05.2013 o 17:51 Edek <e...@g...com> pisze:
>>>>>>>> (...)
>>>>>>>>
>>>>>>>> Ja się kiedyś zastanawiałem nad innym problemem: jaką strategię
>>>>>>>> obrać
>>>>>>>> jedząc pizzę, której rozmiar pokrywa się z rozmiarem talerza, aby
>>>>>>>> możliwie jak najszybciej mieściła się na talerzu (nie miała żadnych
>>>>>>>> punktów wspólnych z brzegiem talerza).
>>>>>>>
>>>>>>> Obgryźć rant (dowolnie wąski pasek:) na długości ponad połowy
>>>>>>> obwodu?
>>>>>>>
>>>>>>
>>>>>> Racja - to mniej niz krzyzyk.
>>>>>>
>>>>>
>>>>> A jednak sie da lepiej :-)
>>>>> Trzy bardzo cienkie wycinki kołowe plus malusienki dysk (o promieniu <
>>>>> pi - 3) w srodku?
>>>>
>>>> Mógłbyś narysować?
>>>>
>>>> Twój krzyżyk można zmodyfikować:
>>>> Wystarczy dowolnie cienki pasek ze średnicy i zsunąć obie połówki.
>>>
>>> Wystarczy.
>>>
>>> Ale lepiej dwa wycinki kolowe ze srednicy i kolko w srodku?
>>
>> Nadal tego nie widzę.
>>
>> Tzn obraz, który mi się kreuje daje rozwiązanie gorsze
>> (dłuższe) niż wycięcie średnicy.
>>
>>> (Lepiej w sensie - wyciac jak najmniejsza powierzchnie pizzy)
>>
>> Powierzchnia? Ale wycinamy przecież szerokość dx, tyle,
>> co na nożu zostanie;)
>> Każdym sposobem możemy wyciąć dowolnie mało.
>>
>
> Dla ustalonego dx porownujemy sposoby :-)
>
> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci min
> polowy obwodu jest najlepszym rozwiazaniem?

Nie. Cięcie po średnicy. Raz wystarczy.


pzdr
bartekltg

do góry

Dnia Mon, 20 May 2013 14:36:08 +0100 po głębokim namyśle Andrzej Jarzabek
rzekł:

> On 20/05/2013 13:03, Michal Kleczek wrote:
> [...]
>>>> Obgryźć rant (dowolnie wąski pasek:) na długości ponad połowy obwodu?
>>>>
>>>>
>>> Racja - to mniej niz krzyzyk.
>>>
>>>
>> A jednak sie da lepiej :-)
>> Trzy bardzo cienkie wycinki kołowe plus malusienki dysk (o promieniu <
>> pi - 3) w srodku?
>
> Ale jakie jest kryterium "lepszości"? Było tylko powiedziane "możliwiej
> jak najszybciej" ale w zadaniu nie ma nic o tym jak obgryzanie/wycinanie
> przebiega w czasie.

1. Wycinana powierzchnia 2. Stosunek obwodu wycinanych fragmentów do
powierzchni. W zasadzie 1 odpada, istnieje tylko w celu uniknięcia
zjedzenia zbyt dużej ilości pizzy zanim się zmieści na talerzu. Ale
2. jest ważne ze względu na ściekający sos.

--
Edek

do góry

Dnia Mon, 20 May 2013 01:55:16 +0200 po głębokim namyśle bartekltg rzekł:

> Jeśli szukasz algorytmu dającego ścisły deterministyczny wynik,
> jest źle. Prostszy problem, czyli zamiast dowolnej figury mamy okręgi:
> http://en.wikipedia.org/wiki/Circle_packing_in_a_cir
cle
> http://hydra.nat.uni-magdeburg.de/packing/cci/#Resul
ts

Dobre. Nie wszystkie kolumny rozumiem, ale gęstość rośnie, czego można się
było spodziewać.

> Zwróć uwagę, że tylko do 13 kółka 'minimalna patelnia'
> jest pewna. Kolejne to to, co wypluł algorytm (w drugim linku jest
> bardzo bogata bibliografia,
> pewnie coś dla siebie zajdziesz boczku), nawet bez pewności,
> że nie da się lepiej.

O przepraszam bardzo. Podobno jestem dresem a nie boczkiem ;) No
ale dzięki, nie wiedziałem, że koła w kole są warte takiej ilości
zachodu i mają bibliografię - najważniejsze jest wiedzieć gdzie
szukać, podobno.

> Oryginalny problem i jakieś algorytmy i herystyki powinno się dać
> wygooglać, problem dość życiowy,
> ale mi nic rozsądnego wyszukiwarka nie wypluła,
> pewnie złe zaklęcia wpisałem.

Zakręcony ogon?

Chyba najlepiej zacząć od bąbelków w wodzie, kulek w naczyniu
czy struktury kryształów. Oidp kulki i tym podobne szukają stanu
o najniższej energii - jeżeli znajdą minimum lokalne może
nastąpić gwałtowna konwersja do niżej położonego układu, co
zawsze wiąże się z różnymi nieregularnościami w strukturze.
Najlepsze jest to, że kulki w naczyniu tak mają, stabilizuje
się układ z paroma nieregularnościami, jeżeli cała reszta może
przez to zmieścić się "niżej". Potem wystarczy poszukać nie
kulek a cząsteczek i ma się taki boczek...

Tyle o kulkach, pamiętam że to się bardzo ciężko liczy, ale
też pytanie jest w jakiej objętości się zmieszczą i czy na pewno.

--
Edek

do góry

Dnia Sun, 19 May 2013 21:56:43 +0200 po głębokim namyśle R.e.m.e.K rzekł:

> ja mysle ze to jest do zrobienia trzeba mz zrobic symulacje toru pixela
> po krzywej pogoni pocisku ziemia-ziemia. moze to napisze rano, bo teraz
> sie zle czuje
>
> ale ktos musi mi pomoc zoptymalizowac to w asmie bo jeszcze sie w nim
> nie czuje tak pewnie jak w C

A nie lepiej we flashu? Z dodatkiem aśma najlepiej.

> zaczalbym od obliczenia pola patelni ale niech ktos poda jakis wzor bo
> nie pamietam, chyba to bylo z jakims pi, tak? zreszta to niewazne bo
> pole bedzie mw podobne do kwadratu a rogi mozna ujac w bledzie
> zaokraglania

Całkiem blisko sposobu wyprowadzania wzoru na pole

> wrzuce to zreszta do mojego silnika 2d i zobaczymy co wyjdzie z
> symulacji tylko musze przeprogramowac armstki na boczek i jajka
>
> dam znac jak to policze

Masz potencjał, ale od kiedy okrągła patelnia ma rogi? No dobrze, wiem,
wszystko da się kupić.

> MSPANC :DDDDDD

Toże...

--
Edek

do góry

W dniu 20.05.2013 o 15:37 Andrzej Jarzabek <a...@g...com>
pisze:

> On 20/05/2013 14:20, Michal Kleczek wrote:
>>
>> Ale lepiej dwa wycinki kolowe ze srednicy i kolko w srodku?
>>
>> (Lepiej w sensie - wyciac jak najmniejsza powierzchnie pizzy)
>
> Istnieje bardzo wiele sposobów, w których cel można osciągnąć wycinając
> dowolnie małą powierzchnię. Jak je porównasz?

Rzuciłem ten problem w charakterze żartu, ponieważ strasznie trudno jest
go formalnie zdefiniować - co już zostało zauważone. Sam wpadłem na
rozwiązanie z połową obwodu plus jeden punkt i wydaje mi się, że to jest
prawidłowe rozwiązanie, ale nigdy nie przetestowałem go w praktyce, bo
choć technicznie poprawne, to jednak jest mało praktyczne :)

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

Dnia Tue, 21 May 2013 07:22:58 +0200 po głębokim namyśle Wojciech
\"Spook\" Sura rzekł:

> W dniu 20.05.2013 o 15:37 Andrzej Jarzabek <a...@g...com>
> pisze:
>
>> On 20/05/2013 14:20, Michal Kleczek wrote:
>>>
>>> Ale lepiej dwa wycinki kolowe ze srednicy i kolko w srodku?
>>>
>>> (Lepiej w sensie - wyciac jak najmniejsza powierzchnie pizzy)
>>
>> Istnieje bardzo wiele sposobów, w których cel można osciągnąć wycinając
>> dowolnie małą powierzchnię. Jak je porównasz?
>
> Rzuciłem ten problem w charakterze żartu, ponieważ strasznie trudno jest
> go formalnie zdefiniować - co już zostało zauważone. Sam wpadłem na
> rozwiązanie z połową obwodu plus jeden punkt i wydaje mi się, że to jest
> prawidłowe rozwiązanie, ale nigdy nie przetestowałem go w praktyce, bo
> choć technicznie poprawne, to jednak jest mało praktyczne :)

Przynajmniej wiadomo, że jesz kulturalnie pizzę - ja jem łapom ;)

Mnie w tej dyskusji ciekawi co innego: nasz mózgi radzą sobie z tymi
problemami bez problemu, ale jak trzeba zaimplementować algorytm
to nagle sprawa robi się mega-skomplikowana, ekhm, NP-zupełna.

--
Edek

do góry

W dniu 21.05.2013 o 08:35 Edek <e...@g...com> pisze:
>> Rzuciłem ten problem w charakterze żartu, ponieważ strasznie trudno jest
>> go formalnie zdefiniować - co już zostało zauważone. Sam wpadłem na
>> rozwiązanie z połową obwodu plus jeden punkt i wydaje mi się, że to jest
>> prawidłowe rozwiązanie, ale nigdy nie przetestowałem go w praktyce, bo
>> choć technicznie poprawne, to jednak jest mało praktyczne :)
>
> Przynajmniej wiadomo, że jesz kulturalnie pizzę - ja jem łapom ;)
>
> Mnie w tej dyskusji ciekawi co innego: nasz mózgi radzą sobie z tymi
> problemami bez problemu, ale jak trzeba zaimplementować algorytm
> to nagle sprawa robi się mega-skomplikowana, ekhm, NP-zupełna.

Tu nie chodzi o poziom komplikacji algorytmu, tylko o problem z formalną
definicją - nie określiłem, w jaki sposób usuwane są kawałki pizzy. Gdybym
to zrobił, to pewnie nie trzeba byłoby do tego nawet algorytmu, zrobiłby
się z tego prosty problem geometryczny.

Takich problemów znam więcej. Na przykład kiedyś jeden z wykładowców
analizy stwierdził na wykładzie, że operator sumy to taki matematyczny
odpowiednik pętli for. Nie zgodziłem się z nim twierdząc, że pętla for ma
większą moc obliczeniową od operatora sumy, to jest pętlą for można
obliczyć większy zbiór wyrażeń niż sumą.

Napisałem wtedy post na pl.sci.matematyka - swoją drogą fajna dyskusja się
wtedy wywiązała - i doszliśmy do tego, że największym problemem jest
właśnie precyzyjne zdefiniowanie problemu: począwszy od tego, jak pożenić
matematyczny operator sumy z programistyczną instrukcją pętli a
skończywszy na tym, jakiego rodzaju wyrażenia dopuszczamy po prawej
stronie tychże albo czy dopuszczalne są zagnieżdżenia.

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

On 2013-05-20 16:13, bartekltg wrote:
> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>
>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci min
>> polowy obwodu jest najlepszym rozwiazaniem?
>
> Nie. Cięcie po średnicy. Raz wystarczy.

Moge prosic o wyjasnienie? W swojej ciemnocie tego nie widze.

--
Michal

do góry

W dniu 21.05.2013 o 11:06 Michal Kleczek <m...@k...org>
pisze:

> On 2013-05-20 16:13, bartekltg wrote:
>> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>>
>>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>>> min
>>> polowy obwodu jest najlepszym rozwiazaniem?
>>
>> Nie. Cięcie po średnicy. Raz wystarczy.
>
> Moge prosic o wyjasnienie? W swojej ciemnocie tego nie widze.

Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu, więc
tam pizza już nie styka się z talerzem, natomiast obie połówki przesuwasz
w stronę środka talerza o pół grubości cięcia - tym samym odsuwając
pozostałe punkty od krawędzi.

> Michal

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

On 2013-05-21 11:15, Wojciech "Spook" Sura wrote:
> W dniu 21.05.2013 o 11:06 Michal Kleczek <m...@k...org>
> pisze:
>
>> On 2013-05-20 16:13, bartekltg wrote:
>>> W dniu 2013-05-20 15:56, Michal Kleczek pisze:
>>>>
>>>> Ale ok - moze byc dlugosc cięcia. Wtedy ciecie z krawedzi o dlugosci
>>>> min
>>>> polowy obwodu jest najlepszym rozwiazaniem?
>>>
>>> Nie. Cięcie po średnicy. Raz wystarczy.
>>
>> Moge prosic o wyjasnienie? W swojej ciemnocie tego nie widze.
>
> Załóżmy, że tniesz pionowo. Pozbywasz się górnego i dolnego punktu, więc
> tam pizza już nie styka się z talerzem, natomiast obie połówki
> przesuwasz w stronę środka talerza o pół grubości cięcia - tym samym
> odsuwając pozostałe punkty od krawędzi.

No ale to przy zalozeniu ze wycinasz pasek - czyli ciec jest dwa, a nie
jedno.

--
Michal

do góry