Autor Wątek: Kwiz  (Przeczytany 551986 razy)

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #795 dnia: Września 04, 2013, 12:46:44 pm »
Daj to rozwiązanie (chyba, że ktoś jeszcze walczy - to niech napisze, żeby nie dawać) bom niecierpliwy.
W takim razie dam nie za parę dni, tylko jutro po południu, żeby dać szansę tym, co chcą powalczyć. Chyba wystarczy cierpliwości na przeczekanie jednego dnia?  ;)

maziek

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 13369
  • zamiast bajek ojciec mi Lema opowiadał...
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #796 dnia: Września 04, 2013, 02:30:21 pm »
No nie wiem, rozsadza mnie...
Człowiek całe życie próbuje nie wychodzić na większego idiotę niż nim faktycznie jest - i przeważnie to mu się nie udaje (moje, z życia).

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #797 dnia: Września 04, 2013, 04:00:55 pm »
Może jeszcze jedna podpowiedź: można założyć, że krasnoludki są dobre w matematyce i mają niezawodną pamięć. Dzięki temu każdy potrafi przechowywać w pamięci potrzebne liczby i wykonywać na nich operacje.

olkapolka

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 6891
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #798 dnia: Września 04, 2013, 04:09:47 pm »
Może jeszcze jedna podpowiedź: można założyć, że krasnoludki są dobre w matematyce i mają niezawodną pamięć. Dzięki temu każdy potrafi przechowywać w pamięci potrzebne liczby i wykonywać na nich operacje.
Dyć to dosyć oczywiste, że muszą pamiętać co widziały i trzymać się ustaleń, ale niewiele zmienia. Kombinowałam z tym podziałem na grupy, kombinowałam z jednym wytypowanym, któremu pozostali dają dźwigniowe znaki, z przekładaniem dźwigni przy drugim wejściu i przy tym liczenie zmian położenia dźwigni (wiedzą ilu ich jest), ale to nie daje rozwiązania, bo czarownik może wysyłać ich po kilka razy i całe rachowanie na nic:)
Ja też jestem za podaniem rozwiązania, bo maziek się rozpuknie, a ja widzę wszędzie krasnoludki - tyż źle;)

Mężczyźni godzą się z faktami. Kobiety z niektórymi faktami nie chcą się pogodzić. Mówią dalej „nie”, nawet jeśli już nic oprócz „tak” powiedzieć nie można.
S.Lem, "Rozprawa"
Bywa odwrotnie;)

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #799 dnia: Września 04, 2013, 04:19:03 pm »
A tak się składa, że wśród tego, co podałaś, jest dobry trop  ;)
Naprawdę mam jeszcze dzisiaj podać rozwiązanie? Już się poddajecie? :)

Stanisław Remuszko

  • 1948-2020
  • In Memoriam
  • God Member
  • *
  • Wiadomości: 8769
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #800 dnia: Września 04, 2013, 05:05:38 pm »
Podtrzymuję: błąd zadania lub nieistnienie solucji.
VOSBM
Ludzi rozumnych i dobrych pozdrawiam serdecznie i z respektem : - )

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #801 dnia: Września 04, 2013, 05:08:07 pm »
Dobra, to daję (na wszelki wypadek rozpisałem sobie odpowiedź już wcześniej :) ).
Rozwiązanie wersji "a" (tej drugiej nadal nie zrobiłem):

Oznaczmy początkowe położenie dźwigni jako 0.
Następnie spośród n krasnoludków wybierzmy jednego Krasnoludka-Strażnika (KS). Pozostałe n-1 będziemy nazywali Zwykłymi Krasnoludkami (ZK).

Algorytm postępowania ZK:
Zadaniem każdego ZK jest dokładnie raz w życiu przesunąć dźwignię z położenia 0 na 1, przy czym powinien zrobić to najwcześniej jak to możliwe.
Czyli:
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 1, to nic nie robi
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 0, a jeszcze nigdy jej nie przestawił, to przesuwa ją do położenia 1
- jeśli ZK wchodzi do komnaty i widzi dźwignię ustawioną na 0, ale pamięta, że już kiedyś ją przesuwał, to nic nie robi

Algorytm postępowania KS:
Zadaniem KS jest podać we właściwym momencie odpowiedź czarownikowi.
KS przechowuje w swojej pamięci zmienną całkowitą x, której początkowa wartość wynosi 0 (zawsze i wszędzie pamiętajmy o zerowaniu zmiennych! http://roflcopter.pl/2861 ;) ).
Kiedy KS wchodzi do komnaty:
- jeśli dźwignia jest ustawiona na 0, to nic nie robi
- jeśli dźwignia jest ustawiona na 1 to resetuje ją, przesuwając do położenia 0 i jednocześnie inkrementuje (czyli zwiększa wartość o 1) zmienną x w swojej pamięci
- jeśli zachodzi x=n-1, to wiadomo, że wszystkie krasnoludki były już w komnacie z dźwignią, zatem KS może powiadomić o tym czarownika

I jak? Pasuje takie rozwiązanie czy gdzieś jest jakaś nieścisłość/błąd? Czy może coś rozjaśnić w wytłumaczeniu?
Teraz czekam na krytykę :)

olkapolka

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 6891
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #802 dnia: Września 04, 2013, 05:20:59 pm »
Odrzuciłam rozwiązanie z wybranym krasnoludkiem, bo doszłam do wniosku, że skoro czarownik wybiera ich losowo, to nie musi tego mojego - znakowanego (niech będzie KS) wybrać więcej niż jeden raz. Może go wybrać ponownie za 100 lat. Ale czas nie ma znaczenia;)
Mężczyźni godzą się z faktami. Kobiety z niektórymi faktami nie chcą się pogodzić. Mówią dalej „nie”, nawet jeśli już nic oprócz „tak” powiedzieć nie można.
S.Lem, "Rozprawa"
Bywa odwrotnie;)

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #803 dnia: Września 04, 2013, 05:26:00 pm »
Odrzuciłam rozwiązanie z wybranym krasnoludkiem, bo doszłam do wniosku, że skoro czarownik wybiera ich losowo, to nie musi tego mojego - znakowanego (niech będzie KS) wybrać więcej niż jeden raz. Może go wybrać ponownie za 100 lat. Ale czas nie ma znaczenia;)

Tak, czas nie ma znaczenia. A wiadomo, że po pewnym skończonym czasie każdy krasnoludek zostanie wybrany co najmniej p razy, gdzie p jest dowolną (byle skończoną) wybraną przez nas wartością. Tak więc w pesymistycznym przypadku krasnoludki będą uwięzione n "okresów", ale jest to zawsze czas skończony i to jest najważniejsze.

olkapolka

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 6891
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #804 dnia: Września 04, 2013, 05:54:18 pm »
Jeśli pominąć sprawę żywotności krasnali to wygląda oki.
Tak kombinowałam z tymi grupami - porządkując je wg położenia dźwigni:) Ale mogłeś mi napisać, że podział na grupy nie jest do końca zły;)
To jednak abstrakcyjne zadanie, bo z jednej strony mówisz o czasie, a z drugiej...czy rzeczywiście czarownik musi wybrać n razy KS? Mam wątpliwość. Czy może przez wieczność wybierać pozostałych? Prawo wielgich liczb...hm. Tylko to mi nie pasuje:)
Co do wersji b) - Twoim tropem i pomijając zupełnie kwestię czasu -  KS wykona chyba...zbiorową KS, bo może - bez szczęścia - pomylić się o jednego koleżkę. Nie ma 100% pewności.
Tak czy siak - ciekawa zagadka:)
Mężczyźni godzą się z faktami. Kobiety z niektórymi faktami nie chcą się pogodzić. Mówią dalej „nie”, nawet jeśli już nic oprócz „tak” powiedzieć nie można.
S.Lem, "Rozprawa"
Bywa odwrotnie;)

Stanisław Remuszko

  • 1948-2020
  • In Memoriam
  • God Member
  • *
  • Wiadomości: 8769
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #805 dnia: Września 04, 2013, 06:01:25 pm »
1. Wstępnie jestem na ten algorytm za głupi (ale też teraz brak mi czasu by się porzadniej zastanowić).
2. Jednak nieco inaczej bym sformułował zadanie. Zaproponuję (ale znów nie teraz).
3. Na razie bardzo ciekawe :-)
VOSBM
Ludzi rozumnych i dobrych pozdrawiam serdecznie i z respektem : - )

maziek

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 13369
  • zamiast bajek ojciec mi Lema opowiadał...
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #806 dnia: Września 04, 2013, 06:22:01 pm »
Zwracam honor :) . Czyli jednak mam za ciasny rozumek :) .
Człowiek całe życie próbuje nie wychodzić na większego idiotę niż nim faktycznie jest - i przeważnie to mu się nie udaje (moje, z życia).

HAL 9000

  • Full Member
  • ****
  • Wiadomości: 158
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #807 dnia: Września 04, 2013, 06:38:14 pm »
Jeśli pominąć sprawę żywotności krasnali to wygląda oki.
Tak kombinowałam z tymi grupami - porządkując je wg położenia dźwigni:) Ale mogłeś mi napisać, że podział na grupy nie jest do końca zły;)
To jednak abstrakcyjne zadanie, bo z jednej strony mówisz o czasie, a z drugiej...czy rzeczywiście czarownik musi wybrać n razy KS? Mam wątpliwość. Czy może przez wieczność wybierać pozostałych? Prawo wielgich liczb...hm. Tylko to mi nie pasuje:)
Co do wersji b) - Twoim tropem i pomijając zupełnie kwestię czasu -  KS wykona chyba...zbiorową KS, bo może - bez szczęścia - pomylić się o jednego koleżkę. Nie ma 100% pewności.
Tak czy siak - ciekawa zagadka:)

A naciskaliście, żeby nie czekać dalej i podać rozwiązanie  ;)
Tak, stosując ten algorytm, KS musi być wybrany co najmniej n-1 razy.
Nie może się jednak zdarzyć tak, że czarownik będzie przez wieczność wybierał innych, a KS nigdy. O to właśnie mi chodziło z tymi "okresami": w każdym "okresie" każdy krasnal musi zostać wybrany co najmniej raz, przy czym może to trwać baaardzo długo.
W żadnym wypadku jednak nie twierdzę, że to jedyne rozwiązanie. Być może istnieją inne, lepsze algorytmy. Jeśli tak, to chętnie bym się z nimi zapoznał :)
Co do "b"-później nad tym pomyślę.
Przyznaję, że żadnym erudytą nie jestem, więc sformułowanie zadania jest, jakie jest, zwłaszcza, że była to zagadka opowiedziana mi na wakacjach przez kolegę, więc chyba tym bardziej ciężko to przenieść na formę pisaną.
Mam jednak pytanie: czy ci, którzy prześledzili rozwiązanie, zgadzają się z poprawnością algorytmu? Czy są jakieś zastrzeżenia co do tego? Ta kwestia najbardziej mnie interesuje.

maziek

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 13369
  • zamiast bajek ojciec mi Lema opowiadał...
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #808 dnia: Września 04, 2013, 06:57:04 pm »
Ja się całkowicie zgadzam :) . Wszystko co genialne - jest proste :) .
Człowiek całe życie próbuje nie wychodzić na większego idiotę niż nim faktycznie jest - i przeważnie to mu się nie udaje (moje, z życia).

olkapolka

  • YaBB Administrator
  • God Member
  • *****
  • Wiadomości: 6891
    • Zobacz profil
Odp: Kwiz
« Odpowiedź #809 dnia: Września 04, 2013, 06:57:25 pm »
Twój algorytm rozumiem tak - przekładając na polski;) - KS ma przypisane 0 z dźwigni i tylko on może tej pozycji używać. ZK używaja pozycji 1. Każdy tylko raz - chociażby ZK był w tej komnacie 500 razy. Stąd KS oblicza ile razy cofnął dźwignię do pozycji 0 i jak przesunie ją tyle razy, ilu jest krasnali (bez niego - oczywiście), to może oznajmić czarownikowi, że wszyscy byli chociaż raz.
Wg mnie to jest oki - pomijając całkowicie czas potrzebny na realizację tej umowy i przyjmując, że SK rzeczywiście musi zostać potrzebną liczbę razy wylosowany (taka ość  moja;) ) - nie chodzi o to, że nigdy nie zostanie wylosowany (jak napisałeś), ale że dokładnie tyle razy ile potrzeba by zliczyć koleżków! To mnie niepokoi;)
Co do b) nie znając położenia dźwigni - to Twoim tropem:
- zaczynając od 0 - wchodzi pierwszy SK i nic nie robi - wie, że nikogo nie było, bo tylko o zawiaduje 0 i wszystko toczy się jak wyżej. Kiedy wchodzi pierwszy ZK, to zmienia położenie i SK ma kłopot taki:
- zaczynając od 1 - SK nie wie czy któryś (tylko jeden) ZK już tu był, czy to początkowe położenie dźwigni - dlatego pisałam, że Twoim tropem może pomylić się tu o 1 koleżkę. Nie ma 100% pewności.
Mężczyźni godzą się z faktami. Kobiety z niektórymi faktami nie chcą się pogodzić. Mówią dalej „nie”, nawet jeśli już nic oprócz „tak” powiedzieć nie można.
S.Lem, "Rozprawa"
Bywa odwrotnie;)