【对算法期中卷子的解析和反思】
一、程序阅读并回答问题(共30分)
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- using namespace std;
- char chess[10][10];
- int sign[10];
- int n, k, ans;
- void dfs(int x, int k)
- {
- if (k == 0){
- ans++;
- return;
- }
- if (x+k-1 > n)
- return;
- for (int i = x; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (!sign[j] && chess[i][j] == '#'){
- sign[j] = 1;
- dfs(i + 1, k - 1);
- sign[j] = 0;
- }
- }
- int main()
- {
- while (cin >> n >> k){
- memset(chess, 0, sizeof(chess));
- memset(sign, 0, sizeof(sign));
- if (n == -1 || k == -1)
- break;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- cin >> chess[i][j];
- ans = 0;
- dfs(1, k);
- cout << ans << endl;
- }
- return 0;
- }
设程序的输入如下,请写出程序执行到35行时变量chess的值。(3分)
4 4
...#
..#.
.#..
#...
-1 -1
这里的坑点就是chess[][]的范围是[0-9][0-9],很多人没考虑多余的部分
chess[1][1]~Chess[1][4]的值分别为“.”,“.”,“.”,“#”。
chess[2][1]~Chess[2][4]的值分别为“.”,“.”,“#”,“.”。
chess[3][1]~Chess[3][4]的值分别为“.”,“#”,“.”,“.”。
chess[4][1]~chess[4][4]的值分别为“#”,“.”,“.”,“.”。
其余值为0。
分析函数dfs(.)的时间复杂度,写出分析求解过程。(12分)
这个时间复杂度也是,跟之前的答案出来的还不一样,逆天
以前这个,纯纯数学公式推出来的,啥初始条件都是浮云
你想想,右边是组合数,我们可以理解为n列中选K列,再粗略的n行选、n-1行选......左边也该是个阶乘来着......无语
现在这个
若采用问题(1)中的输入,分析该程序的求解过程。(15分)
这个跟老师之前出的类似题写的真不一样,服了。
我觉得我这个写的是对的
二、算法分析题 (共40分)
某班级的同学正在玩一个游戏。他们在某个时刻把一个物品摆放到跑道的某个位置,设跑道的长度为10米且是笔直的。游戏前他们会把每个物品的价格,物品出现的时间和位置告诉给玩游戏的同学。假设玩游戏的同学刚开始时站在跑道的某个位置,他每秒跑的距离不超过1米。当然他可以不跑,也可以朝前或者朝后跑。他每跑到一个位置便可以快速的拾取该物品,然后以同样的速度跑到下一个位置。请问,他最多能够获得的物品的总价格是多少?
输入:
输入数据的第一行包含两个正整数n(0<n<100)和m(0<=m<=10),其中n表示待摆放的物品的个数,m表示刚开始时玩游戏同学所在的位置;在接下来的n行中,每行有3个整数x, t(0<T< 100000)和p,表示在第t秒会在x位置上摆放一个价值为p的物品。同一时刻可能在同一位置摆放多个物品。
输出:
玩游戏的同学最多能够拾取的物品的总价格是多少?
样例输入:
4 4
2 1 1
3 2 5
5 3 1
6 2 3
样例输出:
5
要求:
请写出采用穷举法求解该问题的伪代码,并画出样例输入时的解空间树。(10分)
我们的算法的起点都不一样,真不知道这咋整
请写出采用动态规划算法求解上述问题的伪代码,并用样例输入对其进行验证,写出求解过程。(20分)
也是算法不一样
【拾取问题】-CSDN博客
好吧,老师写的比我好,我需要递归,他不用,但是这个有点颠覆我的思维,我没看懂
行号 | 执行次数 | i | j | dp[i][j] | mValue |
6 | 1 | 0 | 1 | 0 | 0 |
6 | 2 | 0 | 2 | 0 | 0 |
6 | 3 | 0 | 3 | 0 | 0 |
6 | 5 | 1 | 2 | 0 | 0 |
4 | 15 | 4 | 3 | 5 | 0 |
10 | 1 | - | - | - | 5 |
我也可以给这个表格,但是定义都不一样,咋能指望一模一样
表3 动态规划求解结果(dp[i][j])
(j,i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 5 | 0 | 0 | 3 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 5 | 5 | 5 | 4 | 3 | 3 | 0 | 0 | 0 |
分析(1)中算法的时间复杂度,写出分析求解过程。(10分)
没看懂咋分析的
题(1)为三叉树,深度为lTime+1,因此T(0)=3T(1),T(lTime)=O(1),其时间复杂度为O(3lTime)。
三、算法设计及实现(共30分)
有一个2*n大小的矩形地板,用2*2和2*1大小的瓷砖方块来填满它。求一共有多少种不同的放法?如下所示:
输入:
输入包含若干行,每一行包含一个整数n(0<=n<=250),表示矩形地板的长度。
输出:
对于每一行的输出,输出一行整数,表示矩形地板的不同的摆放方法。
样例输入:
2
8
12
100
200
样例输出:
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
要求:
当n=2时,画出不同的摆放方法。(5分)
三种,略
假设长度为n时摆放两种砖块的不同摆放方法有f(n)种。如果前面两块摆放2*2的砖块,则剩余的n-2块砖块摆放两种不同砖块的摆放方法有多少种?(5分)
这里竟然是把f[n]当作函数,估计是老师像让我们用动态规划做,所以提示,答案是f[n-2]
假设长度为n时摆放两种砖块的不同摆放方法有f(n)种。如果前面1块摆放2*1的砖块,则剩余的n-1块砖块摆放两种不同的砖块总共有多少种不同的摆放方法?(5分)
f[n-1]
按题目要求编写完整程序,并简要说明算法求解思想。(15分)
【地板拼接问题】-CSDN博客
该算法的求解思想:
假设地板长度为n,有f[n]种放置2*1和2*2砖块的方法。假设某一块放2*2,则有方法数f[n-2];假设某一块竖着放2*1,则有方法数f[n-1];假设某一块横着放2*1,则有方法数f[n-2],因此得出转移方程f[n] = 2 * f[n-2] + f[n-1]
于是将求解dp[n]的问题,转化为求解dp[n-1]和dp[n-2]的问题,从而不断分解为简单的子问题,直到分解为最小子问题dp[0]=1,dp[1]=1。
相关文章:
【对算法期中卷子的解析和反思】
一、程序阅读并回答问题(共30分) #include<cstdio>#include<cstring>#include<iostream>using namespace std;char chess[10][10];int sign[10];int n, k, ans;void dfs(int x, int k) { if (k 0){ans;return; } if (xk-1 >…...
sudo apt update sudo: apt: command not found
CentOS或RHEL(Red Hat Enterprise Linux)系统上,包管理器是yum或dnf,而不是apt。您可以使用yum或dnf来安装软件包。以下是如何在CentOS或RHEL上安装Git的详细步骤: 1. 使用yum安装Git 首先,更新软件包列表&…...
ios:文本框默认的copy、past改成中文复制粘贴
问题 ios 开发,对于输入框的一些默认文案展示,如复制粘贴是英文的,那么如何改为中文的呢 解决 按照路径找到这个文件 ios/项目/Info.plist,增加 <key>CFBundleAllowMixedLocalizations</key> <true/> <…...
Qt moc系统的黑魔法?
Qt的元对象系统(Meta-Object System)是Qt框架的核心功能之一,为C语言增加了一些动态特性,借助元对象系统Qt可以实现以下功能 信号与槽机制(Signals and Slots)运行时类型信息(Run-Time Type In…...
MyBatis开发中常用总结
文章目录 常用MyBatis参数映射单个参数多个参数使用索引【不推荐】Param注解Map传参POJO【推荐】List数组 动态标签\<if>标签\<trim>标签\<where>标签\<set>标签\<foreach>标签 MyBatis查询一对一一对多 常用MyBatis参数映射 单个参数 XML中可…...
Git基本使用教程(学习记录)
参考文章链接: Git教程(超详细,一文秒懂) RUNOOB Git教程 Git学习记录 1Git概述 1.1版本控制软件功能 版本管理:更新或回退到历史上任何版本,数据备份共享代码:团队间共享代码,…...
【Linux-RTC】
Linux-RTC ■ rtc_device 结构体■ RTC 时间查看与设置■ 1、时间 RTC 查看■ 2、设置 RTC 时间 ■ rtc_device 结构体 Linux 内核将 RTC 设备抽象为 rtc_device 结构体 rtc_device 结构体,此结构体定义在 include/linux/rtc.h 文件中 ■ RTC 时间查看与设置 ■ 1…...
机器学习目录
文章目录 基本概念有监督学习回归问题分类问题 无监督学习聚类问题异常检测 基本概念 pass 有监督学习 回归问题 通过拟合函数,解决连续值的预测问题梯度下降法优化;最小二乘法求解;度量指标 均方误差;均方根误差;平…...
React开发环境配置详细讲解-04
环境简介 前端随着规范化,可以说规范和环境插件配置满天飞,笔者最早接触的是jquery,那个开发非常简单,只要引入jquery就可以了,当时还写了一套UI框架,至今在做小型项目中还在使用,show一张效果…...
Go 如何通过 Kafka 客户端库 生产与消费消息
文章目录 0.前置说明1. confluent-kafka-go2. sarama3. segmentio/kafka-go4. franz-go选择建议 1.启动 kafka 集群2.安装 confluent-kafka-go 库3.创建生产者特殊文件说明如何查看.log文件内容 4.创建消费者 0.前置说明 Go 语言中有一些流行的 Kafka 客户端库。以下是几个常用…...
【设计模式深度剖析】【B】【结构型】【对比】| 主要区别包装的不同
👈️上一篇:享元模式 回 顾:结构型设计模式 1.代理模式👈️ 2.装饰器模式👈️ 3.适配器模式👈️ 4.组合模式👈️ 5.桥接模式👈️ 6.外观模式👈️ 7.享元模式&#x…...
信息学奥赛初赛天天练-17-阅读理解-浮点数精准输出与海伦公式的巧妙应用
PDF文档公众号回复关键字:20240531 1 2023 CSP-J 阅读程序1 阅读程序(程序输入不超过数组成字符串定义的范围:判断题正确填√,错误填;除特殊说明外,判断题1.5分,选择题3分,共计40分࿰…...
mysql - 为什么MySQL不建议使用NULL作为列默认值?
为什么MySQL不建议使用NULL作为列默认值? InnoDB有4中行格式: Redundant : 非紧凑格式,5.0 版本之前用的行格式,目前很少使用,Compact : 紧凑格式,5.1 版本之后默认行格式,可以存储更多的数据Dynamic , Compressed : 和Compact类似,5.7 版本之后默认使…...
数据分析案例-在线食品订单数据可视化分析与建模分类
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
构建LangChain应用程序的示例代码:2、使用LangChain库实现的AutoGPT示例:查找马拉松获胜成绩
AutoGPT 示例:查找马拉松获胜成绩 实现 https://github.com/Significant-Gravitas/Auto-GPT,使用LangChain基础组件(大型语言模型(LLMs)、提示模板(PromptTemplates)、向量存储(VectorStores)、嵌入(Embeddings)、工具(Tools))。…...
代码随想录算法训练营第三十四 |● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果
今天的解析写在了代码注释中 1005.K次取反后最大化的数组和 讲解链接:https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html class Solution { public:static bool cmp(i…...
GB-T 43206-2023 信息安全技术 信息系统密码应用测评要求
GB-T 43206-2023 信息安全技术 信息系统密码应用测评要求 编写背景 随着信息技术的飞速发展,信息系统在社会经济活动中扮演着越来越重要的角色。信息安全问题也随之成为社会关注的焦点。GB-T 43206-2023《信息安全技术 信息系统密码应用测评要求》是针对信息系统中…...
线程进阶-1 线程池
一.说一下线程池的执行原理 1.线程池的七大核心参数 (1)int corePoolSize:核心线程数。默认情况下核心线程会一直存活,当设置allowCoreThreadTimeout为true时,核心线程也会被超时回收。 (2)i…...
LabVIEW中PID控制器系统的噪声与扰动抑制策略
在LabVIEW中处理PID控制器系统中的噪声和外部扰动,需要从信号处理、控制算法优化、硬件滤波和系统设计四个角度入手。采用滤波技术、调节PID参数、增加前馈控制和实施硬件滤波器等方法,可以有效减少噪声和扰动对系统性能的影响,提高控制系统的…...
JavaWeb笔记整理+图解——Listener监听器
欢迎大家来到这一篇章——Listener监听器 监听器和过滤器都是JavaWeb服务器三大组件(Servlet、监听器、过滤器)之一,他们对于Web开发起到了不可缺少的作用。 ps:想要补充Java知识的同学们可以移步我已经完结的JavaSE笔记&#x…...
AIGC智能办公实战 课程,祝你事业新高度
在数字化时代,人工智能(AI)已经渗透到我们生活的方方面面,从智能家居到自动驾驶,从医疗诊断到金融分析,AI助手正在改变我们的工作方式和生活质量。那么,你是否想过自己也能从零开始,…...
专科生听劝 这种情况你就不要专转本了
罗翔老师说过,读书学习主要作用是提高人的下限 我们能掌握的只有学习,以确保学历不会太差再去等机遇让自己活得更好 大部分情况来说,专科生努力去专转本挺好的提升自己准没错,我当年也是一心这样想的,但今天不得不说点…...
MySQL增删查改初阶
目录 一,数据库操作 1.关键字 show 显示当前数据库有哪些:show databases; 2.创建数据库 3.选中数据库 4.删除数据库 二,表的操作,在选中数据库的基础之上 1.查看表的结构 2.创建表 3.查看当前选中的数据库中…...
IService 接口中定义的常用方法
文心一言生成 以下是一些 IService 接口中定义的常用方法(以你提供的 UserSQL 类为例,该类继承自 ServiceImpl,因此也会拥有这些方法): 插入(新增) boolean save(T entity): 插入一条记录&…...
api网关kong对高频的慢接口进行熔断
一、背景 在生产环境,后端服务的接口响应非常慢,是因为数据库未创建索引导致。 如果QPS低的时候,因为后端服务有6个高配置的节点,虽然接口慢,还未影响到服务的正常运行。 但是,当QPS很高的时候,…...
python作业:实现一个任务列表管理系统,使用到python类、对象、循环等知识
实现一个简单的任务列表管理系统,可以用于python学习的作业或者练习。系统的功能包括: 用户可以添加任务、查看任务列表、标记任务为已完成,以及删除任务。 代码如下: class Task: def __init__(self, name, completedFalse):…...
大宋咨询(深圳产品价格调查)如何开展电子商品渠道价格监测
开展电子商品渠道价格监测是当今电商时代的重要任务之一。随着电子商务的迅猛发展,电子商品的价格波动日益频繁,市场竞争也愈发激烈。为了解优化渠道管理策略,提升品牌竞争力,大宋咨询(深圳市场调查)受客户…...
py黑帽子学习笔记_web攻击
python网络库 py2的urllib2 py3好像把urllib2继承到了标准库urllib,直接用urllib就行,urllib2在urllib里都有对应的接口 py3的urllib get请求 post请求,和get不同的是,先把post请求数据和请求封装到request对象,再…...
MVC、MVP 和 MVVM 架构总结
MVC、MVP 和 MVVM 是常见的软件架构模式,主要用于组织应用程序的结构,特别是在用户界面和业务逻辑之间进行分离。以下是对它们的详细解释,包括它们的差异、优缺点。 MVC(Model-View-Controller) 结构 Model…...
C++ vector的使用和简单模拟实现(超级详细!!!)
目录 前言 1.STL是什么 2.vector使用 2.1 vector简介 2.2 常用接口函数 1. 构造函数 2.operator[ ]和size,push_back 3. 用迭代器进行访问和修改 4. 范围for遍历 5.修改类型函数 pop_back find insert erase 6. 容量相关函数capacity resize reserve 3.…...
MySQL中,不能在一个DML(数据操纵语言,如INSERT, UPDATE, DELETE)语句中直接引用目标表进行子查询
错误示例 <delete id"deleteOldRelations">DELETE FROM departments_closure_tableWHERE descendant IN ( SELECT descendant FROM departments_closure_tableWHERE ancestor #{departmentId})</delete>程序运行之后,会报错:You …...
【CH32V305FBP6】4. systick 配置
配置 main.c void SYSTICK_Init_Config(u_int64_t ticks) {SysTick->SR & ~(1 << 0);//clear State flagSysTick->CMP ticks - 1;SysTick->CNT 0;SysTick->CTLR 0xF;NVIC_SetPriority(SysTicK_IRQn, 15);NVIC_EnableIRQ(SysTicK_IRQn); }中断计数 …...
【PECL】在扩展中实现 autoload
【PECL】在扩展中实现 autoload 摘要PHP代码想这么写C 代码这么实现 摘要 php-8.3.x 用扩展写个框架。想实现类管理器,自动加载,上代码: PHP代码想这么写 $ws new \Ziima\Applet(); $ws->import(Ziima, ../base/core); $ws->runAu…...
企业微信H5授权登录
在企业中如果需要在打开的网页里面携带用户的身份信息,第一步需要获取code参数 如何实现企业微信H5获取当前用户信息即accessToken? 1.在应用管理--》创建应用 2.创建好应用,点击应用主页-》设置-》网页-》将授权链接填上去 官方文档可以看…...
玩机进阶教程------修改gpt.bin分区表地址段 完全屏蔽系统更新 fast刷写分区表 操作步骤解析【二】
上期博文简单说明了分区表的基本常识。我们在有些环境中需要屏蔽手机的系统更新选项。除了以前博文中说明的修改系统更新下载文件夹的方法。还可以通过修改分区表类达到目的。在一些辅助维修工具上面带修改分区表功能。修改后效果为屏蔽系统更新和可以恢复出厂。原则上不深刷都…...
Java实现数据结构---数组
文章目录 概念存储原理数组的操作完整代码 概念 数组是(Array)是有限个相同类型的变量所组成的有序集合,数组中的每一个变量为称为元素。数组是最简单、最常用的数据结构。 数组下标从零开始。 存储原理 数组用一组连续的内存空间来存储一…...
java解析excel文件,返回json
我这里用的是springboot项目,配合Maven使用的。首先需要引入依赖: <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.2</version></dependency><dependency…...
uniapp 添加字体ttf
效果图如下 一、逻辑概述 在uniapp中使用字体,一共分成两种情况,一种是普通vue页面,一种是nvue页面引入字体。。 1.vue页面引入字体需要如下步骤 1. 先选择下载一种字体:字体格式一般为 ttf后缀名 黄凯桦律师手写体免费下载和在线…...
Linux入门攻坚——24、BIND编译安装、Telnet和OpenSSH
BIND编译安装 对于没有rpm包,需要源代码编译安装。 1、下载源代码:bind-9.12.2-P1.tar.gz,解压:tar -xf bind-9.12.2-P1.tar.gz 2、完善环境: 1)增加用户组named:groupadd -g 53 named 2&…...
1.5.3 基于Java配置方式使用Spring MVC
本实战教程主要介绍了如何使用Java配置方式来使用Spring MVC框架。相较于XML配置方式,Java配置方式提供了一种更为简洁和灵活的配置方法。 项目创建与配置 创建一个Jakarta EE项目,并设置项目名称和位置。选择Jakarta EE 10版本,不添加依赖&a…...
Artifactory清理二进制文件丢失的制品
一、摘要 当制品上传到 Artifactory 时,Artifactory 会在数据库中记录制品的相关元数据信息,包括文件路径、大小、校验和(如 MD5、SHA1)、上传时间、索引、依赖等。实际的制品二进制文件会存储在指定的存储后端,具体的…...
C#中的数组探索
在C#编程语言中,数组是一种基本的数据结构,用于存储固定大小的同类型元素序列。本文将深入探讨C#数组的各个方面,包括定义、赋值、范围操作、切片、多维数组(矩形与锯齿形)、简化初始化表达式以及边界检查。 数组定义…...
身份认证与口令攻击
身份认证与口令攻击 身份认证身份认证的五种方式口令认证静态口令动态口令(一次性口令)动态口令分类 密码学认证一次性口令认证S/KEY协议改进的S/KEY协议 其于共享密钥的认证 口令行为规律和口令猜测口令规律口令猜测 口令破解操作系统口令破解Windows密码存储机制Windows密码破…...
卷积网络迁移学习:实现思想与TensorFlow实践
摘要:迁移学习是一种利用已有知识来改善新任务学习性能的方法。 在深度学习中,迁移学习通过迁移卷积网络(CNN)的预训练权重,实现了在新领域或任务上的高效学习。 下面我将详细介绍迁移学习的概念、实现思想,…...
Ansible04-Ansible Vars变量详解
目录 写在前面6 Ansible Vars 变量6.1 playbook中的变量6.1.1 playbook中定义变量的格式6.1.2 举例6.1.3 小tip 6.2 共有变量6.2.1 变量文件6.2.1.1 变量文件编写6.2.1.2 playbook编写6.2.1.3 运行测试 6.2.2 根据主机组使用变量6.2.2.1 groups_vars编写6.2.2.2 playbook编写6.…...
Flutter 中的 SliverCrossAxisGroup 小部件:全面指南
Flutter 中的 SliverCrossAxisGroup 小部件:全面指南 Flutter 是一个功能丰富的 UI 开发框架,它允许开发者使用 Dart 语言来构建高性能、美观的移动、Web 和桌面应用。在 Flutter 的丰富组件库中,SliverCrossAxisGroup 是一个较少被使用的组…...
开源还是闭源这是一个问题
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...
数据结构与算法笔记:基础篇 - 栈:如何实现浏览器的前进和后退功能?
概述 浏览器的前进、后退功能,你肯定很熟悉吧? 当依次访问完一串页面 a-b-c 之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面 b 和 a。当后退到页面 a,点击前进按钮,就可以重新查看页面 b 和 c。但…...
【AIGC】大型语言模型在人工智能规划领域模型生成中的探索
大型语言模型在人工智能规划领域模型生成中的新应用 一、引言二、LLM在规划领域模型生成中的潜力三、实证分析:LLM在规划领域模型生成中的表现四、代码实例:LLM在规划领域模型生成中的应用五、结论与展望 一、引言 随着人工智能技术的迅猛发展࿰…...
从零开始学习Slam-旋转矩阵旋转向量四元组(二)
本文参考:计算机视觉life 仅作笔记用 书接上回,上回不清不楚的介绍了旋转矩阵&旋转向量和四元组 现在回顾一下重点: 本着绕谁谁不变的变则 假设绕z轴旋转θ,旋转矩阵为: 再回顾一下旋转向量的表示以及这个基本记不…...