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

发表于

这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战

俄罗斯轮盘赌的基本思想

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

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

步骤

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

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

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
c++复制代码#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)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%