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

数学建模练习小题目

题目A

有三名商人各带一名仆人过河,船最多能载两人。在河的任何一岸,若仆人数超 过商人数,仆人会杀商人越货。如何乘船由商人决定,问是否有安全过河方案,若有,最少需要几步?

定义变量

商人和仆人的状态:使用状态 (M, S) 来表示某一岸上的商人数和仆人数。

船的状态:由于船只能在两岸之间移动,使用一个二元变量来表示船的位置,1 表示船在左岸(起始岸),0 表示船在右岸(目标岸)。

因此,系统的一个状态可以表示为三元组 (M, S, B),其中,M 表示左岸的商人数,S 表示左岸的仆人数,B 表示船的位置(左岸或右岸),定义初始状态为 (3, 3, 1),目标状态为 (0, 0, 0),即所有人都在右岸。

状态转换

在问题的解决过程中,船一次可以带1或2人过河,因此允许的操作包括一名商人和一名仆人一起过河 (1, 1),两名商人一起过河 (2, 0),两名仆人一起过河 (0, 2),一名商人过河 (1, 0),一名仆人过河 (0, 1)

基于当前船所在的位置,商人和仆人要么从左岸到右岸(如果船在左岸),要么从右岸到左岸(如果船在右岸)。

合法状态条件:

如果左岸有商人和仆人,必须满足左岸的商人数 >= 左岸的仆人数。

如果右岸有商人和仆人,也必须满足右岸的商人数 >= 右岸的仆人数。

如果某岸没有商人,则无需考虑仆人数量。

目标函数

问题的目标是找到一种安全的过河策略,使得所有商人和仆人安全过河,并且最少步数完成过河过程。步数是需要最小化的目标函数。

约束条件

  1. 每次船的载重不能超过两人。

  2. 每次过河之后,任何一岸的仆人数不能超过商人数。

  3. 商人决定乘船方案,仆人不能独立决定过河。

BFS求解

广度优先搜索(BFS)是一种常用来寻找最短路径的算法,适合用来解决这种问题。

具体步骤如下:

  1. 从初始状态 (3, 3, 1) 开始,加入队列。

  2. 对于队列中的每个状态,尝试所有可能的合法过河方式,生成新状态。

  3. 如果新状态满足安全条件并且没有被访问过,将其加入队列。

  4. 当某个状态到达目标状态 (0, 0, 0) 时,停止搜索,返回路径。

  5. 如果所有状态都搜索完毕还没有找到解,则说明问题无解。

from collections import deque
​
# 定义初始状态 (左岸商人数量, 左岸仆人数量, 船所在岸 1表示左岸, 0表示右岸)
initial_state = (3, 3, 1)
goal_state = (0, 0, 0)
​
# 检查状态是否合法
def is_valid(state):left_m, left_s, _ = stateright_m = 3 - left_mright_s = 3 - left_s# 检查两岸的商人数和仆人数比例if (left_m >= 0 and left_s >= 0 and left_m >= left_s) or left_m == 0:if (right_m >= 0 and right_s >= 0 and right_m >= right_s) or right_m == 0:return Truereturn False
​
# 使用BFS算法来搜索最优解
def bfs():queue = deque([(initial_state, [])])  # 队列保存当前状态和走过的路径visited = set()  # 记录已经访问过的状态visited.add(initial_state)while queue:current_state, path = queue.popleft()# 如果到达目标状态,返回路径if current_state[:2] == goal_state[:2] and current_state[2] == goal_state[2]:return path + [current_state]left_m, left_s, boat = current_statenew_boat = 1 - boat  # 切换船所在的岸# 定义所有可能的船的移动情况moves = [(1, 0), (0, 1), (1, 1), (2, 0), (0, 2)  # (商人移动数量, 仆人移动数量)]for move_m, move_s in moves:if boat == 1:  # 如果船在左岸new_state = (left_m - move_m, left_s - move_s, new_boat)else:  # 如果船在右岸new_state = (left_m + move_m, left_s + move_s, new_boat)# 检查新状态是否合法if is_valid(new_state) and new_state not in visited:visited.add(new_state)queue.append((new_state, path + [current_state]))
​return None
​
# 运行BFS算法
result = bfs()
​
if result:print("找到安全过河方案,最少步骤为:", len(result) - 1)for step in result:print(step)
else:print("没有找到安全过河方案。")

求解结果

找到安全过河方案,最少步骤为: 11
(3, 3, 1)
(2, 2, 0)
(3, 2, 1)
(3, 0, 0)
(3, 1, 1)
(1, 1, 0)
(2, 2, 1)
(0, 2, 0)
(0, 3, 1)
(0, 1, 0)
(1, 1, 1)
(0, 0, 0)

得到方案如下:

商人和仆人最少经过11步安全渡河。首先,一名商人和一名仆人过河,两岸各有2名商人和2名仆人。接着,一名仆人回到左岸,左岸有3名商人和2名仆人。然后,两名仆人过河,左岸剩下3名商人,右岸有3名仆人和2名商人。接着一名仆人返回左岸,左岸有3名商人和1名仆人。随后,两名商人过河,左岸剩下1名商人和1名仆人。接着一名商人和一名仆人返回,左右岸再次各有2名商人和2名仆人。然后两名商人过河,左岸只剩下仆人,右岸有4名商人和2名仆人。接着一名仆人回到左岸,左岸有1名仆人,右岸有4名商人和1名仆人。随后两名仆人过河,右岸所有人到达。最后,一名仆人回到左岸,并带着最后的商人和仆人安全到达右岸,完成全部渡河过程。

问题C

四个著名的音乐人受邀成为一场音乐比赛的评委,评委席的座次安排一他们互相谦让,最后组委会不得不让他们投票选出自己心中的座次安排,如果你是组委会拿到了如下的投票结果,请问你将如何安排座次?(注:排在最前面的坐首席)

甲:乙丙甲丁
乙:丙甲丁乙
丙:甲丙丁乙
丁:甲丙乙丁

解:根据每个人的投票顺序,为每个评委进行排序打分。排名越靠前,得分越高。假设排名第一得 3 分,排名第二得 2 分,排名第三得 1 分,排名第四得 0 分;然后将所有投票结果进行加总,得出每位评委的总分,分数高者安排在靠前的位置。

编写代码如下:

# 定义每位评委的投票顺序
votes = {'甲': ['乙', '丙', '丁', '甲'],'乙': ['丙', '甲', '丁', '乙'],'丙': ['甲', '丙', '丁', '乙'],'丁': ['甲', '丙', '乙', '丁']
}
# 初始化得分表
scores = {'甲': 0, '乙': 0, '丙': 0, '丁': 0}
# 给每个评委根据投票顺序打分
for voter, ranking in votes.items():# 第一名得3分,第二名得2分,第三名得1分,第四名得0分for i, candidate in enumerate(ranking):scores[candidate] += 3 - i
# 按得分从高到低排序
sorted_scores = sorted(scores.items(), key=lambda x: x[1], reverse=True)
# 输出最终座次安排
print("最终座次安排:")
for i, (name, score) in enumerate(sorted_scores, 1):print(f"第{i}名: {name},得分: {score}")

求得结果:

最终座次安排:
第1名: 丙,得分: 9
第2名: 甲,得分: 8
第3名: 乙,得分: 4
第4名: 丁,得分: 3

故应将座位安排为丙甲乙丁。

相关文章:

数学建模练习小题目

题目A 有三名商人各带一名仆人过河,船最多能载两人。在河的任何一岸,若仆人数超 过商人数,仆人会杀商人越货。如何乘船由商人决定,问是否有安全过河方案,若有,最少需要几步? 定义变量 商人和仆人的状态…...

不可错过的10款文件加密软件,企业电脑加密文件哪个软件好用

在信息安全日益重要的今天,企业和个人都需要可靠的文件加密软件来保护敏感数据。以下是2024年不可错过的10款文件加密软件,它们以强大的加密功能和易用性而闻名。 1.安秉加密软件 安秉加密软件是一款专为企业设计的信息安全管理工具,采用驱动…...

常用卫星学习

文章目录 Landsat-8 Landsat-8 由一台操作陆地成像仪 (OLI) 和一台热红外传感器 (TIRS)的卫星,OLI 提供 9 个波段,覆盖 0.43–2.29 μm 的波长,其中全色波段(一般指0.5μm到0.75μm左…...

音视频入门基础:FLV专题(3)——FLV header简介

一、引言 本文对FLV格式的FLV header进行简介,FLV文件的开头就是FLV header。 进行简介之前,请各位先从《音视频入门基础:FLV专题(1)——FLV官方文档下载》下载FLV的官方文档《video_file_format_spec_v10_1.pdf》和…...

python中数据处理库,机器学习库以及自动化与爬虫

Python 在数据处理、机器学习和自动化任务方面非常强大,它的库生态系统几乎涵盖了所有相关领域。我们将从以下几个部分来介绍 Python 中最常用的库: 数据处理库:Pandas、NumPy 等机器学习库:Scikit-learn、TensorFlow、Keras 等自…...

2024最新测评:低代码平台在企业复杂应用场景的适用性如何?

低代码平台种类多,不好一概而论。但最近有做部分低代码平台的测评,供大家参考。 一个月前接到老板紧急任务:调研有没有一款低代码平台能开发我司的软件场景。我司是一家快速发展中的制造业企业,业务遍布全国,需要一个…...

URL中 / 作为字符串,而不是路径。

在Harbor中,仓库路径是二级,有时候在打镜像的时候,会把 / 作为字符串打进去,URL访问的时候有可能就当路径了。 解决办法:/ 转义 %252F...

el-input只能输入指定范围的数字

el-input只能输入指定范围的数字 需求:el-input只能输入指定范围的数字,不采用el-input-number组件。 几个关键点如下 v-model.numbertype"number"min"1" max"999999" 数字的范围 οninput"validity.valid ||(value…...

数据结构编程实践20讲(Python版)—01数组

本文目录 01 数组 arrayS1 说明S2 举例S3 问题:二维网格中的最小路径求解思路Python3程序 S4 问题:图像左右变换求解思路Python3程序 S5 问题:青蛙过河求解思路Python3程序 写在前面 数据结构是计算机科学中的一个重要概念,用于组…...

数据库实验2—1

10-1 查询重量在[40,65]之间的产品信息 本题目要求编写SQL语句&#xff0c; 检索出product表中所有符合40 < Weight < 65的记录。 提示&#xff1a;请使用SELECT语句作答。 表结构: CREATE TABLE product (Pid varchar(20), --商品编号PName varchar(50), --商品名称…...

现代前端框架实战指南:React、Vue.js、Angular核心概念与应用

随着互联网技术的发展&#xff0c;前端开发变得越来越复杂。 为了应对这些挑战&#xff0c;前端框架应运而生&#xff0c;它们提供了丰富的功能和工具&#xff0c;帮助开发者更高效地构建 和维护大型前端应用。前端框架是现代Web开发中不可或缺的一部分&#xff0c;它们提供了…...

MySQL --用户管理

文章目录 1.用户1.1用户信息1.2创建用户1.3删除用户1.4修改用户密码 2.数据库的权限2.1给用户授权2.2回收权限 如果我们只能使用root用户&#xff0c;这样存在安全隐患。这时&#xff0c;就需要使用MySQL的用户管理。 1.用户 1.1用户信息 MySQL中的用户&#xff0c;都存储在系…...

详解前驱图与PV操作

前驱图、PV操作 前驱图与PV操作的结合例子&#xff1a;两个进程的同步问题使用PV操作实现同步 前驱图的实际应用更复杂的场景示例示例1&#xff1a;前驱图与PV操作的结合1. 前驱图表示2. 使用信号量&#xff08;PV操作&#xff09;实现同步进程的执行逻辑&#xff1a; 3. 示例代…...

孩子来加拿大上学真的那么轻松吗?(上)

点击文末“阅读原文”即可参与节目互动 剪辑、音频 / 卷圈 运营 / SandLiu 卷圈 监制 / 姝琦 封面 / 姝琦Midjourney 产品统筹 / bobo 这是拼娃时代第三十一期节目&#xff0c;经过了一年的沉寂&#xff0c;拼娃时代在今年九月份终于恢复更新啦&#xff0c;JunJun老师也…...

【算法篇】二叉树类(1)(笔记)

目录 一、认识二叉树 1. 二叉树的种类 &#xff08;1&#xff09;满二叉树 &#xff08;2&#xff09;完全二叉树 &#xff08;3&#xff09;二叉搜索树 &#xff08;4&#xff09;平衡二叉搜索树 2. 二叉树的存储方式 3. 二叉树的遍历方式 4. 二叉树的定义 二、Leet…...

《C++无锁编程:解锁高性能并发的新境界》

在当今的软件开发领域&#xff0c;并发编程的重要性日益凸显。随着多核处理器的普及&#xff0c;开发者们越来越需要利用并发来提高程序的性能和响应速度。而 C作为一种强大的编程语言&#xff0c;提供了多种技术来实现无锁编程&#xff0c;从而在并发环境下获得更高的性能和更…...

系统架构设计师教程 第9章 9.5 软件可靠性测试 笔记

9.5 软件可靠性测试 ★★★☆☆ 9.5.1 软件可靠性测试概述 软件测试者可以使用很多方法进行软件测试&#xff0c;如按行为或结构来划分输入域的划分测试&#xff0c; 纯粹随机选择输入的随机测试&#xff0c;基于功能、路径、数据流或控制流的覆盖测试等。 软件可靠性测试由可…...

如何使用ssm实现校园体育赛事管理系统的设计与实现+vue

TOC ssm713校园体育赛事管理系统的设计与实现vue 绪论 课题背景 身处网络时代&#xff0c;随着网络系统体系发展的不断成熟和完善&#xff0c;人们的生活也随之发生了很大的变化。目前&#xff0c;人们在追求较高物质生活的同时&#xff0c;也在想着如何使自身的精神内涵得…...

CSS 中的文本相关属性(line - height、font、letter - 属性、text - 属性)

目录 非 VIP 用户可前往公众号回复“css”进行免费阅读 line - height属性 字号与行高的取值约定 行高与盒子高度的关系 font、letter -属性 、text -属性 font属性 letter -属性 text - 属性 非 VIP 用户可前往公众号回复“css”进行免费阅读 line - height属性 字号与…...

mobaxterm、vscode通过跳板机连接服务器

目标服务器&#xff1a;111.111.11.11 跳板机&#xff1a;100.100.10.10 1. mobaxterm通过跳板机连接服务器 1.1 目标服务器信息 1.2 跳板机信息 1.3 登录 点击登录&#xff0c;会输入密码&#xff0c;成功 参考&#xff1a;https://blog.csdn.net/qq_40636486/article/det…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

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

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

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...