szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 gru 2004, o 22:52 
Użytkownik

Posty: 83
Lokalizacja: L-ca
Chyba wiekszosc osob na forum wie jak wyglada problem Józefa flawiusza, ale pokrótce go opiszę:

Dawno temu, podczas wojny rzymsko-żydowskiej Flawiusz wraz z grupą 41 żydowskich powstańców został otoczony przez Rzymian w jaskini! Woląc samobójstwo od poddania powstancy postanowili utworzyć krąg i zabijać co trzecią osobę, aż nikt nie pozostanie przy zyciu! Jednak Flawiusz wraz z przyjacielem nie zgadzali się na to bezsensowne samobójstwo i szybko wyliczył, gdzie powinni stanąć on i jego przyjaciel aby jako ostatni zostali tylko oni!

Ten problem jest rozwiązany, dla n osob i jezeli zabija się co drugą osobę i chcemy aby jedna została, w ksiażce: "Matematyka konkretna" Graham, Knuth i Patashnik.

A czy moze ktos umie rozwiazać, lub zna rozwązanie do pierwotnej treści zadania czyli gdy zabijana jest co trzecia osoba i trzeba obliczyc dwa ostatnie uratowane miejsca?
Konkretnie to trzeba znaleźć wzór pozwalający wyznaczyć J_1(n) i J_2(n) znając wartości J_1(m) oraz J_2(m) dla m
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 27 gru 2004, o 13:36 
Użytkownik
Avatar użytkownika

Posty: 1554
Lokalizacja: Kraków
16 i 31 - to jest wynik jesli cie ciekawi, w ksiazce S. Kowala "Przez rozrywke do wiedzy" jest podany wraz z recznym rozwiazaniem
Góra
Kobieta Offline
PostNapisane: 27 gru 2004, o 16:32 
Gość Specjalny

Posty: 800
Lokalizacja: W-U
a mi recznie wyszlo 17 i 32, pewnie zalezy od poczatku
Góra
Mężczyzna Offline
PostNapisane: 28 gru 2004, o 00:10 
Użytkownik

Posty: 83
Lokalizacja: L-ca
No poprawny wynik to 16 i 31 tyle to ja umiem wyliczyc recznie co nie jest trudne, a na dodatek napisalem program ktory to wylicza i to dla n osob i co m zabijanego! Tylko ze problem polega na tym aby znalezc wzor rekurencyjny na to, czyli jak sie zabija co 3 osobe to ktore dwie zostana w zaleznosci od liczby osob. Dla zabijanej co drugiej osoby to taki wzor wyglada:
J(1)=1
J(2n)=2J(n)-1 dla n >=1
J(2n+1)=2J(n)+1 dla n >=1

Kożystajac z tych wzorow mozna obliczyc dla kazdego n.

Dalej w Matematyce Konkretnej wyprowadzaja na to wzór:
J(2^m + L) = 2L +1

Moze sprobuje to ladniej napisac:

J(2^m+l)=2l+1

No i jeszcze co ciekawe to ostatnie uratowane miejsce to jak zapisze sie liczbe osob w systemie binarnym i przesunie o jeden bit zdaje sie w lewo to bedzie numer tego uratowanego miejsca! jezeli ktos nie wie co to znaczy przesunac o bit to to jest to samo co wziac pierwsza cyfre i dac ja na koniec!

No i ja poszukuje czegos podobnego dla tej wersji gdzie zabija sie co trzecia osobe!
A przynajmniej cos takiego jak te trzy pierwsze wzory!
Góra
Kobieta Offline
PostNapisane: 28 gru 2004, o 00:35 
Gość Specjalny

Posty: 800
Lokalizacja: W-U
Poprawka do mojego poprzedniego: wyszlo mi recznie 19 i 34, ale ja liczylam, ze osob nie jest 41, bo przeciez
Cytuj:
Flawiusz wraz z grupą 41 żydowskich powstańców
;) Dla mnie to znaczy, ze osob bylo 42.

J(m) to jest co? numer (wyjsciowy) osoby, ktora zostanie zabita w m tym ruchu? czy numer osoby, ktora zostanie na koncu, jesli poczatkowo osob bylo m?
Góra
Mężczyzna Offline
PostNapisane: 28 gru 2004, o 18:36 
Użytkownik

Posty: 83
Lokalizacja: L-ca
A no masz racje mozna brac pod uwage ze lacznie bylo ich 42 osoby i wtedy poprawne wyniki to:
J_1(42)=19 i J_2(42)=34


Jest tak:
dla przypadku gdzie zabija sie co druga osobe to:
J(n) jest to ostatnia zywa osoba kiedy zabija sie co druga osobe sposrod n liczby osob!

a dla przypadku gdy zabija sie co trzecia osoba to :
J_1(n) to jest pierwsza z dwoch pozostalych osob kiedy zabijaja co trzecia osobe z grupy n osob

natomiast J_2(n) to jest druga z pozostalych osob
Góra
Mężczyzna Offline
PostNapisane: 14 sty 2005, o 12:46 
Użytkownik
Avatar użytkownika

Posty: 96
Lokalizacja: Warszawa / Stalowa Wola
Ale w "Matematyce Konkretnej" problem ogólny też jest rozwiązany, tylko przy końcu rozdziału...
Góra
Mężczyzna Offline
PostNapisane: 21 maja 2013, o 11:51 
Użytkownik

Posty: 106
Lokalizacja: Warszawa
SoD napisał(a):
(..)
Dalej w Matematyce Konkretnej wyprowadzaja na to wzór:
J(2^m + L) = 2L +1

Moze sprobuje to ladniej napisac:

J(2^m+l)=2l+1
(...)

Witam, bardzo ciekawy wzór rekurencyjny podałeś dla przesunięcia o dwa. nie spodziewałem się że to można w tak łatwy sposób napisać. Jednak nie rozumiem tej części:
J(2^m + L) = 2L +1
J(2^m+l)=2l+1
Czyli dla pomijanie co dwa rozumiem, ale co m już nie potrafię pojąć.
Czy mógłby mi ktoś to wytłumaczyć tak łopatologicznie?
Góra
Mężczyzna Offline
PostNapisane: 4 maja 2019, o 23:52 
Użytkownik

Posty: 7249
Lokalizacja: Z Bielskia-Białej
A jak ( z dowodem ) przejść z wersji pierwotnej do takiej, że najpierw zabijamy nieparzystych. Zabijamy od 1
Góra
Mężczyzna Offline
PostNapisane: 15 maja 2019, o 22:38 
Użytkownik
Avatar użytkownika

Posty: 6669
Lokalizacja: 53°02'N 18°35'E
Kartezjusz, wątpie aby tobie odpowiedzieli skoro od lat już nikt nie kontynuuje tego wątku

SoD, się tutaj chwalił że napisał program

Program jest łatwiejszy do napisania niż sito Eratostenesa dla liczb pierwszych

Program można napisać albo z użyciem tablicy
(do indeksowania przydaje się arytmetyka modularna)
albo z użyciem listy cyklicznej
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z silnią - zadanie 5  Thuddy  7
 Problem z permutacjami  abstractly  1
 Problem z dowodem pewnego wzoru.  kaarol  3
 Algorytm rozwiązujący problem  damianel  3
 Problem z zadankiem z kombinatoryki - zadanie 2  dwukwiat15  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl