俄罗斯轮盘赌的基本思想
俄罗斯轮盘赌(Russian roulette)是一种残忍的赌博游戏。俄罗斯轮盘赌的赌具是左轮手枪]和人的性命。俄罗斯轮盘赌的规则很简单:在左轮手枪的六个弹槽中放入一颗或多颗子弹,任意旋转转轮之后,关上转轮。游戏的参加者轮流把手枪对着自己的头,扣动板机;中枪的当然是自动退出,怯场的也为输,坚持到最后的就是胜者。
只要运气不好,每次都会第一次找到。
步骤
根据随机数生成开始的下标,并进行标记。从标记处开始循环顺序查找。直到循环一遍还未找到则停止。俄罗斯轮盘赌的核心在于装入子弹之后任意旋转转轮,增加了随机性。
算法代码
#include <iostream>#include <cstdlib>#include <ctime>using namespace std;//俄罗斯轮盘赌算法 void DrawAlgorithm(int nums[],int n,int bullet){srand((int)time(0));int begin=rand()%n,mark=begin,count=0;//利用随机数生成第一次比较的下标 begin,mark 对第一次比较的位置进行标记 do{count++;if(nums[begin]==bullet){//查看当前位置的元素是否存在于 bullets 数组 cout<<bullet<<"已找到,查找次数为:"<<count<<endl;//如果存在则命中 return;}if(++begin==n){//判断是否越界begin=0;}}while(mark!=begin);//如果循环一遍代表没有找到 cout<<"没有找到"<<endl;}//打印数组 void printNum(int numbers[],int n){for(int i=0;i<n;i++){cout<<numbers[i]<<" ";}cout<<endl; }int main(){int numbers[10]={3,44,38,5,47,15,99,32,66,100};int n=sizeof(numbers)/sizeof(numbers[0]);//数组长度 cout<<"序列为:";printNum(numbers,n);DrawAlgorithm(numbers,n,5);//调用 DrawAlgorithm 函数在 numbers 序列中进行抽签查找 5 return 0;}
算法性能分析
空间复杂度:O(1)O(1)O(1)时间复杂度 最好情况下时间复杂度:O(1)O(1)O(1)最坏情况下时间复杂度:O(n)O(n)O(n)