Das Josephus-Problem ist eine alte Denkaufgabe: Eine Anzahl Gefangene (z.B. 41) wird in einem Kreis aufgestellt und dann wird abgez\u00e4hlt: Immer nach einer bestimmten Zahl, z.B. immer beim Dritten, wird der Kopf abgeschlagen. Dies geht so lange im Kreis der noch Verbliebenen herum, bis nur noch einer \u00fcbrig bleibt. Die Frage ist nun, wo muss ich mich hinstellen, damit ich als Letzte \u00fcberlebe?
\nEs gibt unz\u00e4hlige L\u00f6sungen f\u00fcr dieses Problem in diversen Programmiersprachen, hier ist meine L\u00f6sung in Groovy:<\/p>\n
<\/p>\n
\r\nk = 3 \/\/Immer der k. wird gek\u00f6pft\r\nn = 41 \/\/Anzahl Gefangene\r\n\/\/Alle Gefangenen im Kreis, true = lebt, false = tot\r\nkreis = [true] * n \/\/Array mit n boolschen Werten\r\nprintln kreis\r\npos = -1 \r\nanzFalse = 0\r\n\/\/die Schleife l\u00e4uft, solange es noch mehr als 1 \u00dcberlebenden gibt\r\nwhile (anzFalse < n) {\r\n for (int counter = 0; counter < k; counter++) {\r\n pos = pos + 1\r\n \/\/wenn die n\u00e4chsten schon tot sind, werden sie \u00fcbersprungen\r\n while (!kreis [pos.mod(n)]) {\r\n pos = pos + 1\r\n }\r\n \/\/den Gefangenen an dieser Position trifft es\r\n if (counter == k - 1) {\r\n kreis[pos.mod(n)] = false\r\n anzFalse = anzFalse + 1\r\n \/\/das ist der Letzte\r\n if (anzFalse == n) {\r\n println ((pos.mod(n) + 1) + " \u00fcberlebt") \r\n } else {\r\n println ((pos.mod(n) + 1) + " ist tot")\r\n }\r\n }\r\n }\r\n}\r\n<\/pre>\nDer Kreis wird durch einen Array of boolean dargestellt. Wenn die Person an der jeweiligen Position im Array lebt, dann ist der Wert true, ansonsten false. Nun wird in einer Schleife abgez\u00e4hlt. Immer nach k Schritten trifft es einen Gefangenen. Ab der zweiten Runde werden diejenigen \u00fcbersprungen, die bereits tot sind. Die Variable pos l\u00e4uft immer weiter, mit pos.mod(n) wird wieder vorne begonnen, wenn die letzte Position erreicht worden ist.<\/p>\n","protected":false},"excerpt":{"rendered":"
Das Josephus-Problem ist eine alte Denkaufgabe: Eine Anzahl Gefangene (z.B. 41) wird in einem Kreis aufgestellt und dann wird abgez\u00e4hlt: Immer nach einer bestimmten Zahl, z.B. immer beim Dritten, wird der Kopf abgeschlagen. Dies geht so lange im Kreis der noch Verbliebenen herum, bis nur noch einer \u00fcbrig bleibt. Die Frage ist nun, wo muss […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4,3],"tags":[285,223],"_links":{"self":[{"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2074"}],"collection":[{"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2074"}],"version-history":[{"count":6,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2074\/revisions"}],"predecessor-version":[{"id":2080,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2074\/revisions\/2080"}],"wp:attachment":[{"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2074"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2074"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.ecotronics.ch\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2074"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}