【算法】经典博弈论问题——巴什博弈 python
目录
- 前言
- 巴什博弈(Bash Game)
- 小试牛刀
- PN分析
- 实战检验
- 总结
前言
博弈类问题大致分为:
公平组合游戏、非公平组合游戏(绝大多数的棋类游戏)和 反常游戏
巴什博弈(Bash Game)
一共有n颗石子,两个人轮流拿,每次可以拿1~m颗石子
最先取光石子的一方为胜(没有石子可以拿的人为败),根据n、m返回谁赢
分析:
我们从最简单的情景开始分析
当石子有 1−m 个时,先手必胜(一次拿完)
当石子有m+1个时,先手无论拿几个,后手都可以拿完,先手必败
不难发现:面临 m+1个石子的人一定失败。
这样的话,最优策略一定是:通过拿走石子,使得对方拿石子时还有 m+1个剩余
推广至一般情况:
【1】当n不可被m+1整除时,先手必胜
为什么? n %(m+1)= r,先手拿走 r ,后手即面临 m+1的整数倍颗石子,必败
【2】同理,当n可被m+1整除时,先手必败
测试链接 hduoj1846
示例code:
c = int(input())
for _ in range(c):n, m = map(int, input().split())if n % (m + 1) == 0:print("second")else:print("first")
小试牛刀
hduoj2188

题解:
# 和前面几乎一样的code
c = int(input())
for _ in range(c):n, m = map(int, input().split())if n % (m + 1) != 0:print("Grass")else:print("Rabbit")
PN分析

实战检验
Roy&October之取石子
题目背景
Roy 和 October 两人在玩一个取石子的游戏。
题目描述
游戏规则是这样的:共有 n n n 个石子,两人每次都只能取 p k p^k pk 个( p p p 为质数, k k k 为自然数,且 p k p^k pk 小于等于当前剩余石子数),谁取走最后一个石子,谁就赢了。
现在 October 先取,问她有没有必胜策略。
若她有必胜策略,输出一行 October wins!;否则输出一行 Roy wins!。
输入格式
第一行一个正整数 T T T,表示测试点组数。
第 2 2 2 行 ∼ \sim ∼ 第 T + 1 T+1 T+1 行,一行一个正整数 n n n,表示石子个数。
输出格式
T T T 行,每行分别为 October wins! 或 Roy wins!。
样例输入
3
4
9
14
样例输出
October wins!
October wins!
October wins!
提示
对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 30 1\leq n\leq 30 1≤n≤30;
对于 60 % 60\% 60% 的数据, 1 ≤ n ≤ 1 0 6 1\leq n\leq 10^6 1≤n≤106;
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 5 × 1 0 7 1\leq n\leq 5\times 10^7 1≤n≤5×107, 1 ≤ T ≤ 1 0 5 1\leq T\leq 10^5 1≤T≤105。
(改编题)
思路:
每次可以拿质数的自然数次方颗石子
对于6的倍数,一定不是质数的某一自然数次方
1,2,3,4,5都可以一次取到,
当n=6时,第一个人无论怎么取,后手赢
推至一般情况:
当n不是6的倍数,先手赢
当n是6的倍数,后手赢
题解代码:
t = int(input())
for _ in range(t):n = int(input())if n % 6 == 0:print("Roy wins!")else:print("October wins!")
总结
巴什博弈是一个相对简单的问题,但它引入了重要的概念,比如P态和N态的概念,对理解更复杂的组合博弈非常有用。
此外,如何通过数学公式快速得出结论也是解决此类问题的关键技巧之一。
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢
相关文章:
【算法】经典博弈论问题——巴什博弈 python
目录 前言巴什博弈(Bash Game)小试牛刀PN分析实战检验总结 前言 博弈类问题大致分为: 公平组合游戏、非公平组合游戏(绝大多数的棋类游戏)和 反常游戏 巴什博弈(Bash Game) 一共有n颗石子,两个人轮流拿,每次可以拿1~m颗…...
ES6语法
一、Let、const、var变量定义 1.let 声明的变量有严格局部作用域 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"&g…...
窥探QCC518x-308x系列与手机之间的蓝牙HCI记录与分析 - 耳机篇
上一篇是介绍如何窥探手机端Bluetooth的HCI log, 本次介绍是如何窥探Bluetooth的HCI log-耳机篇. 这次跟QCC518x/QCC308x测试的手机是Samsung S23 Ultra. QCC518x/QCC308x透过HCI界面取得Log教学. 步骤1: 开启QMDE -> 选择ADK r1102 QCC3083 Headset workspace.步骤2: 点…...
ubuntu k8s 1.31
ubuntu 系统 设置 更新源 apt-get upgradeapt upgradeapt update apt-get update释放root sudo passwd root密码su - 密码设置root可以登录 cd /etc/ssh/sshd_config.d && vi ssh.confPermitRootLogin yes PasswordAuthentication yes:wq 保存退出 systemctl resta…...
Prometheus+grafana实践:Doris数据库的监控
文章来源:乐维社区 Doris数据库背景 Doris(Apache Doris)是一个现代化的MPP(Massive Parallel Processing,大规模并行处理)数据库,主要用于在线分析处理(OLAP)场景。 D…...
【豆包MarsCode蛇年编程大作战】花样贪吃蛇
目录 引言 展示效果 prompt提示信息 第一次提示(实现基本功能) 初次实现效果 第二次提示(美化UI) 第一次美化后的效果 第二次美化后的效果 代码展示 实现在线体验链接 码上掘金使用教程 体验地址: 花样贪吃蛇…...
企业级流程架构设计思路-基于价值链的流程架构
获取更多企业流程资料 纸上得来终觉浅,绝知此事要躬行 一.企业流程分级规则定义 1.流程分类分级的总体原则 2.完整的流程体系需要体现出流程的分类分级 03.通用的流程分级方法 04.流程分级的标准 二.企业流程架构设计原则 1.流程架构设计原则 流程框架是流程体…...
AI编程工具使用技巧:在Visual Studio Code中高效利用阿里云通义灵码
AI编程工具使用技巧:在Visual Studio Code中高效利用阿里云通义灵码 前言一、通义灵码介绍1.1 通义灵码简介1.2 主要功能1.3 版本选择1.4 支持环境 二、Visual Studio Code介绍1.1 VS Code简介1.2 主要特点 三、安装VsCode3.1下载VsCode3.2.安装VsCode3.3 打开VsCod…...
钉钉群机器人设置——python版本
钉钉群机器人设置——python版本 应用场景钉钉界面操作程序开发效果展示 应用场景 由于工作需要,很多项目执行程序后出现报错信息无法第一时间收到,因此实时预警对于监控程序还是有必要。(仅个人观点) 参考文档及博客:…...
细说STM32F407单片机电源低功耗StandbyMode待机模式及应用示例
目录 一、待机模式基础知识 1、进入待机模式 2、待机模式的状态 3、退出待机模式 二、待机模式应用示例 1、示例功能和CubeMX项目设置 (1) 时钟 (2) DEBUG、LED1、KeyRight、USART6、CodeGenerator (3&#x…...
IOS 安全机制拦截 window.open
摘要 在ios环境,在某些情况下执行window.open不生效 一、window.open window.open(url, target, windowFeatures) 1. url:「可选参数」,表示你要加载的资源URL或路径,如果不传,则打开一个url地址为about:blank的空…...
jmeter中对接口进行循环请求后获取相应数据
1、工作中遇到一个场景就是对某个单一接口进行循环请求,并需要获取每次请求后返回的相应数据; 2、首先就在jmeter对接口相关组件进行配置,需要组件有:循环控制器、CSV数据文件设置、计数器、访问接口、HTTP信息头管理器、正则表达…...
【QT】-explicit关键字
explicit explicit 是一个 C 关键字,用于修饰构造函数。它的作用是防止构造函数进行隐式转换。 为什么需要 explicit? 在没有 explicit 的情况下,构造函数可以用于隐式类型转换。这意味着,如果你有一个接受某种类型的参数的构造…...
【深度学习】 自动微分
自动微分 正如上节所说,求导是几乎所有深度学习优化算法的关键步骤。 虽然求导的计算很简单,只需要一些基本的微积分。 但对于复杂的模型,手工进行更新是一件很痛苦的事情(而且经常容易出错)。 深度学习框架通过自动…...
字节跳动自研HTTP开源框架Hertz简介附使用示例
字节跳动自研 HTTP 框架 Hertz Hertz 是字节跳动自研的高性能 HTTP 框架,专为高并发、低延迟的场景设计。它基于 Go 语言开发,结合了字节跳动在微服务架构中的实践经验,旨在提供更高效的 HTTP 服务开发体验。 1. 背景介绍 随着字节跳动业务…...
skynet 源码阅读 -- 核心概念服务 skynet_context
本文从 Skynet 源码层面深入解读 服务(Service) 的创建流程。从最基础的概念出发,逐步深入 skynet_context_new 函数、相关数据结构(skynet_context, skynet_module, message_queue 等),并通过流程图、结构…...
每日十题八股-2025年1月23日
1.快排为什么时间复杂度最差是O(n^2) 2.快排这么强,那冒泡排序还有必要吗? 3.如果要对一个很大的数据集,进行排序,而没办法一次性在内存排序,这时候怎么办? 4.面试官:你的…...
MongoDB部署模式
目录 单节点模式(Standalone) 副本集模式(Replica Set) 分片集群模式(Sharded Cluster) MongoDB有多种部署模式,可以根据业务需求选择适合的架构和部署方式。 单节点模式(Standa…...
opencv笔记2
图像灰度 彩色图像转化为灰度图像的过程是图像的灰度化处理。彩色图像中的每个像素的颜色由R,G,B三个分量决定,而每个分量中可取值0-255,这样一个像素点可以有256*256*256变化。而灰度图像是R,G,B三个分量…...
springboot使用ssl连接elasticsearch
使用es时ssl证书报错 unable to find valid certification path to requested target 1.依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-elasticsearch</artifactId></dependency>2…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
