Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
płaty boczku na patelnię (okrągłą) zastanawiałem się,
jakiego algorytmu użyć, aby uzyskać możliwie największą
ilość boczku nałożonego na patelnię tak, żeby się równo
przypiekł.

Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
poligonem, jak to boczek. Kroimy w poprzek, czyli w
płaszczyźnie przekroju, i układamy na patelni o promieniu
r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
patelni. Przekrój boczku na płaską podstawę (nie wiem jak
to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).

O ile mnie zadanie rano stanowczo przerosło i nawet nie
oczekuję żadnych konkretnych algorytmicznych rozwiązań,
jaka jest złożoność tego problemu? Powiedzmy, że boczek
ma przekrój wypukły.

Szczerze mówiąc rano rozbiłem na niego dwa jajka i
tu byłoby drugie zadanie specjalnie do gier:
policzyć i odtworzyć 2x odgłos plućkającego na powierzchnię
płaską o temperaturze 68 stopni jajka (klasa B, rozmiar
niewielki)..

--
Edek

do góry

Dnia Sun, 19 May 2013 15:51:02 +0000 (UTC), Edek napisał(a):

> Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
> płaty boczku na patelnię (okrągłą) zastanawiałem się,
> jakiego algorytmu użyć, aby uzyskać możliwie największą
> ilość boczku nałożonego na patelnię tak, żeby się równo
> przypiekł.
>
> Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
> poligonem, jak to boczek. Kroimy w poprzek, czyli w
> płaszczyźnie przekroju, i układamy na patelni o promieniu
> r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
> patelni. Przekrój boczku na płaską podstawę (nie wiem jak
> to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
> z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).
>
> O ile mnie zadanie rano stanowczo przerosło i nawet nie
> oczekuję żadnych konkretnych algorytmicznych rozwiązań,
> jaka jest złożoność tego problemu? Powiedzmy, że boczek
> ma przekrój wypukły.
>
> Szczerze mówiąc rano rozbiłem na niego dwa jajka i
> tu byłoby drugie zadanie specjalnie do gier:
> policzyć i odtworzyć 2x odgłos plućkającego na powierzchnię
> płaską o temperaturze 68 stopni jajka (klasa B, rozmiar
> niewielki)..

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

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

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




MSPANC :DDDDDD

--
pozdro
R.e.m.e.K

do góry

On 19/05/2013 20:56, R.e.m.e.K wrote:
> Dnia Sun, 19 May 2013 15:51:02 +0000 (UTC), Edek napisał(a):
>
> 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

Błąd zaokrąglenia jest w drugą stronę. W tę stronę to jest błąd
średniokwadratowy.

do góry

W dniu 2013-05-19 17:51, Edek pisze:
> Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
> płaty boczku na patelnię (okrągłą) zastanawiałem się,
> jakiego algorytmu użyć, aby uzyskać możliwie największą
> ilość boczku nałożonego na patelnię tak, żeby się równo
> przypiekł.
>
> Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
> poligonem, jak to boczek. Kroimy w poprzek, czyli w
> płaszczyźnie przekroju, i układamy na patelni o promieniu
> r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
> patelni. Przekrój boczku na płaską podstawę (nie wiem jak
> to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
> z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).
>
> O ile mnie zadanie rano stanowczo przerosło i nawet nie
> oczekuję żadnych konkretnych algorytmicznych rozwiązań,
> jaka jest złożoność tego problemu? Powiedzmy, że boczek
> ma przekrój wypukły.

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


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.

Czytałem to jakiś czas temu i najprostszy algorytm miał
swoją cześć 'wykładniczą' pod postacią przeszukiwania
możliwych postaci "grafu kontaktów".

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.


BTW. podobny problem występuje z serem lub wędliną
na kanapce. Tam najlepiej sprawdza się krojenie
i przestawianie małych kawałków sera aż do uzyskania
zadowalającej dokładności.
;)

pzdr
bartekltg

do góry

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).

Pozdrawiam -- Spook.

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

do góry

On 2013-05-19 17:51, Edek wrote:
> Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
> płaty boczku na patelnię (okrągłą) zastanawiałem się,
> jakiego algorytmu użyć, aby uzyskać możliwie największą
> ilość boczku nałożonego na patelnię tak, żeby się równo
> przypiekł.
>
> Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
> poligonem, jak to boczek. Kroimy w poprzek, czyli w
> płaszczyźnie przekroju, i układamy na patelni o promieniu
> r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
> patelni. Przekrój boczku na płaską podstawę (nie wiem jak
> to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
> z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).
>
> O ile mnie zadanie rano stanowczo przerosło i nawet nie
> oczekuję żadnych konkretnych algorytmicznych rozwiązań,
> jaka jest złożoność tego problemu? Powiedzmy, że boczek
> ma przekrój wypukły.
>

Problem plecakowy? NP-trudny.

--
Michal

do góry

On 2013-05-20 08:36, Wojciech "Spook" Sura wrote:
> 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).

Wiecej szczegolow? Ograniczenia na rozmiar kawalkow ktore sie mieszcza w
ustach? Mozna przesuwac pociete kawalki?

Jesli mozna przesuwac i nie ma ograniczen na rozmiary kawalkow to chyba
najefektywniej wyciac mozliwie cienki krzyz przez srodek i zsunac kawalki.
Jak nie mozna przesuwac, to nie ma wyjscia - trzeba zjesc suche ciasto z
brzegu :-)

--
Michal

do góry

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?

pzdr
bartekltg

do góry

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.

--
Michal

do góry

On 2013-05-20 12:36, Michal Kleczek wrote:
> On 2013-05-20 08:36, Wojciech "Spook" Sura wrote:
>> 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).
>
> Wiecej szczegolow? Ograniczenia na rozmiar kawalkow ktore sie mieszcza w
> ustach? Mozna przesuwac pociete kawalki?
>
> Jesli mozna przesuwac i nie ma ograniczen na rozmiary kawalkow to chyba
> najefektywniej wyciac mozliwie cienki krzyz przez srodek i zsunac kawalki.

Oczywiscie nie :)

> Jak nie mozna przesuwac, to nie ma wyjscia - trzeba zjesc suche ciasto z
> brzegu :-)
>

Jak pisal barteklg - z ponad polowy obwodu.

--
Michal

do góry