GXUOJ-算法-第一次作业
1.整数划分
问题描述
GXUOJ | 整数划分

题解
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;int n;
int f[N];int main(){cin>>n;f[0]=1;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){f[j]=(f[j]+f[j-i])%mod;}}cout<<f[n];
}
2.汉诺塔
问题描述
GXUOJ | 汉诺塔

题解
#include<bits/stdc++.h>
using namespace std;
int n;void hnt(int n,char A,char B,char C){if(n==1) cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;else{hnt(n-1,A,C,B);cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;hnt(n-1,B,A,C);}
}int main(){cin>>n;hnt(n,'A','B','C');return 0;
}
3.算法训练 排列问题
问题描述
GXUOJ | 算法训练 排列问题

题解
#include <bits/stdc++.h>
using namespace std;// 定义全局变量n表示排列的元素个数,k表示要找的第k个排列
int n, k;
// 二维数组table用于存储限制条件,table[i][j]表示j - 1能否出现在i - 1后面
// 1标识 j-1可以出现在 i-1后面 0 标识不能
// 并保证第i行第i列为0
int table[20][20];
// 数组l用于存储当前生成的排列
int l[20];
// sum用于记录满足条件的排列的数量
int sum = 0;int main() {// 输入排列元素个数n和要找的第k个排列cin >> n >> k;// 读取限制条件表for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {// 输入table[i][j]的值,0表示不能,1表示能cin >> table[i][j];}}// 初始化排列为0到n - 1for (int i = 0; i < n; ++i) {l[i] = i;}// 使用do - while循环生成全排列并检查是否满足条件do {// flag用于标记当前排列是否满足限制条件bool flag = true;// 检查相邻元素是否满足限制条件for (int i = 0; i < n - 1; ++i) {// 如果当前相邻元素不满足限制条件(table值为0)if (!table[l[i]][l[i + 1]]) {// 将flag设为false,表示不满足条件flag = false;// 跳出内层循环,不再继续检查后续相邻元素break;}}// 如果当前排列满足限制条件if (flag) {// 满足条件的排列数量加1sum++;// 如果找到第k个满足条件的排列if (sum == k) {// 跳出外层循环break;}}} while (next_permutation(l, l + n)); //C++标准库中的一个循环结构,用于生成数组l所有元素的全排列 // 输出结果for (int i = 0; i < n; ++i) {// 输出排列中的元素cout << l[i];// 如果不是最后一个元素,则输出一个空格if (i < n - 1) {cout << ' ';}}return 0;
}
思路解析
-
布尔变量
flag的作用:flag就像是一个 “标记器”,初始化为true时,它假设当前生成的排列是满足所有限制条件的。在后续对排列的检查过程中,如果发现任何不符合限制条件的情况,就把flag设为false。这样,当整个检查过程结束后,通过查看flag的值,就能知道这个排列是否满足所有限制条件。
-
for循环遍历相邻元素对:for (int i = 0; i < n - 1; ++i)这个循环的目的是依次检查排列中每一对相邻的元素。因为要检查相邻元素关系,所以循环到n - 1即可,因为l[n - 1]没有下一个相邻元素可检查了。- 对于每一对相邻元素
(l[i], l[i + 1]),程序会去查看table[l[i]][l[i + 1]]的值。这里的table数组存储着限制条件,table[l[i]][l[i + 1]]表示l[i + 1]这个数能否出现在l[i]这个数后面。
-
判断与处理:
- 如果
table[l[i]][l[i + 1]]为0,这就表明在给定的限制条件下,l[i + 1]不允许出现在l[i]后面,也就意味着当前排列不满足限制条件。此时,将flag设为false,并使用break跳出内层for循环。因为只要发现一对不满足条件的相邻元素,就可以确定整个排列不满足条件了,无需再检查后面的相邻元素对。
- 如果
-
实例说明:
-
假设
n = 3,限制条件table如下:0 1 1 1 0 0 0 1 0并且当前生成的排列
l为[1, 0, 2]。 -
初始化
flag = true。 -
进入
for循环:- 当
i = 0时,相邻元素对是(l[0], l[1]),即(1, 0)。查看table[1][0](因为l[0]=1,l[1]=0),table[1][0] = 1,说明0可以出现在1后面,继续循环。 - 当
i = 1时,相邻元素对是(l[1], l[2]),即(0, 2)。查看table[0][2](因为l[1]=0,l[2]=2),table[0][2] = 1,说明2可以出现在0后面。
- 当
-
由于整个循环过程中没有出现
table[l[i]][l[i + 1]]为0的情况,所以flag仍然为true,这就表示排列[1, 0, 2]满足限制条件。 -
再假设当前生成的排列
l为[0, 2, 1]。 -
初始化
flag = true。 -
进入
for循环:- 当
i = 0时,相邻元素对是(l[0], l[1]),即(0, 2)。查看table[0][2],table[0][2] = 1,继续循环。 - 当
i = 1时,相邻元素对是(l[1], l[2]),即(2, 1)。查看table[2][1],table[2][1] = 0,这表明1不允许出现在2后面,所以将flag设为false并跳出循环。此时就确定排列[0, 2, 1]不满足限制条件。
- 当
-
通过这种方式,程序可以逐个检查生成的排列是否符合给定的限制条件。
4.数塔问题
问题描述
GXUOJ | 数塔问题

题解
#include <bits/stdc++.h>
using namespace std;const int MAX_N = 101;int main() {int n;cin >> n; // 读取数塔层数int f[MAX_N][MAX_N]; // 存储数塔的值int a[MAX_N][MAX_N]; // 存储到每个点的最大路径和// 读取数塔的每一层的数字for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {cin >> a[i][j];}}// 初始化最后一层的最大路径和for (int i = 0; i < n; i++) {f[n - 1][i] = a[n - 1][i];}// 从下到上计算每一层的最大路径和for (int i = n - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];}}// 输出从顶部到底部的最大路径和cout << f[0][0] << endl;return 0;
}
相关文章:
GXUOJ-算法-第一次作业
1.整数划分 问题描述 GXUOJ | 整数划分 题解 #include<bits/stdc.h> using namespace std; const int N1010,mod1e97;int n; int f[N];int main(){cin>>n;f[0]1;for(int i1;i<n;i){for(int ji;j<n;j){f[j](f[j]f[j-i])%mod;}}cout<<f[n]; } 2.汉诺塔…...
Springboot项目Druid运行时动态连接多数据源的功能
项目支持多数据库连接是个很常见的需求,这不仅是要在编译前连已经知道的多个数据库,有时还要在程序运行时连后期增加的多个数据源来获得数据。 一、编译前注册数据库连接 1.引入依赖包 <!-- springboot 3.x --><dependency><groupId&g…...
字符串匹配——KMP算法
前言 刷到字符串匹配的力扣题了【28. 实现 strStr() 】,这题简单吧用库函数做就可以,说难吧,就得引出大名鼎鼎的线性匹配算法——KMP。 目录 KMP 算法背景与原理算法优势 前缀表1. 构建Next数组2. 搜索匹配 KMP 算法背景与原理 KMP&#x…...
Qt开发技术【下拉复选框 MultiSelectComboBox 自定义全选项】
继承ComboBox完成下拉复选框 自定义全选项 效果图 整个控件继承于QCombobox类。主要修改QLineEdit、QListWidget这两部分,QComboBox提供如下接口,可以将这两部分设置为新建的QLineEdit、QListWidget对象 CMultiSelectComboBox::CMultiSelectComboBo…...
20_HTML5 SSE --[HTML5 API 学习之旅]
HTML5 Server-Sent Events (SSE) 是一种技术,它允许服务器向浏览器推送更新。与传统的轮询不同,SSE提供了真正的单向实时通信通道:服务器可以主动发送数据到客户端,而不需要客户端发起请求。这对于实现实时更新的应用非常有用&…...
jetson Orin nx + yolov8 TensorRT 加速量化 环境配置
参考【Jetson】Jetson Orin NX纯系统配置环境-CSDN博客 一 系统环境配置: 1.更换源: sudo vi /etc/apt/sources.list.d/nvidia-l4t-apt-source.list2.更新源: sudo apt upgradesudo apt updatesudo apt dist-upgrade sudo apt-get updat…...
Android Studio IDE环境配置
需要安装哪些东西: Java jdk Java Downloads | OracleAndroid Studio 下载 Android Studio 和应用工具 - Android 开发者 | Android DevelopersAndroid Sdk 现在的Android Studio版本安装时会自动安装,需要注意下安装的路径Android Studio插件…...
PTA 7-2 0/1背包问题(回溯法) 作者 王东 单位 贵州师范学院
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求重量和恰好为W具有最大的价值。 输入格式: 第一行输入背包载重量W及背包个数n,再依次输入n行,每行为背包重量wi和价值vi。 输出格式: 第一行输出装入背包内…...
Matlab环形柱状图
数据准备: 名称 数值 Aa 21 Bb 23 Cc 35 Dd 47 保存为Excel文件后: % Load data from Excel file filename data.xlsx; % Ensure the file is in the current folder or provide full path dataTable readtable(filena…...
【AI大模型】探索GPT模型的奥秘:引领自然语言处理的新纪元
目录 🍔 GPT介绍 🍔 GPT的架构 🍔 GPT训练过程 3.1 无监督的预训练语言模型 3.2 有监督的下游任务fine-tunning 🍔 小结 学习目标 了解什么是GPT.掌握GPT的架构.掌握GPT的预训练任务. 🍔 GPT介绍 GPT是OpenAI公…...
5.Python爬虫相关
爬虫 爬虫原理 爬虫,又称网络爬虫,是一种自动获取网页内容的程序。它模拟人类浏览网页的行为,发送HTTP请求,获取网页源代码,再通过解析、提取等技术手段,获取所需数据。 HTTP请求与响应过程 爬虫首先向…...
Windows系统上配置eNSP环境的详细步骤
华为eNSP(Enterprise Network Simulation Platform)是一款针对华为数通网络设备的网络仿真平台,用于辅助工程师进行网络技术学习、方案验证和故障排查等工作。以下是在Windows系统上配置eNSP环境的详细步骤: 1. 准备工作 下载安…...
Database.NET——一款轻量级多数据库客户端工具
文章目录 Database.NET简介下载使用使用场景总结 Database.NET简介 Database.NET 是一个功能强大且易于使用的数据库管理工具,适用于多种数据库系统。它为开发者和数据库管理员提供了一个统一的界面,可以方便地管理和操作不同类型的数据库。 支持的数据…...
新浪微博C++面试题及参考答案
多态是什么?请详细解释其实现原理,例如通过虚函数表实现。 多态是面向对象编程中的一个重要概念,它允许不同的对象对同一消息或函数调用做出不同的响应,使得程序具有更好的可扩展性和灵活性。 在 C 中,多态主要通过虚函…...
计算机视觉目标检测-1
文章目录 摘要Abstract1.目标检测任务描述1.1 目标检测分类算法1.2 目标定位的简单实现思路1.2.1 回归位置 2.R-CNN2.1 目标检测-Overfeat模型2.1.1 滑动窗口 2.2 目标检测-RCNN模型2.2.1 非极大抑制(NMS) 2.3 目标检测评价指标 3.SPPNet3.1 spatial pyr…...
【物联网技术与应用】实验15:电位器传感器实验
实验15 电位器传感器实验 【实验介绍】 电位器可以帮助控制Arduino板上的LED闪烁的时间间隔。 【实验组件】 ● Arduino Uno主板* 1 ● 电位器模块* 1 ● USB电缆*1 ● 面包板* 1 ● 9V方型电池* 1 ● 跳线若干 【实验原理】 模拟电位器是模拟电子元件,模…...
java常用类(上)
笔上得来终觉浅,绝知此事要躬行 🔥 个人主页:星云爱编程 🔥 所属专栏:javase 🌷追光的人,终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 一、包装类 1.1包装类…...
包管理工具npm、yarn、pnpm、cnpm详解
1. 包管理工具 1.1 npm # 安装 $ node 自带 npm# 基本用法 npm install package # 安装包 npm install # 安装所有依赖 npm install -g package # 全局安装 npm uninstall package # 卸载包 npm update package # 更新包 npm run script #…...
CI/CD是什么?
CI/CD 定义 CI/CD 代表持续集成和持续部署(或持续交付)。它是一套实践和工具,旨在通过自动化构建、测试和部署来改进软件开发流程,使您能够更快、更可靠地交付代码更改。 持续集成 (CI):在共享存储库中自动构建、测试…...
[Java]合理封装第三方工具包(附视频)
-1.视频链接 视频版: 视频版会对本文章内容进行详细解释 [Java]合理封装第三方工具包_哔哩哔哩_bilibili 0.核心思想 对第三方工具方法进行封装,使其本地化,降低记忆和使用成本 1.背景 在我们的项目中,通常会引用一些第三方工具包,或者是使用jdk自带的一些工具类 例如: c…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
