技术控

    今日:122| 主题:49289
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] How can a computer deal a poker hand?

[复制链接]
滑稽戏Farcetowards 发表于 2016-10-1 03:12:51
114 5

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

How can a computer deal a poker hand?-1 (describes,important,computer,standard,testing)
   programming
   by
   jon
   Bentley
    with  Special  Guest  Oyster  Bob Floyd     
   pearls
    A  SAMPLE  OF BRILLIANCE   
    How  can  a computer  a  poker  hand?  If  we assign      
    each  card  in  the  deck  its  own  integer  between  1  and 52,           
    then  we  can  make  a hand  a  “random  sample” of      
    5  integers  in  the  range  1..52,  for instance,      
   4a314647
    (It  is  important  that  no  number  appear  twice; holding        
    more  than  one  ace  of  spades  can  jeopardize  a card-         
    player’s  health.)  Random  samples  also  arise  in appli-      
    cations  such  as  simulation,  program  testing, and      
   statistics.
    The  first  section  of  this  column  reviews several      
    standard  algorithms  for  random  sampling.  The next      
    section  describes  an  elegant  new  algorithm  by Floyd.      
    The  third  section  describes  how  Floyd  extends his      
    algorithm  to  generate  random permutations.   
    A  SamplingSampling Algorithms  
    Before  we  can  generate a      sample,  we  have to   
    be  able  to generate    a  single  random  number.  That topic     
    is  worth  a  column  all  its  own,  so  we  will  simply assume           
    that  we  have  a function   
   RandInt
    ( I,
   J
    )  that returns  
    an  integer  uniformly  distributed  over I..J     
    It  is  easy  to  generate  a  random sequence     of   
   M
   inte-
    gers  in  the  range  l..N,  soas  we  don’t  mind dupli-         
   cates
    for  I :=  
   1
   print
    RandInt(1, N)
    When  I set  
   M
    toto3,  that  code  produced the   
   sequence
   313311121131
    This  very  sequence  might  come  in  handy  for  your next         
    tough  game  of  rock-paper-scissors;  more  serious appli-      
    cations  include  testing  finite  state  machines  and sorting      
   programs.
    Many  applications,  though,  require  a  random sample      
    without  duplicates.  A  statistical  analysis,  for instance,      
    might  waste  work  by  observing  the  same element      
    twice.  Such  samples  are  often  referred  to  as “samples        
    without  replacement”  or  as  “combinations”;  for the      
    01987  ACM  OOOl-0782/0900-0754 $1.50   
    remainder  of  this  column,  though,  the  word “sample”      
    will  denote  a  random  sample  with  no duplicates.      
    The  December  1984  column  described  several sam-      
    pling  algorithms.’  The  majority  of  the  algorithms were      
    based  on  the  pseudocode  in  Algorithm  S,  which stores        
    the sample  the  set S.  
   en
    ALGORITHM  S.  A  Typical  Sampling Algorithm     
    If  the  set  S  is  implemented  correctly  and if        
   RandInt
    produces  random  integers,  then  Algorithm  S  produces a      
    random  sample.  That  is,  each  M-element  subset  is pro-        
    duced  with  probability  I/(%).  The  loop  invariant  is that        
    S  always  contains  a  random  sample  of  Size:  integers in         
    the  range l..N.  
    There  are  four  operations  on  S:  initializing  it to        
    empty,  testing  an  integer  for  membership, inserting      
    a  new  integer,  and  printing  all  the  members. The        
    December  1984  column  sketched  five  data structures      
    that  could  be  used  to  implement  the  set  S:  bit vectors,         
    arrays  (sorted  and  unsorted),  binary search    and   
    bins.  In  the May   
   1986
    column,  Don  Knuth presented   
    a  “literate”  sampling  program  that  implements  S as      
    an  ordered  hash  table;  David  Gries  described the      
    same  data  structure  using abstract    data  types  in the   
    April  1987 column.  
    Floyd’s Algorithm
    Algorithm  S  has  many  virtues:  it  is  correct,  fairly effi-         
    cient,  and  remarkably  succinct.  It  is  so  good,  as  a mat-         
    ter  of  fact,  that  I  thought  one  couldn’t  do  better.  In the           
    ’  An  updated  version  of  that  column  appears  as  Column 111986           
    Addison-Wesley book
    Programming Pearls.
    It  contains  several  algorithms  not in     
    the  original column.  
   754
    Communications of
    the ACM
    September 1987309

How can a computer deal a poker hand?-2 (describes,important,computer,standard,testing)
   Programming
   Pearls
    December  1984I  therefore  charged  ahead and     
    described  it  in detail.   
    Unfortunately,  I  was  wrong;  fortunately,  Bob Floyd      
    caught  me  sleeping.  When  he  studied  Gries’s imple-      
    mentation  of  Algorithm  S  in  the  April  1987  column, he         
    was  bothered  by  a  flaw  that  is  displayed  clearly when         
    M  ==  100. When   =  99,  the  set  S contains    but   
    one  the  desired  integers.  The  algorithm  closes its      
    eyes  and  blindly  guesses  integers  until  it  stumbles over        
    the  right  one,  which  requires  100  random numbers   on      
    the  average.  That  analysis assumes     the random
    number  generator  is  truly  random;  for  some non-      
    random  sequences,  the  algorithm  won’t  even terminate.      
    Floyd  set  outto  find  an  algorithm  that  uses exactly        
    one  call of  
   RandInt
    for  each  random  number  in  S. The      
    structure  of  Floyd’s  algorithm  is  easy  to understand    re-     
    cursively:  to  generate  a  5-element  sample  from l..lO,      
    we  first  generate  a  4-element  sample  from  1..9, and        
    then  add  the  fifth  element.  The  recursive  program is        
    sketched  as  Program Fl.   
    We  can  appreciate  the  correctness  of  Floyd’s algo-      
    rithm  anecdotally.  When  M  ==  10,  the algo-      
    rithm  first  recursively  computes  in  S  a 4-element      
    random  sample  from  1..9.  Next  it assigns    to    random
    integer  in the   l..lO.  Of  the  10  values  that  T can         
    assume,  exactly  5  result  in inserting    10  into  S:  the four      
    values  already  in  S,  and  the  value  10  itself.  Thus ele-         
    ment  10  is  inserted  into  the set  the correct      
    probability  of  5/10.  The  next  section  proves that      
    Algorithm  Fl  produces  each  M-element  sample with      
    equal probability.
    function  SampleCM, N)  
    if  M  =  0 then   
    return  the  empty set   
   else
   S
    := SampleCM-I,
   N-l)
    T  :=  RandInt(1, N)   
    if  T  is  not  in  S then      
    insert  T  in S   
   else
    insert  N  in S   
    return S
    ALGORITHM  Fl.  Floyd’s Algorithm-Recursive   
    Because  Algorithm  Fl  uses  a  restricted  form  of recur-        
    sion.  Floyd  was  able  to translate  to  an  iterative form      
    by  introducing  a  new variable,   
   J.
    (Problem  8 addresses  
    recursion  removal  in  more  general  terms.) The    is   
    Algorithm  F2,  which  is  more  efficient  than Algo-      
    rithm  S,  yet  is  almost  as  succinct. Problems        
    address  the  data  structures  that  might  be  used to        
    implement  the  set S.   
    For  those  who  might  scoff  that  Algorithm  F2  is “just         
    pseudocode,”  Program  F2  implements  Floyd’s algorithm     
    in  the  Awk  language.  The  June  1985  column sketched        
    initialize  set  S  to empty   
    for  J  :=  N  -  M +      
   1
    to  N do  
   T
    :=  RandInt(1, J)  
    if  T  is  not  in  S then      
    insert  T  in S   
   else
    insert  J  in S   
    ALGORITHM  F2.  Floyd’s Algorithm-Iterative   
    that  language,  with  particular  emphasis  on  its associa-      
    tive arrays  are  used  to  implement  sets  in Pro-      
    gram  F2).  Complete  with  input  and  output,  the program        
    requires  only  nine  lines  of Awk.     
    BEGIN {
    m  = ARGVLII;  = ARGV121  
    for  Cj  =  n-m+l;  j  i=  n;  j++) {        
    t =
   1
    +  int(j  * randO)   
    if  (t  in  s)  s[jl =     
   1
    else  s[tl =  
   1
    for  (i  inprint i   
    PROGRAM F2.
    Floyd’s  Algorithm  in Awk   
    Random Permutations
    Some  programs  that  use  a  random  sample require      that   
    the elements  the  sample  occur  in a  order.   
    Such  a  sequence is   a  random  permutation with-   
    out  replacement  of  M  integers from      In  testing a  
    sorting  program,  for  instance,  it  is  important  that ran-        
    domly  generated  input  occur  in  random  order  (if the        
    input  were  always  sorted,  for  instance,  it  might not        
    fully  exercise  the  sort code).   
    We  could  use  Floyd’s  Algorithm  F2  to  generate a        
    random  sample,  then  copy  it  to  an  array,  and finally         
    shuffle  the elements  the  array.  This  code randomly     
    scrambles  the  array X[l..M]:   
    for I
    :=  M  downto  2 do   
    Swap(X[RandInt(l,  I)], X[Il)  
    This  three-step  method  uses  2M  calls to      
   RandInt.
    Floyd’s  random  permutation  generator  is  very similar      
    to  Algorithm  F2;  it is    Algorithm  P,  next page.’   
    To  compute  an  M-element  permutation  from  l..N, it      
    first  computes  an  (M  -  I)-element  permutation from      
    l..N  -  1;  a  recursive  version  of  the  algorithm ehmi-         
    nates  the  variable  I.  The  primary  data  structure  of Al-         
    gorithm  P,  though,  is  a  sequence rather   a    set.  
    ‘Flovd  observes  that  Aleorithm  P  can  be  viewed  as  a  nondeterministic aleo-           
    rithm  and  macroexpand~d  into  a  backtracking  procedure  that  generates aTI         
    permutations  ofof  N.For  details,  see  Floyd’s  “Nondeterministic Algo-      
    rithms”  in 1.  
    ACM  14. 4  
    (Oct. 1967).
   636-644.
    September 1987309  
   Communications
   of
    the ACM
   755
12下一页
友荐云推荐




上一篇:Perform Hot Backups of MySQL Databases with Percona XtraBackup on Ubuntu 16.04
下一篇:Purposes, Concepts, Misfits, and a Redesign of Git
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

bydwp 发表于 2016-10-1 14:39:23
过去的一页,能不翻就不要翻,翻落了灰尘会迷了双眼。
回复 支持 反对

使用道具 举报

果蔬 发表于 2016-10-2 00:16:51
无图无真相!
回复 支持 反对

使用道具 举报

香萱 发表于 2016-10-6 10:34:18
有空一起交流一下
回复 支持 反对

使用道具 举报

ttt 发表于 2016-11-15 02:30:53
为保住菊花,这个一定得回复!
回复 支持 反对

使用道具 举报

海海 发表于 2016-11-19 10:28:58
楼下的,觉得比特币咋样啊?
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表