szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 gru 2004, o 21: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
Góra
Mężczyzna Offline
PostNapisane: 27 gru 2004, o 12:36 
Użytkownik
Avatar użytkownika

Posty: 1555
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 15: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: 27 gru 2004, o 23: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: 27 gru 2004, o 23: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 17: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 11: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 10: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
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem z asymptotyka  ram22  4
 problem z 3-ma zadaniami  Cubas  2
 Rekurencja niejednorodna - problem  prezes123  2
 Problem wydawania reszty  Opal  9
 Problem Langforda  mol_ksiazkowy  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl