首页/新闻资讯/正文详情

PTA基础编程题目集 6-11 求自定类型元素序列的中位数(C语言实现)

发布时间:2026/9/27 15:58:47 来源:云帆数科 栏目:资讯中心
PTA基础编程题目集 6-11 求自定类型元素序列的中位数(C语言实现)
题目描述摘要本文介绍如何实现求自定义类型元素序列的中位数核心思路是先降序排序希尔排序再取下标 (N-1)/2 的元素时间复杂度约 O(N^1.3)空间 O(1)。文末附完整代码及测试用例。本题要求实现一个函数求 N 个集合元素 A[] 的中位数即序列中第 ⌊(N1)/2⌋ 大的元素。其中集合元素的类型为自定义的 ElementType。函数接口定义ElementType Median( ElementType A[], int N );其中给定集合元素存放在数组 A[] 中正整数 N 是数组元素个数。该函数须返回 N 个 A[] 元素的中位数其值也必须是 ElementType 类型。裁判测试程序样例#include stdio.h #define MAXN 10 typedef float ElementType; ElementType Median( ElementType A[], int N ); int main () { ElementType A[MAXN]; int N, i; scanf(%d, N); for ( i0; iN; i ) scanf(%f, A[i]); printf(%.2f\n, Median(A, N)); return 0; } /* 你的代码将被嵌在这里 */输入样例3 12.3 34 -5输出样例12.30函数部分实现/* 快速选择后返回中位数 */ElementTypeMedian(ElementType A[],intN){inti,j,gap;ElementType temp;/* 希尔排序降序时间复杂度约 O(N^1.3)可通过大 N 时限 */for(gapN/2;gap0;gap/2){/* 增量序列每次折半 */for(igap;iN;i){/* 从 gap 开始向后扫描 */tempA[i];/* 暂存当前元素 *//* 降序插入若前一个增量位置的元素更小则后移 */for(ji;jgapA[j-gap]temp;j-gap)A[j]A[j-gap];A[j]temp;/* 放入正确位置 */}}/* 降序排列后A[(N-1)/2] 恰好是第 ⌊(N1)/2⌋ 大的元素 */returnA[(N-1)/2];}下面是 Median 函数的算法流程图是是是否否否开始 Median(A, N)gap N / 2gap 0 ?i gapi N ?temp A[i]; j ij gap 且 A[j-gap] temp ?A[j] A[j-gap]; j - gapA[j] temp; igap / 2返回 A[(N-1)/2]结束代码部分实现/* 6-11 求自定类型元素序列的中位数 * 题目实现函数 Median(A[], N)返回 N 个元素的中位数。 * 实现原理先排序再取中间元素。 * 这里用希尔排序把数组降序排列 * 排序后中位数位于下标 (N-1)/2向下取整 * 对奇数/偶数长度都适用偶数时取中间偏左者。 * 时间复杂度 O(N^1.3)希尔空间复杂度 O(1)。 */#includestdio.h#defineMAXN10typedeffloatElementType;ElementTypeMedian(ElementType A[],intN);intmain(){ElementType A[MAXN];intN,i;scanf(%d,N);for(i0;iN;i)scanf(%f,A[i]);printf(%.2f\n,Median(A,N));return0;}/* 希尔排序降序后返回中位数 */ElementTypeMedian(ElementType A[],intN){inti,j,gap;ElementType temp;/* 希尔排序降序时间复杂度约 O(N^1.3)可通大 N 时限 */for(gapN/2;gap0;gap/2){/* 增量序列每次折半 */for(igap;iN;i){/* 从 gap 开始向后扫描 */tempA[i];/* 暂存当前元素 *//* 降序插入若前一个增量位置的元素更小则后移 */for(ji;jgapA[j-gap]temp;j-gap)A[j]A[j-gap];A[j]temp;/* 放入正确位置 */}}/* 降序排列后A[(N-1)/2] 恰好是第 ⌊(N1)/2⌋ 大的元素 */returnA[(N-1)/2];}

相关推荐

AGV小车驱动计算
AGV小车驱动计算

AGV驱动系统电机及减速机选型计算书1 编制目的 为保证AGV在额定载荷条件下能够满足启动、加速、匀速运行及爬坡等工况要求,对驱动系统进行理论计算,为驱动电机及减速机选型提供依据。 本计算依据车辆运动力学原理,综合考虑车辆滚动阻力、加速… · 2026/9/20 21:16:28

2026年元宇能量环开发全攻略:打造智能健康管理与轻养生新生态【行业深度解析】
2026年元宇能量环开发全攻略:打造智能健康管理与轻养生新生态【行业深度解析】

2026年元宇能量环开发全攻略:打造智能健康管理与轻养生新生态在2026年的数字化健康浪潮中,人们对身体状态的关注已从单纯的“治疗”转向了全方位的“预防与日常养护”。随着物联网与人工智能技术的深度融合,元宇能量环开发成为了大健康产业中… · 2026/9/21 11:59:17

Journal of Neurology:脑结构改变对纯遗传性痉挛性截瘫4型患者运动体征的影响
Journal of Neurology:脑结构改变对纯遗传性痉挛性截瘫4型患者运动体征的影响

本篇文献发表在Journal of Neurology杂志。所发布内容旨在与大家分享学术新知,促进交流学习,版权归原作者或原出处所有,感谢各位学者的辛勤付出与研究成果。1.引言遗传性痉挛性截瘫(HSP)指一组异质性神经退行性疾病&am… · 2026/7/27 14:33:26

南宁网站制作价格全解析:3个实战案例拆解报价单里的猫腻
南宁网站制作价格全解析:3个实战案例拆解报价单里的猫腻

南宁网站制作价格全解析:3个实战案例拆解报价单里的猫腻 很多老板在南宁找建站公司,第一反应不是问功能,而是问“多少钱”。但真正让人头大的是,报价单拿过来,域名、服务器、SSL证书这些名词堆在一起,完全搞不懂钱花哪儿了。… · 2026/9/27 15:58:43

VS Code + Remote SSH + Codex 故障排查笔记(Mac 版):TaoToken 统一 Key 配置与连接验证
VS Code + Remote SSH + Codex 故障排查笔记(Mac 版):TaoToken 统一 Key 配置与连接验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 15:58:43

别让AI代码变成技术债:用TaoToken统一Key管住Cline与CC Switch的配置骨架
别让AI代码变成技术债:用TaoToken统一Key管住Cline与CC Switch的配置骨架

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 15:58:37

Claude vs GPT怎么选?编程场景下实测对比与TaoToken统一接入配置
Claude vs GPT怎么选?编程场景下实测对比与TaoToken统一接入配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 15:58:19

公司建网站多少钱?5年对比评测揭秘域名服务器坑
公司建网站多少钱?5年对比评测揭秘域名服务器坑

公司建网站多少钱?5年对比评测揭秘域名服务器坑 很多老板问公司建网站多少钱,心里没底,其实最大的坑不在代码,而在 域名服务器搞不懂… · 2026/9/27 15:58:19

Claude Code + CC-Switch 一键安装与快速上手:TaoToken 统一 Key 配置实战
Claude Code + CC-Switch 一键安装与快速上手:TaoToken 统一 Key 配置实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 15:58:06

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码