当前位置: 首页 > 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…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...