基于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. 远…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
