基于C++实现循环赛日程表(分治算法)
一、问题描叙
设有n=2^k个运动员,要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表
- 每个选手必须与其他n-1个选手各赛一场
- 每个选手一天只能赛一次
- 循环赛一共进行n-1天
二、问题分析
按此要求可将比赛日程表设计成n行n-1列的表,在表中第 i 行和第j 列处填入第 i 个选手在第 j 天所遇到的对手。
例如,当选手的人数为8人时,其比赛日程表如下图

算法分析:
按分治策略,我们可以将所有的选手分为两半,则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分,直到只剩下两个选手时,比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。如上图,所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此,将左上角小块中的所有数字按其相对位置抄到右下角,又将左下角小块中的所有数字按其相对位置抄到右上角,这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
算法实现步骤:
(1)当k=1时,即人数为2人,此情况为最简单的情况
此表为:

(2)当k=2时,人数为4人,循环表为

(3)当k=3时,人数为8人,此时循环表为

以此类推,我们不难发现,我们可以用分治的方法实现,现自顶向下分解,直到分解到最简单的情况,即人数为2人,这时就可以两两比赛,表的填充为对角填充的方式,然后再自底向上填充表格,具体的看上面的k=1,k=2,k=3时形成的循环表就很好理解了。
三、代码示例
#include<stdio.h>
#include<math.h>
#define N 50
void GameTable(int k,int array[][N]);
void print(int k,int array[][N]); //输出二维数组
main()
{int k;int array[N][N];printf("\t\t****************************************\n");printf("\t\t**\t\t循环赛日程表 **\n");printf("\t\t****************************************\n\n");printf("设参赛选手的人数为n(n=2^k),请输入k 的值:");do{scanf("%d",&k);if(k!=0){GameTable(k,array);print(k,array);}elseprintf("您输入的数据有误,请重新输入");}while(k!=0);}
void GameTable(int k,int array[][N])//数组下标从1开始
{int i,j,s,t;int n=1;for(i=1;i<=k;i++)n*=2; //求总人数for(i=1;i<=n;i++)array[1][i]=i; //第一行排1-8int m=1; //用来控制每一次填表时i行j列的起始填充位置for(s=1;s<=k;s++) //s指对称赋值的总循环次数,即分成几大步进行制作日程表{n=n/2;for(t=1;t<=n;t++) //t指明内部对称赋值的循环次数for(i=m+1;i<=2*m;i++)for(j=m+1;j<=2*m;j++){array[i][j+(t-1)*m*2]=array[i-m][j+(t-1)*m*2-m]; //右上角等于左上角的值array[i][j+(t-1)*m*2-m]=array[i-m][j+(t-1)*m*2]; //左下角等于右上角的值}m*=2;}}
void print(int k,int array[][N])
{int i,j;int num=pow(2,k);printf("%d人的循环赛日程表如下\n",num);for(i=1;i<=num;i++) //输出二维数组{for(j=1;j<=num;j++){printf("%d\t",array[i][j]);}printf("\n");}
}
四、程序结果展示

相关文章:
基于C++实现循环赛日程表(分治算法)
一、问题描叙 设有n2^k个运动员,要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表 每个选手必须与其他n-1个选手各赛一场每个选手一天只能赛一次循环赛一共进行n-1天 二、问题分析 按此要求可将比赛日程表设计成n行n-1列的表,在表中第 i 行…...
基于uni-app的汽车租赁app的设计与实现
1.项目背景及意义 项目背景: 随着人们生活水平的提高,汽车租赁服务在城市中变得越来越普及。传统的租车方式存在一些问题,比如租车流程繁琐、费用不透明、选择有限等。因此,开发一款基于uni-app的汽车租赁app成为了满足用户需求…...
3.8-镜像的发布
如果我们想将image push到docker hub里面,那么我们的image的名字一定要是这种格式:docker hub id/imageName,例如:lvdapiaoliang/hello-docker docker hub个人账户设置地址: 在push之前要先登录: docker l…...
Navicat 基于 GaussDB 主备版的快速入门
Navicat Premium(16.2.8 Windows版或以上) 已支持对GaussDB 主备版的管理和开发功能。它不仅具备轻松、便捷的可视化数据查看和编辑功能,还提供强大的高阶功能(如模型、结构同步、协同合作、数据迁移等),这…...
String的字符串拼接
java中 String a “123” “234”; String b “123”; String c b “234”; 其中a和c的区别是什么? a c 为什么为false 在Java中,字符串的处理特别是涉及到字符串常量和字符串变量的连接时,会涉及到字符串池(String Pool&a…...
反渗透水处理成套设备有哪些
反渗透水处理成套设备主要包括反渗透装置、预处理系统、控制系统等部分。 反渗透装置:反渗透水处理设备的核心部分,由反渗透膜、压力容器、膜组件等组成。反渗透膜是一种高分子材料制成的半透膜,能够截留水中的溶解盐、有机物、细菌等杂质&a…...
DPC15 国产带有 SPI 接口的独立 CAN 控制器兼容替代MCP2551
DPC15是一款独立控制器局域网络(Controller Area Network,CAN)协议控制器,完全支持CAN V2.0B技术规范。该器件能发送和接收标准和扩展数据帧以及远程帧。 DPC15自带的两个验收屏蔽寄存器和六个验收滤波寄存器可以过滤掉不想要的报…...
【ELK01】ELK简介以及ElasticSearch安装、ES客户端工具-Head安装、报错问题整理
有一段时间没有更新这个专栏了,最近在用ELK相关的技术,今天开始写一下ELK的系列的内容,与大家共同学习 一、什么是ELK ELK 是elastic公司提供的一套完整的日志收集以及展示的解决方案,是三个产品的首字母缩写,分别是ElasticSearch、Logstash 和 Kibana。 1. E-ELASTICS…...
根据音频绘制频谱
根据音频链接绘制频谱图 封装 // 可以这样使用 也可以 import { AudioContext } from standardized-audio-context; const getAudioContext window.AudioContext ||window.webkitAudioContext ||window.mozAudioContext ||window.msAudioContext;const clearArr []export c…...
SSL证书对网站SEO的好处
随着网络安全意识的提高,越来越多的网站开始采用SSL证书来保护自己的数据传输过程。那么,SSL证书真的能为网站SEO带来好处吗?下面将为您分析这个问题。 加强用户体验和信任度 SSL证书不仅能确保数据传输的安全性,还能让客户感受…...
YB506AB是一款理电池充、放电管理专用芯片,集成锂电池充电管理和降压DC-DC电路。
YB506AB 锂电转可充电AA/AAA电池专用SOC芯片 概述: YB506AB是一款理电池充、放电管理专用芯片,集成锂电池充电管理和降压DC-DC电路。充电过程满足锂电池三段式滑流/恒流/恒压充电规范,B506内部的线性充电电路采用了恒流可配置模式,可以通过…...
Linux | C语言中volatile关键字的理解
目录 前言 一、代码引入 二、现象解释 三、具体引用 前言 本章主要讲解介绍volatile关键的作用与使用场合;深刻理解volatile关键字;本文你需要有信号相关的基础知识; Linux | 信号-CSDN博客 一、代码引入 首先,我们来查看下面…...
汇编层面有三个主要的操作对象
1.为啥会有addi指令? 在汇编层面有三个主要的操作对象:寄存器,内存,立即数,它们是完全不同,不可以混淆,组织结构也不一样的不同对象,所以不能单纯拿针对寄存器的指令去处理内存和立…...
React中的Redux:简介和实例代码
React是一个流行的JavaScript库,用于构建用户界面。它提供了一种简单而强大的方式来构建交互式的界面。Redux是一个用于管理应用程序状态的JavaScript库。它可以与React一起使用,以帮助管理React应用程序的状态。 引言 在本文中,我们将介绍R…...
Modbus转Profinet网关在金银精炼控制系统中应用案例
金银精炼控制系统中采用Modbus转Profinet网关(XD-MDPN100)连接1200plc与PID控制阀门进行通讯,通过控制PID阀门的大小来实现温度的恒温控制。这一系统的好处在于它能够提高金银精炼过程的效率和精确度。PID控制阀门可以根据温度的变化实时调整…...
小程序商城免费搭建之java商城 电子商务Spring Cloud+Spring Boot+二次开发+mybatis+MQ+VR全景+b2b2c
1. 涉及平台 平台管理、商家端(PC端、手机端)、买家平台(H5/公众号、小程序、APP端(IOS/Android)、微服务平台(业务服务) 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…...
Rabin加解密算法(python3)
Rabin加解密算法 详细代码如下: # 空空 # dahouzi.cn import random from sympy import isprimedef decrypt_rabin(c, p, q):"""解密 Rabin 密文Args:c (int): 密文p (int): 素数 pq (int): 素数 qReturns:tuple: 解密结果 M1, M2, M3, M4"&q…...
【带头学C++】----- 七、链表 ---- 7.5 学生管理系统(链表--上)
目录 1.main函数设计 2.定义Node节点类型 3.链表插入结点 在main函数中调用插入函数、打印函数 插入结点函数实现(头插法) 插入结点函数实现(尾插法) 遍历链表函数实现 4.演示插入、遍历结果 目录 1.main函数设计 2.定义…...
(四)什么是Vite——冷启动时vite做了什么(源码、middlewares)
vite分享ppt,感兴趣的可以下载: Vite分享、原理介绍ppt 什么是vite系列目录: (一)什么是Vite——vite介绍与使用-CSDN博客 (二)什么是Vite——Vite 和 Webpack 区别࿰…...
Docker部署MinIO对象存储服务器结合Cpolar实现远程访问
🔥博客主页: 小羊失眠啦. 🎥系列专栏:《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
