Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Lemingi (rozwiązane)


  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
12 odpowiedzi w tym temacie

#1 Matofil

Matofil

    Pierwsza pochodna

  • VIP
  • 98 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 03.01.2008 - 16:17

Świetnie, mam nadzieję że zagadka się podoba :)

To już ostatnie pytanie: jak wskazać w początkowym ustawieniu leminga, który zleci jako ostatni?
  • 0
"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!

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Gralcio

Gralcio

    Kombinator

  • VIP
  • 235 postów
37
Mały Pomocnik II
  • Płeć:Mężczyzna

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ć :)
  • 0
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

#3 Kloss

Kloss

    Pierwsza pochodna

  • Użytkownik
  • 96 postów
1
Neutralny
  • Płeć:Mężczyzna

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
  • 0

#4 Matofil

Matofil

    Pierwsza pochodna

  • VIP
  • 98 postów
0
Neutralny
  • Płeć:Mężczyzna

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 50 \cdot 50 = 2500 . Łatwo też ustalić, że to układ optymalny.
  • 0
"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!

#5 Gralcio

Gralcio

    Kombinator

  • VIP
  • 235 postów
37
Mały Pomocnik II
  • Płeć:Mężczyzna

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

Załączone miniatury

  • Kopia_lemingi_123.gif

  • 0
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

#6 Matofil

Matofil

    Pierwsza pochodna

  • VIP
  • 98 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 12.01.2008 - 19:39

Lemingi uważam za rozpracowane :)
  • 0
"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!