游戏常用算法-洗牌算法

游戏常用算法-洗牌算法洗牌算法是一个比较常见的面试题。一副扑克54张牌,有54!种排列方式。最佳的洗牌算法,应该能够等概率地生成这54!种结果中的一种

大家好,又见面了,我是你们的朋友全栈君。

洗牌算法是一个比较常见的面试题。

一副扑克54张牌,有54!种排列方式。最佳的洗牌算法,应该能够等概率地生成这54!种结果中的一种

基于Unity的洗牌算法代码实现

GitHub链接

<span role="heading" aria-level="2">游戏常用算法-洗牌算法

抽牌洗牌

原理

这是完全合乎现实洗牌逻辑的算法。

就是抽出纸牌的最后一张随机插入到牌库中,这般抽54次就完成了对扑克牌的洗牌

复杂度

空间O(1),时间O(n^2)

优缺点

如果牌库是以一个数组描述,这种插入式的洗牌不可避免地要大量移动元素。

Fisher_Yates算法

原理

取两个列表,一个是洗牌前的序列A{1,2….54),一个用来放洗牌后的序列B,B初始为空

while A不为空

随机从A取一张牌加入B末尾

复杂度

空间O(n),时间O(n^2)

代码实现

 1 List<int> list = new List<int>(pukes.pukes);//洗牌前的序列A
 2 List<int> newlist = new List<int>(list.Count);//洗牌后的序列B
 3 for(int i = 0 ; i < pukes.pukes.Length ; ++i)
 4 {
 5   int randomIndex = Random.Range(0, list.Count);
 6   int r = list[randomIndex];//随机取牌
 7    newlist.Add(r);
 8    list.RemoveAt(randomIndex);
 9 }
10 pukes.ResetPuke(newlist.ToArray());//序列B为洗牌后的结果

优缺点

算法原理清晰,但额外开辟了一个List,而且为List删除元素是不可避免地需要移动元素

通过54次生成的随机数取1/54,1/53,…1/1能等概率地生成这54!种结果中的一种

Knuth_Durstenfeld算法

Knuth 和Durstenfeld 在Fisher 等人的基础上对算法进行了改进。 每次从未处理的数据中随机取出一个数字,然后把该数字放在数组的尾部, 即数组尾部存放的是已经处理过的数字 。 这是一个原地打乱顺序的算法,算法时间复杂度也从Fisher算法的 O ( n 2 )提升到了 O ( n )。

 

1 for(int i = pukes.pukes.Length - 1;i>0;--i)
2   {
3       int randomIndex = Random.Range(0, i+1);
4       pukes.Swap(randomIndex, i);
5   }

是最佳的洗牌算法

Inside_Out算法

C++ stl中random_shuffle使用的就是这种算法

原理

在[0, i]之间随机一个下标j,然后用位置j的元素替换掉位置i的数字

通过54次生成的随机数取1/1,1/2,…1/54能等概率地生成这54!种结果中的一种

复杂度

空间O(1),时间O(n)

代码实现

1 public static void Shuffle(Pukes pukes)
2   {
3       int len = pukes.pukes.Length;
4       for (int i = 0; i < len; ++i)
5       {
6           int randomIndex = Random.Range(0, i + 1);
7           pukes.Swap(i, randomIndex);
8       }
9   }

random_shuffle

关于c++ stl 的random_shuffle

它的算法原理和Knuth_Durstenfeld类似

先从所有元素中选一个与位置1的元素交换,然后再从剩下的n-1个元素中选择一个放到位置2,以此类推

参考链接

维基百科-Fisher–Yates shuffle

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155556.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • LiveWriter高亮显示方法专题「建议收藏」

    LiveWriter高亮显示方法专题「建议收藏」2013年9月26日花了一上午的时间,熟悉了LiveWriter的用法,学会了怎么配置语法高亮,总结下来。方法1.用博客园推荐的方法没有成功。pass方法2方法来自一个人的旅行.试过OK博客

  • UML活动图、状态图

    UML活动图、状态图 本文主要介绍状态图和活动图。一.状态图     状态(state)是指在对象的生命期中的某个条件或状况,在此期间对象将满足某些条件、执行某些活动或等待某些事件。所有对象都具有状态,状态是对象执行了一系列活动的结果,当某个事件发生后,对象的状态发生变化。    状态图(statechartdiagram):     用来描述一个特定的对象所有可能的状态,以及由于各种事件的发…

  • 用matlab产生时域离散信号实验报告(有关数字信号处理)

    1.正弦序列离散正弦序列的MATLAB表示与连续信号类似,只不过是用stem函数而不是用plot函数来画出序列的波形。下面就是正弦序列的MATLAB源程序。%正弦序列实现程序k=0:39;fk=sin(pi/6*k);stem(k,fk)2.指数序列离散指数序列的一般形式为,可用MATLAB中的数组幂运算(即点幂运算)c*来实现。下面为用MATLAB编写绘制离散时

  • python3.7安装pip_centos怎么安装

    python3.7安装pip_centos怎么安装CentOS自带Python2.7但现在基本使用Python3所以需要自行下载编译及安装,以下为过程步骤。首先确认目前的Python版本及可执行文件位置,执行命令whichpython返回结果这里可以看到,Python执行文件位置为/usr/bin/python,故我们进入到该目录下cd/usr/bin/python现在开始进行我们Pyth…

  • 使用 SSHFS 挂载远程的 Linux 文件系统及目录

    使用 SSHFS 挂载远程的 Linux 文件系统及目录步骤1:在Linux系统上安装SSHFS默认情况下,sshfs包不存在所有的主流Linux发行版中,你需要在你的Linux系统中启用epel,在Yum命令行的帮助下安装SSHFS及其依赖。#yuminstallsshfs#dnfinstallsshfs【在Fedora22+发行版上】$sudoapt-getins…

    2022年10月28日
  • ArcGIS二次开发知识点总结「建议收藏」

    ArcGIS二次开发知识点总结「建议收藏」空间分析定义:空间分析是指分析具有空间坐标或相对位置的数据和过程的理论和方法,是对地理空间现象的定量研究,其目的在于提取并传输空间数据中隐含的空间信息。叠置分析定义:是指将同一坐标系统下不同信息表达的两组或多组专题要素的图层进行叠加,从而产生一个新图层的过程缓冲区分析定义:是指根据分析对象的点、线、面实体,自动建立其周围一定距离的带状区,用以识别这些实体或者主体对邻近对象的辐射范围或者…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号