查看: 657|回复: 0

[PHP学习] PHP算法趣谈--猴子找大王

发表于 2017-10-29 08:33:37
太阳http代理AD
一、算法问题

将一群猴子排成一圈,按照猴子数按照1,2,...,n依次编号。然后从第1只开始数,定义数m个猴子,之后将数到的猴子将它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去...,如此循环的进行下去,直到最后只剩下一只猴子为止,那只猴子就是大王。

二、算法思想及来源 递归函数 子函数调用 时间复杂度是O(n*m)

此算法问题来自于约瑟夫问题(来源维基百科)

三、算法原题

约瑟夫斯问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。 有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过 k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过 k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。 问题是,给定了n和k,一开始要站在什么地方才能避免被处决?

四、算法设计与实现
  1. <?php
  2. //算法问题
  3. //
  4. function xdw($m, $n){
  5. //存猴子名称
  6. $arr = array();
  7. //给猴子定义名称
  8. $a = "a";
  9. for($i=0; $i<$m; $i++){
  10. $arr[] = $a++;
  11. }
  12. //print_r($arr);
  13. //定义猴子排序个数
  14. $j = 0;
  15. while (count($arr) > 1) {
  16. if($j%$n==0){
  17. unset($arr[$j]);
  18. }else{
  19. $arr[] = $arr[$j];
  20. unset($arr[$j]);
  21. }
  22. $j++;
  23. }
  24. return $arr;
  25. }
  26. print_r(xdw(40, 3));
  27. ?>
复制代码


太阳http代理AD
回复

使用道具 举报