常见抽牌洗牌算法
最近玩卡牌游戏比较多，了解了一下洗牌抽牌的算法。参考了原博客（https://blog.csdn.net/qq_26399665/article/details/79831490）的内容
1.Fisher-Yates Shuffle算法
（1）每次随机将原始数组的元素抽出.
（2）把该元素放到新数组中
（3）然后删除原始数组中的该元素
（4）重复123步直到原始数组为空
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
void Fisher_Yates_Shuffle(vector<int> & v1,vector<int> &v2){
srand((unsigned)time(NULL));
int len=v1.size();//v1的长度
for(int i=0;i<len;i++){
int temp=rand()%(v1.size()); //（1）每次随机将原始池的元素抽出.
v2.push_back(v1[temp]);//（2）把该元素放到新池中
v1.erase(v1.begin()+temp); //（3）然后删除原始池中的该元素
}
}
int main(){
int n;
vector<int> v1={2,5,9,7,6,31};
vector<int> v2={};
Fisher_Yates_Shuffle(v1,v2);
for(int i=0;i<v2.size();i++){
cout<<v2[i]<<" ";
}
return 0;
}
2.Knuth-Durstenfeld Shuffle 算法
这种方法比第一种更节约空间，但是会打乱原始数组的顺序
（1）在前n个数中随机生成一个下标，将该数字与第n个数字交换
（2）接着从前n-1个数字中随机生成一个下标，将该数字与第n-1个数字交换
（3）重复12步直到所有数字都被交换完了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
void Knuth_Durstenfeld_Shuffle(vector<int> & v1){
srand((unsigned)time(NULL));
for(int i=v1.size()-1;i>=0;i--){
int temp=rand()%(i+1);
swap(v1[i],v1[temp]);
}
}
int main(){
int n;
vector<int> v1={2,5,9,7,6,31};
Knuth_Durstenfeld_Shuffle(v1);
for(int i=0;i<v1.size();i++){
cout<<v1[i]<<" ";
}
return 0;
}
3.Inside-Out Algorithm
（1）将新数组第k个元素放到新数组第i个位置。
（2）将原始数组v1中的第i个元素放到新数组v2的第k个位置(k<i)
然后重复以上步骤直到i=n
其实效果相当于新数组中位置k和位置i的数字进行交互。
void Inside_Out_Shuffle(const vector<int>&arr,vector<int>& res)
{
res.assign(arr.size(),0);
copy(arr.begin(),arr.end(),res.begin());
int k;
for (int i=0;i<arr.size();++i)
{
srand((unsigned)time(NULL));
k=rand()%(i+1);
res[i]=res[k];
res[k]=arr[i];
}
}
|
|