二分查找法、猴子选大王、洗牌算法小解

忘是亡心i 2022-05-30 04:36 144阅读 0赞

1、二分查找法

二分查找法实现了快速在一个已经排好序的数组中找出指定的元素的方法，思想是首先找到数组中间的元素，和指定的元素进行比较（一分为二），如果大于指定元素，说明这个指定的元素在选出中间元素的前面，否则在后面。依次循环，直到找到指定元素（递归思想）。

代码为

function second_find($arr,$value,$start=0,$end=null){
       $end = count($arr) -1;
       $mid = floor(($start+$end)/2);
       if($value<$arr[$mid]){
          return second_find($arr,$value,$start,$mid-1)
       }else if($value<$arr[$mid]){
          return second_find($arr,$value,$start,$mid-1)
       }else{
          return $mid;
       }
    }

2、猴子选大王

猴子选大王是指有n个猴子围在一起，开始数1,2,3,4,5...m，数到m把这个猴子t出去，再重新开始数，直到剩下最后一个猴子，就是大王。代码思路是数到第m只（或者为m的倍数）时，删除这个元素，没有数到（重新数）时，可以理解为将这个元素插入到数组最后（同时删除这个元素）

代码为

function king($arr,$m){
       $i=1;//从1开始
       while(count($arr)>1){
           if($i%m == 0){
              unset($arr[$i-1]);
           }else{
              array_push($arr,$arr[$i-1]);
              unset($arr[$i-1]);
           }
           $i++;
       }
       return $arr;
    }

3、洗牌算法

要求公平洗牌（随机），并将洗好的牌存入新的数组中。算法的关键是每个位置上的牌要是随机的，并且要保证相同的牌只能出现一次，因此在一张牌出现过以后，要删除掉这张牌，并重新再剩余的牌中随机。

代码为

function wash_cards($num){
       $tmp = $cards = array();
       for($i=0;$i<$num;$i++){
          $tmp[] = $i;//牌的位置
       }
       for($i=0;$i<num;$i++){
          $rand = rand(0,$count($tmp));
          $cards[$i] = $tmp($rand);//这个位置上的牌是随机的
          unset($tmp($rand));//删除这张牌，保证一张牌只出现一次
          $tmp = array_values($tmp);//重置数组的数字索引（从0开始）
       }
       return $cards;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关洗牌算法

一、什么是洗牌算法 Fisher–Yates shuffle 洗牌算法简单来说Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（

淡淡的烟草味﹌/ 2023年12月13日 06:18/ 0 赞/ 108 阅读

相关 7-28 猴子选大王 (20 分)

猴子选大王 (20 分) 一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即

悠悠/ 2023年10月11日 16:08/ 0 赞/ 60 阅读

相关【算法】洗牌算法

目录 1.概述 2.代码实现 2.1.暴力法 2.2.Fisher-Yates 洗牌算法 3.应用 > 本文参考： >

怼烎@/ 2023年10月07日 22:56/ 0 赞/ 46 阅读

相关猴子选大王(顺序表)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

逃离我推掉我的手/ 2023年01月13日 04:15/ 0 赞/ 123 阅读

相关基础算法题——猴子选大王（约瑟夫环）

[猴子选大王][Link 1] 一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的

心已赠人/ 2022年12月20日 11:08/ 0 赞/ 198 阅读

相关猴子选大王(循环单链表)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

Love The Way You Lie/ 2022年11月10日 14:17/ 0 赞/ 176 阅读

相关洗牌算法

shuffle算法，我把他叫做洗牌算法，它的目标正好与各种的sort算法相反，即把一个有序(或者无序)的一系列元素打乱，以满足需求。举个两例子，大家都知道扑克牌，我

小咪咪/ 2022年08月11日 15:28/ 0 赞/ 320 阅读

相关二分查找法、猴子选大王、洗牌算法小解

1、二分查找法二分查找法实现了快速在一个已经排好序的数组中找出指定的元素的方法，思想是首先找到数组中间的元素，和指定的元素进行比较（一分为二），如果大于指定元素，

忘是亡心i/ 2022年05月30日 04:36/ 0 赞/ 145 阅读

相关洗牌算法

算法描述：类似于我们平时玩扑克牌的洗牌过程，将一副未拆封的扑克牌（大小为n的有序数组），通过洗牌打乱排序（变成无重复的随机排列数组）。主要有全局洗牌以及局部洗牌两种思路。

约定不等于承诺〃/ 2022年05月24日 01:27/ 0 赞/ 306 阅读

相关猴子选大王问题

猴子选大王（亚瑟夫换）的问题是数据结构和算法中常见的一类问题。可以使用循环队列实现，也可以使用链表实现。还可以使用数组的回溯法实现。 M只猴子要选大王，选举办法如下：所有猴子

不念不忘少年蓝@/ 2022年05月23日 10:54/ 0 赞/ 282 阅读