Problem Józefa Flawiusza: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian Znaczniki: Wycofane VisualEditor |
|||
Linia 1:
'''Problem Józefa Flawiusza''' (także: '''permutacja Józefa Flawiusza''') – problem teoretyczny z zakresu [[kombinatoryka|kombinatoryki]]. Często rozważany w [[informatyka|informatyce]]. W ogólnej wersji problem brzmi następująco: na okręgu ustawiamy <math>n</math> obiektów, następnie eliminujemy co <math>k</math>-ty obiekt, tak długo, aż zostanie tylko jeden. Należy wskazać obiekt, który pozostanie.
Dla <math>k=2</math>9 istnieje [[wzór jawny]]<ref name="mk">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 23–32 |isbn = 83-01-14764-4 |rozdział = Problem Józefa Flawiusza}}</ref>, a dla pozostałych <math>k</math> istnieją algorytmy rozwiązujące problem między innymi w [[Złożoność obliczeniowa|złożonościach czasowych]] <math>O(n)</math> i <math>O(k \log n)</math>{{r|dynamic}}<ref name="maximal">{{Cytuj stronę |url = http://e-maxx.ru/algo/joseph_problem |tytuł = Задача Иосифа |data = 2008-06-11 |opublikowany = MAXimal |język = ru |data dostępu = 2017-06-09}}</ref><ref name="nlogm">{{Cytuj pismo |nazwisko = Lloyd |imię = Errol |tytuł = An O(n log m) Algorithm for the Josephus Problem |czasopismo = Journal of Algorithms |strony = 262–270 |język = en |data = 1983-09}}</ref>.
== Historia i odmiany problemu ==
| |||