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

分治与递归

实验一:分治与递归

【实验目的】

深入理解分治法的算法思想,应用分治法解决实际的算法问题。

【实验性质】

验证性实验(学时数:2H)

【实验内容与要求】

1、设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴每个选手必须与其他n-1个选手各赛一次;⑵每个选手一天只能赛一次;⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计成有n行和n列的一个表。表中第一列是选手编号,表中第i行和第j列(j>1)处填入第i个选手在第j天所遇到的选手。例如8个选手的日程表安排如右图所示。

要求:请设计算法,并采用C或C++语言编写程序实现上述功能,调试运行并对算法的时间复杂度进行分析。

【算法思想及处理过程】

首先,通过输入参赛人数n,判断n是否合法(是否为2的幂次方),如果不合法则输出错误信息。

然后,输入第一个选手的编号k。

调用roundrob函数,传入参数k和n。roundrob函数的作用是生成对阵表。

首先,判断n是否为2,如果是,则直接生成对阵表。对阵表是一个二维数组a,每个元素表示某个选手与另一个选手的对阵情况。

如果n不是2,递归调用roundrob函数,将n除以2传入,并分成两个子问题,分别解决。

递归结束后,对阵表的前一半行和后一半行进行交换,生成完整的对阵表。

最后,遍历对阵表,并输出每个元素的值。

在主函数中,先判断n是否合法,如果合法则调用roundrob函数生成对阵表,并输出。

如果n不合法,则直接返回。

【程序代码】

#include <stdio.h>

#include<iostream>

using namespace std;

int a[100][100]{};

void roundrob(int k, int n)

{

  

    if (n == 2)

    {

        a[k][0] = k + 1;

        a[k][1] = k + 2;

        a[k + 1][0] = k + 2;

        a[k + 1][1] = k + 1;

    }

    else

    {

        roundrob(k,n / 2);

        roundrob(k + n / 2,n / 2);

    }

    for (int i = k; i < k + n / 2; i++)

    {

        for (int j = n / 2; j < n; j++)

        {

            a[i][j] = a[i + n / 2][j - n / 2];

        }

    }

    for (int i = k + n / 2; i < k + n; i++)

    {

        for (int j = n / 2; j < n; j++)

        {

            a[i][j] = a[i - n / 2][j - n / 2];

        }

    }

}

int determine(int n)

{

    if (n % 2 == 0)

    {

        if (n / 2 == 1) return 1;

        determine(n / 2);

    }

    else

    {

        cout << "输入人数不合法" << endl;

        return 0;

    }

}

int main()

{

    int n;

    int k;

    cout << "请输入参赛人数" << endl;

    cin >> n;

    if (determine(n) == 1)

    {

        cout << "请输入第一个选手编号" << endl;

        cin >> k;

        k = k - 1;

        roundrob(k, n);

        int i = 0, j = 0;

        for (i = 0; i < n; i++)

        {

            for (j = 0; j < n; j++)

            {

                cout << a[i][j] << " ";

            }

            cout << endl;

        }

    }

    if (determine(n) == 0)

    {

        return 0;

    }

}

【运行结果】

程序运行结果截图。

【算法分析】

代码的时间复杂度为O(n^2),其中n为参赛人数。代码中使用递归的方式生成了一个二维数组a,数组的大小为n×n。在生成数组a的过程中,有两个嵌套的循环,每个循环的次数都是n/2,因此循环次数总共为n/2 × n/2 = n^2/4,所以时间复杂度为O(n^2)。另外,代码中还有一个determine函数,该函数的时间复杂度为O(logn),因为每次递归都将n除以2,直到n为偶数。

相关文章:

分治与递归

实验一&#xff1a;分治与递归 【实验目的】 深入理解分治法的算法思想&#xff0c;应用分治法解决实际的算法问题。 【实验性质】 验证性实验&#xff08;学时数&#xff1a;2H&#xff09; 【实验内容与要求】 1、设有n2k个运动员要进行网球循环赛。现要设计一个满足以…...

Spring中IOC容器

IoC IOC容器 IoC是一种设计思想&#xff0c;面向对象编程 Spring通过IoC管理所有Java对象的实例化和初始化&#xff0c;控制对象之间依赖关系 将IoC容器管理的Java对象称为Spring Bean&#xff0c;与new创建的对象没有区别 控制反转&#xff08;IoC Inversion of Controle&a…...

php redis分布式锁

一&#xff0c;概念 在PHP中实现分布式锁通常可以使用数据库、缓存系统&#xff08;如Redis&#xff09;或者其他中央存储系统来保证在分布式系统中的数据一致性与同步。秒杀下单、抢红包等等业务场景&#xff0c;都需要用到分布式锁。 常规方案大概有七中 方案一&#xff1a;…...

kotlin 中的布尔

1、kotlin中内置的Boolean类型&#xff0c;可以有true与false两个值的布尔对象。 布尔值的内置运算有&#xff08;跟很多语言如java、js一摸一样&#xff09;&#xff1a; ||——逻辑或&&——逻辑与!——逻辑非 fun main() {val a: Boolean trueval b: Boolean fa…...

有哪些ai聊天推荐?简单分享三款

有哪些ai聊天推荐&#xff1f;在当今数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;聊天软件已经成为我们日常生活中不可或缺的一部分。无论是与朋友、家人还是同事交流&#xff0c;这些智能聊天软件都能为我们提供极大的便利。那么&#xff0c;市面上有哪些值得推…...

Python第二语言(十、Python面向对象(上))

目录 1. 标记变量的基础类型 2. 初识对象 2.1 使用对象组织数据 3. 成员变量 3.1 类和类成员的定义 3.2 成员变量和成员方法使用 3.3 成员方法的定义语句 4. 类和对象class Clock: def ring(self): 4.1 创建类对象的语法&#xff1a;对象名 类名称() 4.2 用生活中的…...

SolidWorks 2016 SP5安装教程

软件介绍 Solidworks软件功能强大&#xff0c;组件繁多。 Solidworks有功能强大、易学易用和技术创新三大特点&#xff0c;这使得SolidWorks 成为领先的、主流的三维CAD解决方案。 SolidWorks 能够提供不同的设计方案、减少设计过程中的错误以及提高产品质量。SolidWorks 不仅…...

为什么高考志愿只选计算机专业?

刚刚高考结束&#xff0c;不知道各位学弟学妹考的怎么样啊&#xff1f; 高考毕竟是对十二年寒窗苦读的评判&#xff0c;也是很多人改变命运的机会。很多同学每天等待出分的过程很煎熬&#xff0c;既吃不好也玩不好&#xff08;os&#xff1a;这种同学还挺多的&#xff09;。 但…...

GPT大模型微调-提高垂直领域回答质量

微调一个大模型并测试微调后的效果是一个很好的学习实践。下面是一个逐步指导,帮助你使用一个较小的预训练大模型进行微调,并测试其效果。我们将使用 Hugging Face 的 Transformers 库和一个较小的预训练模型,如 DistilBERT。这个库非常流行且易于使用。 实现步骤 步骤 1:…...

全网首发-Docker被封后的代理设置教程

最近上交、科大以及阿里的一些docker镜像&#xff0c;好像都因为不可控力导致无法访问。 所以&#xff0c;之前好多正常的一些镜像的打包都会报错&#xff1a; 比如&#xff1a; #1 [internall load build definition from Dockerfile#1transferring dockerfile:972B done#1 D…...

代码随想录算法训练营第五十七天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列

代码随想录算法训练营第五十七天 1143.最长公共子序列 题目链接&#xff1a;1143.最长公共子序列 确定dp数组以及下标的含义&#xff1a;dp[i][j] &#xff1a;以下标i - 1为结尾的text1&#xff0c;和以下标j - 1为结尾的text2&#xff0c;最长重复子数组长度为dp[i][j]确…...

RocketMQ事务性消息

RocketMQ事务性消息是一定能保证消息发送成功的 事务消息发送步骤&#xff1a; &#xff08;1&#xff09;发送方将半事务消息发送至RocketMQ服务端。 &#xff08;2&#xff09;RocketMQ服务端将消息持久化之后&#xff0c;向发送方返回ack确认消息已经发送成功。由于消息为…...

mysql (事物)

一.什么是事物 事物是一组操作的集合&#xff0c;不可分割的工作单位&#xff0c;事物会把所有的操作当作一个整体一起向系统提交或撤销操作请求&#xff0c;就是这些操作要么一起成功要么一起失败。 二.事物操作 &#xff08;这个就是一个理解&#xff09; 1.事务特性 原子性…...

kotlin 中的字符串

一、字符类访问 1、字符串的访问跟js一样&#xff0c;可以使用索引来访问或者直接循环。 fun main() {val a: String "2024"// 方式一&#xff1a;for (item in a) {println(item) // 输出每一个字符}// 方式二&#xff1a;println("${a[0]}, ${a[1]}, ${a[2…...

网站线上模板建设的优缺点

优点&#xff1a; 1.搭建的时间短&#xff0c;在线建站&#xff0c;只需要登录注册然后选择网站模板创建网站即可管理自己的网站后台&#xff0c;就几步操作就可以实现。 2.网站出错率少&#xff0c;因为有很多用户在使用&#xff0c;前期所报出来的问题就已经一一…...

哲学家进餐问题

1.最多允许四个哲学家同时进餐&#xff0c;保证有一个筷子是空闲的&#xff0c;从而保证能有有一个哲学家成功进餐&#xff0c;而不导致死锁 semaphore chopstick[5] {1, 1, 1, 1, 1}, mutex4; Pi(){do{think...P(mutex);P(chopstick[i]);P(chopstick[(i1)%5);eat...V(mutex)…...

无人机遥感在农林信息提取中的实现方法与GIS融合应用

在新一轮互联网信息技术大发展的现今&#xff0c;无人机、大数据、人工智能、物联网等新兴技术在各行各业都处于大爆发的前夜。为了将人工智能方法引入农业生产领域。首先在种植、养护等生产作业环节&#xff0c;逐步摆脱人力依赖&#xff1b;在施肥灌溉环节构建智慧节能系统&a…...

联想测开一面(电话面试)笔试60%

联想测开一面&#xff08;电话面试&#xff09;笔试60% 3.21 无自我介绍 基本问项目&#xff0c;问实习 对python自动化测试了解多少 讲一下python中打包和解包的概念 学校无测试相关课程&#xff0c;平时用什么平台去学习的 计算机底层实现原理简要说说&#xff08;软硬结合&…...

【python】tkinter GUI开发: Button和Entry的应用实战探索

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

sm2证书生成(openssl3.0)

1、下载安装包 https://www.openssl.org/source/openssl-3.0.14.tar.gz 2、解压到指定位置 /appserver/openssl-3.0.14 3、安装依赖包 yum -y install gcc perl make zlib-devel perl-CPAN 4、编译 ./config shared --prefix/appserver/SM make depend make make install 5…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...