Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық санау есебі
Mathematical counting out question
Компьютерлік ғылым мен математикада Иосиф мәселесі (немесе Иосифтың ауысуы) – белгілі бір санау ойынымен байланысты теориялық мәселе. Мұндай ойындар топтан бір адамды таңдау үшін қолданылады, мысалы, eeny, meeny, miny, moe. [[Файл:JosephusProblemDrawing.png|thumb|right|500 адамнан тұратын және 6 санын жіберіп тастайтын Иосиф мәселесінің тізбегінің суреті. Көлденең ось – адамның нөмірі. Тік ось (жоғарыдан төменге қарай) – уақыт (цикл саны). Тірі адам жасыл, ал өлген адам қара түспен бейнеленген. Бірақ Иосиф Флавийдің сақталған қолжазбасында басқаша айтылады: ол сандарды ақылмен санап, қалғандарды алдап жіберді. Иосифтың серігі болды; мәселе соңғы екі тірі қалғанның орнын табу болды (олардың құтқарылуын қамтамасыз ететін). Ол өзін және екінші адамды тиісінше 31-ші және 16-шы орындарға орналастырды (төмендегі k = 3 үшін).
In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting out game. Such games are used to pick out a person from a group, e. g. eeny, meeny, miny, moe. [[File:JosephusProblemDrawing. png|thumb|right|A drawing for the Josephus problem sequence for 500 people and skipping value of 6. The horizontal axis is the number of the person. The vertical axis (top to bottom) is time (the number of cycle). A live person is drawn as green, a dead one is drawn as black. But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”. Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for k = 3 below).
Шешім
thumb| Жосеф мәселесіндегі соңғы (күлгін) және түпкілікті (көк) орындар, әртүрлі топ мөлшері, n және қадам мөлшері, k үшін. [SVG файлында] өлтірудің толық ретін көрсету үшін мәндерге тыйысу. Төменде, бастапқы шеңбердегі адамдар санын белгілейді, ал әрбір қадам үшін санауды белгілейді, яғни адамдар өткізіліп, -шысы орындалады. Шеңбердегі адамдар -ден дейін нөмірленеді, бастапқы позиция болып табылады және санау кіріктірілген.
thumb|link=|Penultimate (pink) and ultimate (ultramarine) places in the Josephus problem for various group size, n and step size, k. In [ the SVG file,] hover over the values to show the full order of killing. In the following, denotes the number of people in the initial circle, and denotes the count for each step, that is, people are skipped and the th is executed. The people in the circle are numbered from to , the starting position being and the counting being inclusive.
Біттік
Биттік операторларды қолдану арқылы қауіпсіз позицияны табу оңай. Осы тәсілде n санының ең жоғары орналасқан белгілі битін ең төменгі орналасқан битке жылдыру қауіпсіз позицияны береді.
The easiest way to find the safe position is by using bitwise operators. In this approach, shifting the most significant set bit of n to the least significant bit will return the safe position.