当前位置: 首页 > news >正文

【算法】经典博弈论问题——巴什博弈 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 1n30

对于 60 % 60\% 60% 的数据, 1 ≤ n ≤ 1 0 6 1\leq n\leq 10^6 1n106

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 5 × 1 0 7 1\leq n\leq 5\times 10^7 1n5×107, 1 ≤ T ≤ 1 0 5 1\leq T\leq 10^5 1T105

(改编题)


思路

每次可以拿质数的自然数次方颗石子
对于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数据库的监控

文章来源&#xff1a;乐维社区 Doris数据库背景 Doris&#xff08;Apache Doris&#xff09;是一个现代化的MPP&#xff08;Massive Parallel Processing&#xff0c;大规模并行处理&#xff09;数据库&#xff0c;主要用于在线分析处理&#xff08;OLAP&#xff09;场景。 D…...

【豆包MarsCode蛇年编程大作战】花样贪吃蛇

目录 引言 展示效果 prompt提示信息 第一次提示&#xff08;实现基本功能&#xff09; 初次实现效果 第二次提示&#xff08;美化UI&#xff09; 第一次美化后的效果 第二次美化后的效果 代码展示 实现在线体验链接 码上掘金使用教程 体验地址&#xff1a; 花样贪吃蛇…...

企业级流程架构设计思路-基于价值链的流程架构

获取更多企业流程资料 纸上得来终觉浅&#xff0c;绝知此事要躬行 一.企业流程分级规则定义 1.流程分类分级的总体原则 2.完整的流程体系需要体现出流程的分类分级 03.通用的流程分级方法 04.流程分级的标准 二.企业流程架构设计原则 1.流程架构设计原则 流程框架是流程体…...

AI编程工具使用技巧:在Visual Studio Code中高效利用阿里云通义灵码

AI编程工具使用技巧&#xff1a;在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版本 应用场景钉钉界面操作程序开发效果展示 应用场景 由于工作需要&#xff0c;很多项目执行程序后出现报错信息无法第一时间收到&#xff0c;因此实时预警对于监控程序还是有必要。&#xff08;仅个人观点&#xff09; 参考文档及博客&#xff1a…...

细说STM32F407单片机电源低功耗StandbyMode待机模式及应用示例

目录 一、待机模式基础知识 1、进入待机模式 2、待机模式的状态 3、退出待机模式 二、待机模式应用示例 1、示例功能和CubeMX项目设置 &#xff08;1&#xff09; 时钟 &#xff08;2&#xff09; DEBUG、LED1、KeyRight、USART6、CodeGenerator &#xff08;3&#x…...

IOS 安全机制拦截 window.open

摘要 在ios环境&#xff0c;在某些情况下执行window.open不生效 一、window.open window.open(url, target, windowFeatures) 1. url&#xff1a;「可选参数」&#xff0c;表示你要加载的资源URL或路径&#xff0c;如果不传&#xff0c;则打开一个url地址为about:blank的空…...

jmeter中对接口进行循环请求后获取相应数据

1、工作中遇到一个场景就是对某个单一接口进行循环请求&#xff0c;并需要获取每次请求后返回的相应数据&#xff1b; 2、首先就在jmeter对接口相关组件进行配置&#xff0c;需要组件有&#xff1a;循环控制器、CSV数据文件设置、计数器、访问接口、HTTP信息头管理器、正则表达…...

【QT】-explicit关键字

explicit explicit 是一个 C 关键字&#xff0c;用于修饰构造函数。它的作用是防止构造函数进行隐式转换。 为什么需要 explicit&#xff1f; 在没有 explicit 的情况下&#xff0c;构造函数可以用于隐式类型转换。这意味着&#xff0c;如果你有一个接受某种类型的参数的构造…...

【深度学习】 自动微分

自动微分 正如上节所说&#xff0c;求导是几乎所有深度学习优化算法的关键步骤。 虽然求导的计算很简单&#xff0c;只需要一些基本的微积分。 但对于复杂的模型&#xff0c;手工进行更新是一件很痛苦的事情&#xff08;而且经常容易出错&#xff09;。 深度学习框架通过自动…...

字节跳动自研HTTP开源框架Hertz简介附使用示例

字节跳动自研 HTTP 框架 Hertz Hertz 是字节跳动自研的高性能 HTTP 框架&#xff0c;专为高并发、低延迟的场景设计。它基于 Go 语言开发&#xff0c;结合了字节跳动在微服务架构中的实践经验&#xff0c;旨在提供更高效的 HTTP 服务开发体验。 1. 背景介绍 随着字节跳动业务…...

skynet 源码阅读 -- 核心概念服务 skynet_context

本文从 Skynet 源码层面深入解读 服务&#xff08;Service&#xff09; 的创建流程。从最基础的概念出发&#xff0c;逐步深入 skynet_context_new 函数、相关数据结构&#xff08;skynet_context, skynet_module, message_queue 等&#xff09;&#xff0c;并通过流程图、结构…...

每日十题八股-2025年1月23日

1.快排为什么时间复杂度最差是O&#xff08;n^2&#xff09; 2.快排这么强&#xff0c;那冒泡排序还有必要吗&#xff1f; 3.如果要对一个很大的数据集&#xff0c;进行排序&#xff0c;而没办法一次性在内存排序&#xff0c;这时候怎么办&#xff1f; 4.面试官&#xff1a;你的…...

MongoDB部署模式

目录 单节点模式&#xff08;Standalone&#xff09; 副本集模式&#xff08;Replica Set&#xff09; 分片集群模式&#xff08;Sharded Cluster&#xff09; MongoDB有多种部署模式&#xff0c;可以根据业务需求选择适合的架构和部署方式。 单节点模式&#xff08;Standa…...

opencv笔记2

图像灰度 彩色图像转化为灰度图像的过程是图像的灰度化处理。彩色图像中的每个像素的颜色由R&#xff0c;G&#xff0c;B三个分量决定&#xff0c;而每个分量中可取值0-255&#xff0c;这样一个像素点可以有256*256*256变化。而灰度图像是R&#xff0c;G&#xff0c;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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...