忍者ブログ
このブログはPBW『無限のファンタジア』『シルバーレイン』『エンドブレイカー!』『サイキックハーツ』のキャラクター、およびそのプレイヤー(背後)の対話形式のブログです……でした。 対話形式は気まぐれに、残りはほとんどプレイング置き場になってます。
[467] [466] [465] [464] [463] [462] [461] [460] [459]
ヨセフスの問題というものがあって。
概要としては「n人が円状に並び、交互に自殺をしていく(1番、3番、…が生き残り、2番、4番、…が死ぬ)。最後に生き残る1人は誰(何番)か?」っていう問題なのですが。

まぁ解説はyoutubeを見てもらえば一発なので省略しますが。
数学やってると一般化するのが悪い癖なんですかね。



ヨセフスの問題(もしくはジョセファスの問題)って、「n人」が円状に並んで「1人ごと」に死んでく(もしくは円から離れる)わけです。
ではもし、「1番がm人を殺して、次に生き残った(m+2)番がm人を殺して、…」となると、(自殺しない場合は)何番が生き残る?
もし「1番がm人を殺して、生き残りのうちs人((m+2)番から(m+s+1)番)は生殺与奪が行使できず飛ばされて、(m+s+2)番がm人を殺して…」となると、(同じく自殺しない場合は)何番が生き残る?

ヨセフスの問題(特にYouTubeの解説動画)って、「f(n, m, s)」のうち「f(n, 1, 0)」の限られた場合でしか答えが出せないんだなぁって。
とりあえず、f(n, 2, 0) (1人が2人殺す、スキップはなし)については、nが奇数なら番号は把握した
--
f(n, 1, 0):n=2a+b に対して、2b+1 番が生き残る
f(n, 2, 0):n=3a+b に対して、(3b/2)+1 番が生き残る
PR

コメント


コメントフォーム
お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード
  Vodafone絵文字 i-mode絵文字 Ezweb絵文字


忍者ブログ [PR]
カレンダー
02 2019/03 04
S M T W T F S
1 2
4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
お天気情報
プロフィール
HN:
キッド
年齢:
33
性別:
男性
誕生日:
1986/03/22
職業:
(元)冒険者
最新コメント
[06/16 TWmap管理人]
[05/09 おか(静月PL)]
[09/28 水]
[07/05 イノセ]
[07/04 水]
アクセス解析
ブログ内検索
フリーエリア
Dropboxに登録しませんか? Dropboxは複数の端末でファイルを共有・管理できるサービスです。 (PCからスマフォへの画像送信や、ToDo管理や、スマフォで発注文を書いてPCでリクエスト、など用途はたくさん!) 上のURLから登録すると、500MBが無料拡張されます。
最古記事
(08/12)
(08/15)
(09/15)
(11/01)
(11/05)
最新トラックバック
バーコード