Świetnie, mam nadzieję że zagadka się podoba
To już ostatnie pytanie: jak wskazać w początkowym ustawieniu leminga, który zleci jako ostatni?
Lemingi (rozwiązane)
Rozpoczęty przez Matofil, Dec 26 2007 14:04
12 odpowiedzi w tym temacie
#1
Napisano 03.01.2008 - 16:17
"It is so hard to believe, that all this is the way that it has to be."
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
Napisano 25.09.2011 - 17:55
#2
Napisano 03.01.2008 - 21:57
W ustawieniu dowolnym prawda? Nie w jakichś przypadkach uporządkowanych lub "optymalnych" ?
Zacząłem to sobie rozrysowywać, ale nie mogę się dogrzebać do końca na razie. Idę spać, jutro postaram się nad tym pomyśleć
Zacząłem to sobie rozrysowywać, ale nie mogę się dogrzebać do końca na razie. Idę spać, jutro postaram się nad tym pomyśleć
Używam opcji "Zobacz posty od ostatniej wizyty", gdzie widzę dział oraz TEMAT. Temat postaci "help zadanie" zignoruję, ale koło tematu "Izomorfizm/dowód" nie przejdę obojętnie.
Wyłącznie od Ciebie zależy, czy zainteresuje mnie Twoje zadanie
Wyłącznie od Ciebie zależy, czy zainteresuje mnie Twoje zadanie
#3
Napisano 06.01.2008 - 16:00
Trochę można sobie uprościć rozumowanie odnośnie "odbijania się lemmingów"
a mianowicie - "odbicie" lemmingów można zastąpić przez ich "przenikanie" jako że lemmingi nie są numerowane
a mianowicie - "odbicie" lemmingów można zastąpić przez ich "przenikanie" jako że lemmingi nie są numerowane
#4
Napisano 07.01.2008 - 14:17
Tak, chodzi o pewne "przenikanie". Ja znalazłem jeszcze takie obrazowe wytłumaczenie:
Wyobraźmy sobie, że każdy leming idący w prawo trzyma czerwoną chorągiewkę, a leming idący w lewo zieloną chorągiewkę. W momencie zderzenia wymieniają się chorągiewkami i idą dalej w przeciwną stronę.
Zapomnijmy o lemingach, popatrzmy z daleka na ruch chorągiewek. Po zderzeniu i wymianie zielona dalej "idzie" w lewo, czerwona dalej "idzie" w prawo. Czyli same chorągiewki idą jednostajnym ruchem w tę samą stronę! Zderzenie zaś wygląda jak minięcie się chorągiewki zielonej z czerwoną.
1) Dopóki są lemingi na kładce, doputy są i chorągiewki. Widzimy, że najdłużej będzie noszona chorągiewka, która na początku jest na brzegu kładki i będzie przeniesiona na drugi brzeg. Zatem ostatni leming spadnie wraz z ostatnią chorągiewką, która "przeszła" całą kładkę.
2) Zderzeniu odpowiada minięcie się chorągiewek. Łatwo widzimy, że w układzie zaproponowanym przez gralcia każda zielona chorągiewka minie wszystkie 50 czerwonych chorągiewek, zatem minięć będzie . Łatwo też ustalić, że to układ optymalny.
Wyobraźmy sobie, że każdy leming idący w prawo trzyma czerwoną chorągiewkę, a leming idący w lewo zieloną chorągiewkę. W momencie zderzenia wymieniają się chorągiewkami i idą dalej w przeciwną stronę.
Zapomnijmy o lemingach, popatrzmy z daleka na ruch chorągiewek. Po zderzeniu i wymianie zielona dalej "idzie" w lewo, czerwona dalej "idzie" w prawo. Czyli same chorągiewki idą jednostajnym ruchem w tę samą stronę! Zderzenie zaś wygląda jak minięcie się chorągiewki zielonej z czerwoną.
1) Dopóki są lemingi na kładce, doputy są i chorągiewki. Widzimy, że najdłużej będzie noszona chorągiewka, która na początku jest na brzegu kładki i będzie przeniesiona na drugi brzeg. Zatem ostatni leming spadnie wraz z ostatnią chorągiewką, która "przeszła" całą kładkę.
2) Zderzeniu odpowiada minięcie się chorągiewek. Łatwo widzimy, że w układzie zaproponowanym przez gralcia każda zielona chorągiewka minie wszystkie 50 czerwonych chorągiewek, zatem minięć będzie . Łatwo też ustalić, że to układ optymalny.
"It is so hard to believe, that all this is the way that it has to be."
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
#5
Napisano 07.01.2008 - 20:41
To taka moja teoria Nie wiem, czy jest to dobre rozwiązanie.
Jeżeli wszystkie lemingi idą tak, że nie będzie żadnych zderzeń, nie ma czego sprawdzać. Od razu widać, jaki będzie wynik. W przeciwnym wypadku stosujemy procedurę:
Mój algorytm jest taki:
Krok 1. Usuwamy (skreślamy) wszystkie lemingi idące "na zewnątrz" znajdujące się bliżej krańców niż skrajne lemingi idące do wewnątrz. (te usunięte spadną same, nie biorą udziału w odbijaniu).
Krok 2. Począwszy od zewnątrz z obu stron zaznaczamy kolejne pary lemingów idących "do środka". W zielone owale zbieramy przyjaciół tych lemingów, którzy idą "nie tam gdzie chcemy". Owale te są nieistotne i można zastąpić je pojedynczymi skierowanymi do środka lemingami, pomijając dwa owale, które znajdą się na samym środku.
Krok 3. Skrajne lemingi pozwalają nam odnaleźć punkt ostatniego zderzenia (minięcia). Widzimy, w którą stronę będzie szedł "ostatni" leming (zielona strzałka w stronę bardziej odległego końca kładki). Teraz interesują nas już tylko zakreślone lemingi. Mamy tam takie sytuacje, że z jednej strony idzie jeden leming (w naszym przypadku z prawej), w drugą stronę idzie reszta (w naszym przykładzie są to dwa lemingi idące z lewej). Wybieramy dwa ostatnie lemingi (fioletowy owal) z tej strony, z której jest ich więcej (czyli w naszym przypadku z tych z lewej). To będą lemingi uczestniczące w ostatnim zderzeniu. A że wiemy już, w którym miejscu się zderzą, wybieramy z tej pary tego leminga, który będzie po zderzeniu po stronie bardziej odległej od krawędzi (w naszym wypadku po prawej, oznaczony fioletową strzałką).
Ponieważ przykład wyszedł mi troszkę tendencyjny, bo akurat wyszedł układ 2:1 na środku, na osi x narysowałem, jak wyglądałby wybór przy innym układzie (5:1) na środku.
A więc tak, moje rozwiązanie opiera się na kilku wydumanych faktach.
Po pierwsze, leming, który ostatni spadnie, na pewno weźmie udział w ostatnim zderzeniu.
Po drugie, wiadomo, z której strony spadnie ostatni leming. Widać to interpretując zderzenia lemingów jako mijanie.
Po trzecie, da się lemingi podzielić na grupy, które można zastąpić pojedynczym lemingiem.
Po czwarte, lemingi pomiędzy dwoma skrajnymi lemingami idącymi "do środka" można dowolnie przesuwać tak długo, jak nie zmienia się ich kolejności i niczego to nie zmienia.
PS. Jakie tam przenikanie. Ja mówię, że się mijają i już!
PSS. Jeśli to rozwiązanie faktycznie działa, to pójdę poświętować
[ Dodano: 09 Sty 2008, 20:37:27 ]
Dodam jeszcze, że dzisiaj wpadłem na drugi, łatwiejszy sposób, gdzie coś się po prostu zlicza i odlicza, ale to już pozostawiam innym
Ale podany przeze mnie sposób też działa, jakby ktoś miał wątpliwości
Jeżeli wszystkie lemingi idą tak, że nie będzie żadnych zderzeń, nie ma czego sprawdzać. Od razu widać, jaki będzie wynik. W przeciwnym wypadku stosujemy procedurę:
Mój algorytm jest taki:
Krok 1. Usuwamy (skreślamy) wszystkie lemingi idące "na zewnątrz" znajdujące się bliżej krańców niż skrajne lemingi idące do wewnątrz. (te usunięte spadną same, nie biorą udziału w odbijaniu).
Krok 2. Począwszy od zewnątrz z obu stron zaznaczamy kolejne pary lemingów idących "do środka". W zielone owale zbieramy przyjaciół tych lemingów, którzy idą "nie tam gdzie chcemy". Owale te są nieistotne i można zastąpić je pojedynczymi skierowanymi do środka lemingami, pomijając dwa owale, które znajdą się na samym środku.
Krok 3. Skrajne lemingi pozwalają nam odnaleźć punkt ostatniego zderzenia (minięcia). Widzimy, w którą stronę będzie szedł "ostatni" leming (zielona strzałka w stronę bardziej odległego końca kładki). Teraz interesują nas już tylko zakreślone lemingi. Mamy tam takie sytuacje, że z jednej strony idzie jeden leming (w naszym przypadku z prawej), w drugą stronę idzie reszta (w naszym przykładzie są to dwa lemingi idące z lewej). Wybieramy dwa ostatnie lemingi (fioletowy owal) z tej strony, z której jest ich więcej (czyli w naszym przypadku z tych z lewej). To będą lemingi uczestniczące w ostatnim zderzeniu. A że wiemy już, w którym miejscu się zderzą, wybieramy z tej pary tego leminga, który będzie po zderzeniu po stronie bardziej odległej od krawędzi (w naszym wypadku po prawej, oznaczony fioletową strzałką).
Ponieważ przykład wyszedł mi troszkę tendencyjny, bo akurat wyszedł układ 2:1 na środku, na osi x narysowałem, jak wyglądałby wybór przy innym układzie (5:1) na środku.
A więc tak, moje rozwiązanie opiera się na kilku wydumanych faktach.
Po pierwsze, leming, który ostatni spadnie, na pewno weźmie udział w ostatnim zderzeniu.
Po drugie, wiadomo, z której strony spadnie ostatni leming. Widać to interpretując zderzenia lemingów jako mijanie.
Po trzecie, da się lemingi podzielić na grupy, które można zastąpić pojedynczym lemingiem.
Po czwarte, lemingi pomiędzy dwoma skrajnymi lemingami idącymi "do środka" można dowolnie przesuwać tak długo, jak nie zmienia się ich kolejności i niczego to nie zmienia.
PS. Jakie tam przenikanie. Ja mówię, że się mijają i już!
PSS. Jeśli to rozwiązanie faktycznie działa, to pójdę poświętować
[ Dodano: 09 Sty 2008, 20:37:27 ]
Dodam jeszcze, że dzisiaj wpadłem na drugi, łatwiejszy sposób, gdzie coś się po prostu zlicza i odlicza, ale to już pozostawiam innym
Ale podany przeze mnie sposób też działa, jakby ktoś miał wątpliwości
Używam opcji "Zobacz posty od ostatniej wizyty", gdzie widzę dział oraz TEMAT. Temat postaci "help zadanie" zignoruję, ale koło tematu "Izomorfizm/dowód" nie przejdę obojętnie.
Wyłącznie od Ciebie zależy, czy zainteresuje mnie Twoje zadanie
Wyłącznie od Ciebie zależy, czy zainteresuje mnie Twoje zadanie
#6
Napisano 12.01.2008 - 19:39
Lemingi uważam za rozpracowane
"It is so hard to believe, that all this is the way that it has to be."
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!