查找算法——俄罗斯轮盘赌算法（看谁运气不好）

俄罗斯轮盘赌的基本思想

俄罗斯轮盘赌（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)