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

如何在C语言中实现求解超级丑数

超级丑数是一个正整数,并且它的质因数只包含在给定的质数列表中。超级丑数的定义类似于丑数,但可以根据特定需求改变质因数的范围。下面是如何在C语言中实现求解超级丑数的代码。

我们使用最小堆(优先队列)来高效地生成超级丑数序列。优先队列可以帮助我们始终获得当前最小的超级丑数。

代码实现

#include <stdio.h>
#include <stdlib.h>#define MAX_HEAP_SIZE 10000typedef struct {int* data;int size;
} MinHeap;// 创建一个最小堆
MinHeap* createMinHeap() {MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));heap->data = (int*)malloc(MAX_HEAP_SIZE * sizeof(int));heap->size = 0;return heap;
}// 向堆中插入元素
void insertMinHeap(MinHeap* heap, int value) {if (heap->size >= MAX_HEAP_SIZE) {printf("Heap overflow!\n");return;}int i = heap->size++;while (i > 0 && heap->data[(i - 1) / 2] > value) {heap->data[i] = heap->data[(i - 1) / 2];i = (i - 1) / 2;}heap->data[i] = value;
}// 删除堆顶元素
int extractMin(MinHeap* heap) {if (heap->size <= 0) {printf("Heap underflow!\n");return -1;}int minValue = heap->data[0];heap->data[0] = heap->data[--heap->size];int i = 0;while (i * 2 + 1 < heap->size) {int j = i * 2 + 1;if (j + 1 < heap->size && heap->data[j + 1] < heap->data[j]) {j++;}if (heap->data[i] <= heap->data[j]) {break;}int temp = heap->data[i];heap->data[i] = heap->data[j];heap->data[j] = temp;i = j;}return minValue;
}// 检查堆中是否包含某个元素
int contains(MinHeap* heap, int value) {for (int i = 0; i < heap->size; i++) {if (heap->data[i] == value) {return 1;}}return 0;
}// 找到第n个超级丑数
int nthSuperUglyNumber(int n, int* primes, int primesSize) {MinHeap* heap = createMinHeap();insertMinHeap(heap, 1);int superUgly = 1;for (int i = 0; i < n; i++) {superUgly = extractMin(heap);for (int j = 0; j < primesSize; j++) {int newUgly = superUgly * primes[j];if (!contains(heap, newUgly)) {insertMinHeap(heap, newUgly);}}}free(heap->data);free(heap);return superUgly;
}int main() {int primes[] = {2, 3, 5};int primesSize = sizeof(primes) / sizeof(primes[0]);int n = 10; // 找到第10个超级丑数int result = nthSuperUglyNumber(n, primes, primesSize);printf("The %d-th super ugly number is: %d\n", n, result);return 0;
}

代码解释

  1. 堆数据结构

    • MinHeap结构体定义了最小堆的数据结构,包括一个动态数组和堆的大小。
    • createMinHeap函数创建并初始化最小堆。
    • insertMinHeap函数插入新元素到最小堆,同时维护堆的性质。
    • extractMin函数从最小堆中提取最小元素,并重新调整堆。
    • contains函数检查堆中是否包含某个元素,防止插入重复元素。
  2. 超级丑数计算

    • nthSuperUglyNumber函数接受要查找的超级丑数的位置n,质因数数组primes及其大小primesSize
    • 函数使用最小堆来依次生成超级丑数。每次从堆中取出最小的超级丑数,然后将其乘以所有质因数生成新的超级丑数并插入堆中。
    • 循环执行上述步骤直到找到第n个超级丑数。
  3. 主函数

    • main函数中定义了质因数数组primes,并调用nthSuperUglyNumber函数找到第n个超级丑数并输出结果。

通过这种方式,我们能够高效地找到指定位置的超级丑数。该算法利用最小堆的数据结构,确保每次都能获得当前最小的超级丑数,并避免生成重复的超级丑数。

相关文章:

如何在C语言中实现求解超级丑数

超级丑数是一个正整数&#xff0c;并且它的质因数只包含在给定的质数列表中。超级丑数的定义类似于丑数&#xff0c;但可以根据特定需求改变质因数的范围。下面是如何在C语言中实现求解超级丑数的代码。 我们使用最小堆&#xff08;优先队列&#xff09;来高效地生成超级丑数序…...

secExample靶场之java反序列化漏洞复现

我是使用kali虚拟机搭建的靶场&#xff0c;具体搭建步骤可以看我之前的博客内容。 访问靶机地址&#xff0c;打开java反序列化的 点进去后是如图的页面&#xff0c;随便输入一信息。 可以看到敏感信息直接显示在了页面上。 访问192.168.189.141:8080/cors1&#xff0c;可以看到…...

解决升级Linux内核后,open files设置无效的问题。

问题过程 操作系统是OpenEuler 20.03&#xff0c;内核由4.19.90-2112.8.0.0131.oe1.aarch64升级到kernel-4.19.90-2401.1.0.0233.oe1.aarch64后&#xff0c;重启系统后&#xff0c;重新开起来运行OceanBase就运行不起来了&#xff0c;提示open files must not be less than 20…...

关于防范勒索病毒Play新变种的风险提示

近日&#xff0c;工业信息化部网络安全威胁和漏洞信息共享平台监测发现针对 Linux的勒索病毒Play新变种&#xff0c;攻击对象主要为VMware ESXi 虚拟化环境&#xff0c;攻击目标包括制造、建筑业、IT、金融和房地产等行业。 Play勒索病毒又名 Balloonfly和PlayCrypt&#xff0…...

一款.NET开源、跨平台的DASH/HLS/MSS下载工具

前言 今天大姚给大家分享一款.NET开源&#xff08;MIT License&#xff09;、免费、跨平台的DASH/HLS/MSS下载工具&#xff0c;并且支持点播和直播&#xff08;DASH/HLS&#xff09;的内容下载&#xff1a;N_m3u8DL-RE。 网络流媒体传输协议介绍 DASH DASH是一种基于HTTP的…...

MATLAB学习日志DAY21

结构体&#xff08;2&#xff09; 如果将生成逗号分隔列表的表达式括在方括号中&#xff0c;MATLAB 会将该列表中的每一项都存储在数组中。示例中&#xff0c;MATLAB 创建一个数值行向量&#xff0c;该向量包含结构体数组 S 的每个元素的 score 字段&#xff1a; scores [S.…...

Spingboot请求tcp 方式

import lombok.extern.slf4j.Slf4j; import org.springframework.stereotype.Service;import java.io.IOException; import java.net.InetSocketAddress; import java.nio.ByteBuffer; import java.nio.channels.SocketChannel;/*** 请求tcp接口** author Mr丶s* date 2024/7/1…...

leetcode刷题日记-括号生成

题目描述 题目解析 回溯的题目&#xff0c;不过这个两个if我就感觉有点难以理解了&#xff0c;不过仔细的思考了一下&#xff0c;确实考虑到了每个位置的情况&#xff0c;特别是针对右边括号 题目代码 class Solution:def generateParenthesis(self, n: int) -> List[str…...

小程序按钮分享

使用button设置&#xff1a; open-type"share"&#xff1a;来微信分享&#xff1b; html&#xff1a; <button open-type"share"></button>...

多模态多智能体,在实现系统2(深思熟虑)方面的探索

多模态和多智能体&#xff0c;在系统2&#xff08;深思熟虑&#xff09;方面的探索 提出背景理性的定义为什么理性定义是四大基本原则&#xff0c;而不是其他数量&#xff0c;又为何是这四个&#xff0c;而不是其他&#xff1f;理性 不等于 推理 通过多模态多智能体系统增强理性…...

【CAN通讯系列8】如何准确接收数据?

在 【CAN通讯系列7】波特率是什么&#xff1f;已经介绍了CAN位时间和采样点等概念&#xff0c;每1位由同步段(SS)、传播时间段(PTS)、相位缓冲段1(PBS1)和相位缓冲段2(PBS2)四个段组成&#xff0c;这个也成为位时序&#xff0c;采样点位置处于PBS1和PBS2的交界处&#xff0c;如…...

RabbitMQ知识总结(基本概念)

文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 基本概念 Producer&#xff1a; 消息的生产者&#xff0c;是一个向…...

Prel语言入门学习:一篇全面的指南

引言 在编程语言的海洋中&#xff0c;Prel是一个较少人知的新星。作为一种专为数据处理和分析设计的语言&#xff0c;Prel结合了现代编程语言的简洁性与功能性&#xff0c;提供了一种独特的解决方案&#xff0c;尤其适用于数据科学家和分析师。本文将详细介绍Prel语言的基础&am…...

在云服务器上自动化部署项目,jenkins和gitee

▮全文概述 在编写项目时&#xff0c;很头大的事情就是需要自己手动的上传jar包到服务器上启动。如果出现一点bug&#xff0c;就要重头上传和启动。这是一件很烦的事情&#xff0c;所以&#xff0c;可以使用jenkins和gitee实现项目的自动部署 ▮全流程 在本地提交代码到gitee …...

python 参数输入

在 Python 中&#xff0c;参数输入通常有多种方式&#xff0c;这取决于你要从何处获取参数。以下是几种常见的方法&#xff1a; 1. 命令行参数 使用 sys.argv 获取命令行参数&#xff0c;或者使用 argparse 模块进行更复杂的参数解析。 示例 1: 使用 sys.argv import sys# …...

Spring面试篇章——Spring基本概述

Spring 的基本概述 Spring学习的核心内容—一图胜千言 IOC&#xff1a;控制反转&#xff0c;可以管理 Java 对象AOP&#xff1a;切面编程JDBCTemplate&#xff1a;是Spring提供一套访问数据库的技术&#xff0c;应用性强&#xff0c;相对好理解声明式事务&#xff1a;基于IOC …...

股票预测模型中注意力多层Attention RNN LSTM 的应用

全文链接&#xff1a;https://tecdat.cn/?p37152 原文出处&#xff1a;拓端数据部落公众号 Attention 机制是一种在神经网络处理序列数据时极为关键的技术&#xff0c;它赋予了模型“聚焦”能力&#xff0c;能够自动评估输入序列中各部分的重要性。通过为序列中的每个元素分…...

C语言 | Leetcode C语言题解之第313题超级丑数

题目&#xff1a; 题解&#xff1a; int nthSuperUglyNumber(int n, int* primes, int primesSize) {long dp[n 1];int pointers[primesSize];for (int i 0; i < primesSize; i) {pointers[i] 0;}long nums[primesSize];for (int i 0; i < primesSize; i) {nums[i] …...

PHP健身微信小程序系统源码

&#x1f3cb;️‍♀️健身新潮流&#xff01;解锁“健身微信小程序”的全方位塑形秘籍 &#x1f4f1;开篇&#xff1a;掌中健身房&#xff0c;随时随地动起来 你还在为找不到合适的健身场地或教练而烦恼吗&#xff1f;是时候告别这些束缚&#xff0c;拥抱“健身微信小程序”…...

树组件 el-tree 数据回显

树组件 el-tree 数据回显 树型结构的数据回显问题&#xff1a; 这里我只放了核心代码&#xff0c;主要是如何获取选中的树节点的id集合和如何根据树节点的id集合回显数据 大家根据需要自行更改&#xff01; <el-tree ref"authorityRef" node-key"id" …...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

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;供调用如何按…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...