daily pastebin goal
80%
SHARE
TWEET

Untitled

a guest Feb 10th, 2015 285 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. 入力: n人の生徒
  3. 出力: n人の生徒に対するランダムな番号[1..n]
  4. 条件: 複雑な計算を要しないこと。必ず停止すること。n人のうちランダムにm人選びたいときも応用がきくこと。ランダムであること。戦略的に自分が不利になることはあっても、有利にはなりにくいこと。同時に数字を言う、などではなく、じゃんけんのように、同時に手を出すなどして極力曖昧さが少なくなるようにすること。アルゴリズムが人数によらないこと。ディーラーを必要としないこと。
  5.  
  6. じゃんけん[停止しないので不可]
  7. n人で誰かが勝つまでじゃんけんをする
  8.  -> m人が勝ったら、n-m人とm人でそれぞれじゃんけんをする。これを繰り返して一番勝った人から番号を振る
  9.  
  10. ゲーマーじゃんけん[停止しないので不可]
  11. n人で手を出す
  12.  -> 手が少ない人たちが勝つ。手が少ない人のグループが同数の時は正規のじゃんけんの方法でグループを一つに決める。これを繰り返して一番勝った人から番号をふる。
  13.  
  14. par ou impar[停止しないので不可]
  15.  -> 全員0または1を出す。少ない方が勝つ。これを繰り返す。2人になったら出す手の和の偶奇を当てる。
  16.  
  17. オリジナルの方法
  18. 2, 3人のグループに別れる。それらの人々の間では勝負が簡単かつ確実につく。
  19.  
  20. グループが3人の場合
  21. 0, 1, 2
  22. の中で数字を各人予想する。同時に
  23. どれを選んでも当確率である。
  24. それぞれ同時に0,1,2またはmod3のことなる3数のうちいずれかを出す 👊,👆,👋(5≡2mod3)
  25. 予想の当たったものが勝者になる。
  26.  
  27. 和の場合の数を次のようにして考えられる。プレイヤーAの手とBの手を固定すると、Cが出すべき手cは
  28. a+b≡x のとき一意に決まる。つまり、自分が予想した手になるような出し方は3つの手のうち一つしか無い。ところで、xとしては(0+0)(0+1)(0+2)(1+0)(1+1)(1+2)(2+0)(2+1)(2+2)となるが、この内modが何になるかは1/3で当確率。というかaの値を固定して同様に考えれば結局1/3である。
  29.  
  30. グループ人数が2人の場合
  31. 0,1で同じことを行う。
  32.  
  33. グループ内での優劣をつける。この優劣は一度でかならず付く。3人の時は勝者の予想した数字-1mod3の数字を予想した人を次点とすればよい。
  34.  
  35. こうして選出されたグループの代表者同士で同じことを行う。グループの代表者の数が4人以上でも再帰的にただ一人の勝者を決められる。あるグループAの代表aが勝てば、Bの人間は全てのAの人間に負けたとみなす。
  36. 例えば
  37. a,b,c,d,e,f,g,h,i,j,k
  38. についてやってみる。
  39. グループ化
  40. [a,b,c] [d,e,f] [g,h,i] [j,k]
  41. 勝った順に並べる
  42. [a,c,b] [d,f,e] [g,i,h] [k,j]
  43. 再グループ化
  44. [a,d] [g,k]
  45. 勝った順に並べる
  46. [a,d] [k,g]
  47. グループ化
  48. [a,k]
  49. 勝った順に並べる
  50. [k,a]
  51.  
  52. 順序の復元
  53. [k,a]
  54. [[k,g] [a,d]]
  55. [[[k,j],[g,i,h]] [[a,c,b],[d,f,e]]]
  56. ただし確認が難しいかも
  57.  
  58. 一応2n+3m=x(>=2)となるn,m(>=0)の存在を示す
  59. x≡0(mod6) -> 3m
  60. 2人のグループ数: 0
  61. x≡1(mod6) -> x≡7 && x >= 7なので 2*2 + 3m に分ける
  62. 2人のグループ数: 2
  63. x≡2(mod6) -> 2*1
  64. 2人のグループ数: 1
  65. x≡3(mod6) -> 3m
  66. 2人のグループ数: 0
  67. x≡4(mod6) -> 2*2
  68. 2人のグループ数: 2
  69. x≡5(mod6) -> x≡11 && x >= 11なので 2 + 3*3 + 3m に分ける
  70. 2人のグループ数: 1
  71.  
  72. 計算時間はlog(n)
  73. 100人でやっても
  74. 100 -> 34 -> 12 -> 4 -> 2 -> 1
  75. となり6回で決まる!
  76. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top