算法课习题汇总(2)

整数划分问题

将正整数n表示成一系列正整数之和,n=n1+n2+…+nk(n1>=n2>=…>=nk,k>=1)。正整数n的这种表示称为正整数n的划分。

思路:

n表示待划分数,m表示最大减数。请添加图片描述

#include<iostream>
using namespace std;int q(int n, int m)
{if (m == 1)return 1;if (m > n)return q(n, n);if (n == m)return q(n, n-1) + 1;return q(n - m, m) + q(n, m-1);
}int main()
{int n = 0;cin >> n;cout << q(n, n) << endl;return 0;
}

在这里插入图片描述

Hanoi问题 T(n)=2^n-1

具体看:汉诺塔问题

#include<iostream>
using namespace std;void move(char A, char B)
{cout << A <<"->" << B << endl;
}void hanoi(int n, char A, char B, char C)
{if (n == 0)return;hanoi(n - 1, A, C, B);move(A, B);hanoi(n - 1, C, B, A);
}int main()
{int n = 0;cin >> n;hanoi(n,'A','B','C');return 0;
}

在这里插入图片描述

二分搜索 O(n)=nlogn

int Search(int* arr, int x, int n)
{int left = 0;int right = n;while (left <= right){int mid = left + (right - left) / 2;if (x == arr[mid])return mid;else if (x > arr[mid])left = mid + 1;elseright = mid - 1;}return -1;
}int main()
{int n = 0;cin >> n;int arr[1000];for (int i = 0; i < n; i++)cin >> arr[i];cout << Search(arr, 5, n - 1) << endl;return 0;
}

在这里插入图片描述

合并排序 O(n)=nlogn

#include<iostream>
using namespace std;void Merge(int* arr, int l, int r)
{if (l == r)return;int mid = l + (r - l) / 2;Merge(arr, l, mid);Merge(arr, mid + 1, r);int i = l, j = mid + 1, k = l;int arr2[10000] = {0};while (i <= mid && j <= r){if (arr[i] >= arr[j]){arr2[k++] = arr[j++];}else{arr2[k++] = arr[i++];}}while (i <= mid){arr2[k++] = arr[i++];}while (j <= r){arr2[k++] = arr[j++];}for (i = l; i <= r; i++){arr[i] = arr2[i];}
}int main()
{int n;cin >> n;int arr[10000];for (int i = 0; i < n; i++)cin >> arr[i];Merge(arr, 0, n - 1);for (int i = 0; i < n; i++)cout << arr[i]<<" ";cout << endl;return 0;
}

在这里插入图片描述

快速排序 O(n)=nlogn

#include<iostream>
using namespace std;void q(int* arr, int l, int r)
{if (l >= r)return;int mid=l+(r-l)/2;swap(arr[1], arr[mid]);int tmp = arr[1];int i = l, j = r;while (1){while (i < j && arr[j] >= tmp)j--;while (i < j && arr[i] <= tmp)i++;if (i >= j)break;swap(arr[i], arr[j]);}swap(arr[i],arr[1]);q(arr, l, i - 1);q(arr, i + 1, r);
}int main()
{int n;cin >> n;int arr[100];for (int i = 0; i < n; i++)cin >> arr[i];q(arr, 0, n - 1);for (int i = 0; i < n; i++)cout << arr[i]<<" ";cout << endl;return 0;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428543.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

面试题给图例举测试用例或测试点

目录 从功能测试的角度考虑&#xff1a; 从性能角度考虑&#xff1a; 从兼容性的角度考虑&#xff1a; 从自动化角度考虑&#xff1a; 从安全性角度考虑&#xff1a; 用户体验的角度测试&#xff1a; 面试通常会有技术和人事两种&#xff0c;侧重点不一样。 今天聊一下测…

Qt日志输出及QsLog日志库

目录 Qt日志输出及QsLog日志库日志输出格式化日志普通格式化条件格式化环境变量设置格式化日志输出位置日志输出对象信息禁用输出 QsLog日志库使用方法1. 将QsLog目录添加到项目中2. 配置CMakeLists.txt文件3. 配置.pro文件4. 日志记录器的配置5. 运行程序6. 启用行号和文件名C…

有奖直播 | onsemi IPM 助力汽车电气革命及电子化时代冷热管理

在全球汽车行业向电气化和智能化转型的浪潮中&#xff0c;功率管理技术的创新和应用成为了关键驱动力。作为全球领先的半导体解决方案供应商&#xff0c;onsemi&#xff08;安森美&#xff09;致力于通过其先进的智能功率模块&#xff08;IPM&#xff09;技术&#xff0c;推动汽…

[Linux#55][网络协议] 序列化与反序列化 | TcpCalculate为例

目录 1. 理解协议 1.1 结构化数据的传输 序列化与反序列化 代码感知&#xff1a; Request 类 1. 构造函数 2. 序列化函数&#xff1a;Serialize() 3. 反序列化函数&#xff1a;DeSerialize() 补充 4. 成员变量 Response 类 1. 构造函数 2. 序列化函数&#xff1a;…

JavaWeb - 5 - 前端工程化

一.前后端分离开发 前后端混合开发 缺点&#xff1a;沟通成本高&#xff0c;分工不明确&#xff0c;不便管理&#xff0c;不便维护拓展 前后端分离开发 当前最为主流的开发模式&#xff1a;前后端分离 前后端分离开发中很重要的是API接口文档&#xff08;如&#xff1a;YApi&…

胤娲科技:谷歌DeepMind祭出蛋白质设计新AI——癌症治疗迎来曙光

在科技的浩瀚星空中&#xff0c;DeepMind的“阿尔法”家族总是能带来令人瞩目的璀璨光芒。这一次&#xff0c;它们再次以惊人的姿态&#xff0c; 将AI的触角深入到了生命的微观世界——蛋白质设计领域&#xff0c;为我们描绘了一幅未来医疗的宏伟蓝图。 想象一下&#xff0c;一…

Scrapy爬虫实战——某瓣250

# 按照我个人的习惯&#xff0c;在一些需要较多的包作为基础支撑的项目里&#xff0c;习惯使用虚拟环境&#xff0c;因为这样能极大程度的减少出现依赖冲突的问题。依赖冲突就比如A、B、C三个库&#xff0c;A和B同时依赖于C&#xff0c;但是A需要的C库版本大于N&#xff0c;而B…

VUE3配置路由(超级详细)

第一步创建vue3的项目

多版本node管理工具nvm

什么是nvm&#xff1f; 在项目开发过程中&#xff0c;使用到vue框架技术&#xff0c;需要安装node下载项目依赖&#xff0c;但经常会遇到node版本不匹配而导致无法正常下载&#xff0c;重新安装node却又很麻烦。为解决以上问题&#xff0c;nvm&#xff1a;一款node的版本管理工…

微服务-- Sentinel的使用

目录 Sentinel&#xff1a;微服务的哨兵 生态系统景观 sentinel与spring cloud Hystrix 对比 Sentinel 主要分为两部分 Sentinel安装与使用 Sentinel的控制规则 流控规则 流控规则的属性说明 新增流控规则 关联流控模式 SentinelResource注解的使用 SentinelResou…

mysql-死锁

文章目录 1、概念1.1、创建表 account1.2、id 自动创建 主键索引 primary1.3、name 没有创建索引 2、产生死锁的必要条件2.1、此时 name 没有创建 索引 3、如何处理死锁3.1、方式1&#xff1a;等待&#xff0c;直到超时&#xff08;innodb_lock_wait_timeout50s&#xff09;3.2…

GRE隧道在实际部署中的优化、局限性与弊端

GRE的其他特性 上一篇光讲解配置就花了大量的篇幅&#xff0c;还一些特性没有讲解的&#xff0c;这里在来提及下。 1、动态路由协议 在上一篇中是使用的静态路由&#xff0c;那么在动态路由协议中应该怎么配置呢&#xff1f; undoip route-static 192.168.20.0 255.255.255.0 …

element-plus的菜单组件el-menu

菜单是几乎是每个管理系统的软件系统中不可或缺的&#xff0c;element-plus提供的菜单组件可以快速完成大部分的菜单的需求开发&#xff0c; 该组件内置和vue-router的集成&#xff0c;使用起来很方便。 主要组件如下 el-menu 顶级菜单组件 主要属性 mode:决定菜单的展示模式…

2024/9/20 使用QT实现扫雷游戏

有三种难度初级6x6 中级10x10 高级16x16 完成游戏 游戏失败后&#xff0c;无法再次完成游戏&#xff0c;只能重新开始一局 对Qpushbutton进行重写 mybutton.h #ifndef MYBUTTON_H #define MYBUTTON_H #include <QObject> #include <QWidget> #include <QPus…

2024年8月HarmonyOS鸿蒙应用开发者高级认证全新题库

有题库在手&#xff0c;一小时轻松拿下鸿蒙高级。你们需要也可以无偿分享哦&#xff01; 项目需要为不同的设备形态(如手机 、 智能手表)提供定制化构建 。请说明如何在 DevEcostudio 中 设置不同的构建配置&#xff0c; 以生成针对不同设备的 hap 包&#xff1a; 在模块级别 b…

JavaWeb的Filter详解

过滤器Filter 什么是Filter&#xff1f; 依据字面上的中文意思为过滤器。Filter的作用 当用户的请求到达指定的URL之前&#xff0c;可以借助Filter来改变这些请求的内容&#xff1b;同样地&#xff0c;当响应结果到达客户端之前&#xff0c;可以使用Filter修改输出的内容。什么…

【数据结构入门】排序算法之三路划分与非比较排序

文章目录 前言 一、三路划分优化 1.1. 基本思想 1.2. 实现步骤 1.3. 优点 1.4 代码实现 二、非比较排序 2.1 计数排序 2.1.1基本思想 2.1.2具体步骤 2.1.3算法特性 2.1.4算法实现 2.2 基数排序 2.2.1基本思想 2.2.2具体步骤 2.2.3 基数排序的方法 2.2.4算法特…

MongoDB在Linux系统中的安装与配置指南

在这篇文章中&#xff0c;我们将介绍如何在CentOS 7服务器上安装MongoDB&#xff0c;并通过DataX将数据从MongoDB迁移到MySQL数据库。这将包括MongoDB的安装、配置、数据准备以及使用DataX进行数据迁移的详细步骤。 MongoDB简介 MongoDB是一个高性能、开源、无模式的文档型数据…

Leetcode面试经典150题-97.交错字符串

给定三个字符串 s1、s2、s3&#xff0c;请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下&#xff0c;其中每个字符串都会被分割成若干 非空 子字符串 &#xff1a; s s1 s2 ... snt t1 t2 ... tm|n - m| < 1交错 是…

Springboot3 + MyBatis-Plus + MySql + Uniapp 实现商品规格选择sku(附带自设计数据库,最新保姆级教程)

Springboot3 MyBatis-Plus MySql Uniapp 实现商品规格选择sku&#xff08;附带自设计数据库&#xff0c;最新保姆级教程&#xff09; 1、效果展示2、数据库设计2.1 商品表2.2 商品价格和规格中间表2.3 商品规格表 3、后端代码3.1 model3.2 vo3.3 mapper、server、serverImp3…