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

怼烎@ 2022-09-10 13:25 127阅读 0赞

![Russian roulette\_画板 1][Russian roulette_ 1]

**俄罗斯轮盘赌的基本思想**

俄罗斯轮盘赌（Russian roulette）是一种残忍的赌博游戏。俄罗斯轮盘赌的赌具是左轮手枪\]和人的性命。俄罗斯轮盘赌的规则很简单：在左轮手枪的六个弹槽中放入一颗或多颗子弹，任意旋转转轮之后，关上转轮。游戏的参加者轮流把手枪对着自己的头，扣动板机；中枪的当然是自动退出，怯场的也为输，坚持到最后的就是胜者。

只要运气不好，每次都会第一次找到。

**步骤**

> 俄罗斯轮盘赌的核心在于装入子弹之后任意旋转转轮，增加了随机性。

1.  根据随机数生成开始的下标，并进行标记。
2.  从标记处开始循环顺序查找。
3.  直到循环一遍还未找到则停止。

**算法代码**

#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)

[Russian roulette_ 1]: /images/20220829/301d4a775c134f6694b72d649db2f4be.png