2024蓝桥杯——宝石问题

先展示题目

声明

以下代码仅是我的个人看法,在自己考试过程中的优化版,本人考试就踩了很多坑,我会—一列举出来。代码可能很多,但是总体时间复杂度不高只有0(N²)

函数里面的动态数组我没有写开辟判断和free,这里我忽略掉了。

正文

先直接抛出最后的代码:

 

我也觉得太长了,大家可以当做知识点的掌握来看吧。

从数据中取出n个数的问题-->可以拓展到取出所有子集问题

先讲子集问题

这个问题我们可以用三个for循环来做,但是时间复杂度太高了。所以我们有以下的方法。

一个数取不取就有两种情况。我们可以用0或1来表示。那么我们就可以用二进制来表示我们的取或不取,用每位二进制的位置来对于每个元素。

例如:有1 2 两个数字。我们就可以用两位二进制来表示:00 01 10 11分别表示 不取任何数 取2 取1 都取。一共有2^2次方中情况

那么我们推广到n,就有2^n种。

我们来尝试写一下代码。

直接用二进制

完全没问题。

用数组模拟二进制

这里有一个问题不知道大家看到没:2^n 容易溢出。因此我们可以用数组来模拟二进制的自增。

自增问题涉及到进一问题,所以我们需要运用到递归,递归的判断终止条件就是n+1位由0变成1。

所以我们需要开辟n+1长度的数组nums。

用类似递归来实现
用循环(最优解)

这里几个continue和return一定要有,不然逻辑就错了

这样的话我们就可以遍历任何长度的数组的子集了!

下面把代码给大家

#include<stdio.h>
#include<stdlib.h>

void nums_add(int* arr, int len) {
    if (len == 1) {
        *arr = 1;
        return;
    }
    else if (*arr == 1) {
        *arr = 0;//加一后变成零了
        nums_add(arr + 1, len - 1);//让后面一位加一,然后剩余长度减一
    }
    else if(*arr==0){
        *arr=1;//0加成1
    }
}

void nums_add_(int* arr, int len) {
    int k = len,i=0;
    while (1) {
        if (k == 1) {
            arr[i] = 1;//如果长度为1了就退出
            return;
        }
        if (arr[i] == 1) {
            arr[i] = 0;
            ++i;
            --k;
            continue;//如果要进一我们还要循环一次,所以用continue
        }
        else if (arr[i] == 0) {
            arr[i] = 1;
        }
        return;//到这里表示从0加到一,我们就不需要再循环了,直接结束循环
    }
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    if (!arr)return -1;
    for (int x = 0; x < n; ++x) {
        scanf("%d", arr + x);
    }

    int* nums = (int*)calloc(n+1, sizeof(int));
    int m[3];
    while (1) {
        nums_add_(nums, n + 1);
        if (nums[n] == 1)break;
        int k = 0;
        for (int x = 0; x < n; ++x) {
            if (nums[x] == 1)
            {
                if (k == 3)break;//已经有三个了还要存,直接跳过这个
                m[k++] = arr[x];
            }
        }
        if (k!=3)continue;//如果不等于三个,直接跳过到下一个循环
        printf("%d %d %d",m[0],m[1],m[2]);
        printf("\n");
    }
    return 0;
}

因为递归会开辟内存,所以后面的代码我们都用第二种非递归的

取出长度固定的所有子集

如果我们只要里面长度为3的子集怎么办呢?

自增变量来判断

我们可以在for循环里面先用一个长度为三的数组来存储我们的数据,再用一个变量来看是否满足。满足就打印。

在递归/非递归的时候就检测好

递归的时候我们完全就可以把1的数量统计好,所以可以做以下改变

但是这样也没怎么变化嘛,那么我们既然可以知道1了,我们再储存一下有1的数组的位置可以吧?

这里我们发现是反着来的,我们把打印的顺序反过来就行了。因为这里的m数组相当于栈

#include<stdio.h>
#include<stdlib.h>

void nums_add(int* begain_arr, int* arr, int* m, int* p, int len, int* number) {
    if (len == 1) {
        *arr = 1;
        return;
    }
    else if (*arr == 1) {
        *arr = 0;//加一后变成零了
        --(*number);
        if (*p>0) {
            --p;
        }
        nums_add(arr,arr + 1,m,p, len - 1,number);//让后面一位加一,然后剩余长度减一
    }
    else if(*arr==0){
        ++(*number);
        *arr=1;//0加成1
        if (*p < 3) {
            m[(*p)++] = (int)(arr - begain_arr);
        }
    }
}

void nums_add_(int* arr,int*m,int *p,int len, int*number) {
    int k = len,i=0;
    while (1) {
        if (k == 1) {
            arr[i] = 1;//如果长度为1了就退出
            return;
        }
        if (arr[i] == 1) {
            arr[i] = 0;
            --(*number);
            ++i;
            --k;
            if (*p>0) {
                --(*p);
            }
            continue;//如果要进一我们还要循环一次,所以用continue
        }
        else if (arr[i] == 0) {
            arr[i] = 1;
            ++(*number);
            if (*p < 3) {
                m[(*p)++] =i;
            }
        }
        return;//到这里表示从0加到一,我们就不需要再循环了,直接结束循环
    }
}
int A_(int m, int n) {//非递归型
    int k = 1, i = m, j = n;
    while (1) {
        if (i == 1)return k * j;
        else {
            k *= j;
            --i;
            --j;
        }
    }
}
int C_(int m, int n) {
    return m == 0 ? 1 : A_(m, n) / A_(m, m);
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    if (!arr)return -1;
    for (int x = 0; x < n; ++x) {
        scanf("%d", arr + x);
    }

    int* nums = (int*)calloc(n+1, sizeof(int));
    int m[3] , p = 0 , number1 = 0;//定义number1存储我们的1的数量
    while (1) {
        nums_add_(nums,m,&p, n + 1, &number1);
        if (nums[n] == 1)break;
        int k = 0;
        if (number1 != 3)continue;
        printf("%d %d %d",m[2],m[1],m[0]);
        printf("\n");
    }
    return 0;
}

那么我们第一部分终于也是完成了,我嘞个豆真是多!!!!!!!!!!!!!!!!!!!!!!!!!

a,b的最小公倍数和最大公约数

我们题目要求的是最小公倍数,那么求这个我们可以枚举,但是时间复杂度复很高,所以我们就有特殊的算法。

我们首先要了解一个知识点就是

a*b=最大公约数(a,b)*最小公倍数(a,b)

我们求最小公倍数可能没有优秀的算法,但是我们最大公约数有优秀的算法。那么就可以通过这个式子进行转化。

辗转相除法求最大公约数

举个例子:求16 和 24的最大公约数

                24%16 =8

                16%8 = 0

                所以答案是8 

如果开始两个数字交换呢?

                16%24=16

                24%16=8 

                16%8=0

我们发现就是多了一部,没有太大差别。

那么我们开始实现

这里return的是最大公约数。

如果求三者的最大公约数或者最小公倍数,把其中两个数的先求出来,再看成整体和另一个求。

S

那么图中的表达式我们就可以算了

这里同样的,先除法再乘法,防止溢出了。

创建二维数组来存储三个都是1的数据。

我们就要用一个二维数组来储存我们的数据。那么每一个数组的长度是多少呢?

根据组合数我们要C(3,n)长度。排列组合在编程里面也很常见,我们也要知道他是怎么算出来的,排列组合我在下面讲到

排列组合函数

先是讲A(m,n)

如果m=n,那么就是算的阶乘。

我们可以通过A(m,n)=A(m-1,n-1)*n   来计算

C(m,n)

它有两个公式可以算,一个是C(m,n)=A(m,n)/A(n,n)  另一个是C(m,n)=n!/m!/(n-m)!

那么那个好呢?当然是第一个,第一个数字间相乘的次数少,不容易溢出。

储存后方便我们后面再取。

我们再用一个变量来存储S的最大值

那么我们的宝石问题就完成了。

真的完成了吗?

no no no

存储根本不需要二维数组,我写到这才发现,我们只要用一个长度为3个数组来储存最大的数据就行了

那么我们的排列组合函数就不需要了。

另外补充

我们m数组的长度定义的太短了,会产生越界访问。所以可以将m数组的长度定义长一点。可以和arr的数组一样长.

提前排序来解决字典序要求

我们的代码已经可以计算了,但是还有最后一个坑。例如我们逆向输入

因为S(5,4,3)和S(1,2,3)的值是一样的,所以我们不会存后面字典序小的数据。我们最要先将数据进行排序。

这里我们光速搓一个快排出来

在计算之前排好序就行了。

最终的代码

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547016.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

频率域滤波基础(离散傅里叶变换使用填充的缺陷)

本来是个很简单的问题&#xff0c;作者硬是写的这么复杂&#xff0c;翻译还搞错了。重点是我发现作者真正有用的东西没讲到&#xff0c;比如相位和谱如何影响图像。连个转换公式都没有&#xff0c;我只能说作者是在混字数。 首先看关于中心对称是什么意思&#xff1f;我木太明白…

MySql 视图 存储过程 触发器

文章目录 视图数据库对象视图的理解创建、查看、更新、删除 存储过程和存储函数概述分类存储过程的创建和调用存储函数的创建和调用存储过程和存储函数的对比存储过程和存储函数的查看、修改、删除 变量GLOBAL 与 SESSION 变量的使用会话用户变量和局部变量的使用 定义条件与处…

【机器学习300问】70、向量化技术来计算神经网络时维度如何确保正确?

一、向量化技术在进行神经网络计算时的优势 向量化是一种优化技术&#xff0c;通过使用数组操作代替for循环&#xff0c;可以大大提高代码的性能和效率。在深度学习中尤其明显&#xff0c;可以提高计算效率、简化代码、优化内存使用。 二、如何确保计算时维度是正确的&#xf…

中标了,Trojan/Hijack.v木马病毒怎么解决?

火绒只是提示有病毒木马&#xff0c;并未解决。 经过不断尝试.。。。。。。 往下拉找到 Internet选项 连接 – 局域网设置 把前面的勾选取消 发现以上办法网络上出现的搜索注册表关键字等办法都无法解决。。。 解决方法一&#xff1a; 电脑进入安全模式&#xff0c;然后进…

【vue】v-model 双向数据绑定

:value&#xff1a;单向数据绑定v-model&#xff1a;双向数据绑定 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0">…

STM32 MPU配置参数

TXE LEVEL一般只用MPU_TEX_LEVEL0 1 - 1 - 1 -0性能最强&#xff08;TEX - C - B- S&#xff09;. #define MPU_TEX_LEVEL0 ((uint8_t)0x00) #define MPU_TEX_LEVEL1 ((uint8_t)0x01) #define MPU_TEX_LEVEL2 ((uint8_t)0x02) 基于上表进行常用配置 &#xff…

Wpf 使用 Prism 实战开发Day19

待办事项功能页面完善以及优化 概要&#xff1a; 由于待办事项功能页&#xff0c;数据已正常渲染出来了。但页面新增&#xff0c;查询&#xff0c;修改&#xff0c;删除等功能还未实现。本章节来实现页面的请求后台实现CURD&#xff08;增删改查&#xff09; 一.待办事项查询…

泰迪智能科技携手韩山师范学院“企业微专业合作办学招生宣讲”圆满结束

为进一步深化校企合作&#xff0c;落实高校应用型人才培养。2024年4月11日&#xff0c;泰迪智能科技携手韩山师范学院开展企业微专业合作办学招生宣讲会在韩山师范学院顺利举行&#xff0c;本次宣讲会旨在与韩山师范学院学子深入讲解数字经济时代下的企业用工需求&#xff0c;着…

ins视频批量下载,instagram批量爬取视频信息

简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…

数据结构 -- 二分查找

本文主要梳理了二分查找算法的几种实现思路&#xff0c;基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客 1、基本概念 &#xff08;1&#xff09;前提条件&#xff1a;待查找数据必须…

解决调用相同url数据不刷新问题

原代码 原因 谷歌浏览访问相同接口默认调用缓存数据 解决方案 添加时间戳

WebKit简介及工作流程

文章目录 一、WebKit简介二、WebKit结构三、Webkit工作流程四、WebKit常见问题五、WebKit优点六、相关链接 一、WebKit简介 WebKit是一个开源的浏览器引擎&#xff0c;它的起源可以追溯到2001年&#xff0c;当时苹果公司推出了其首款基于Unix的操作系统Mac OS X。在2002年&…

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法

星火大模型的主页&#xff1a;iFlytekSpark-13B: 讯飞星火开源-13B&#xff08;iFlytekSpark-13B&#xff09;拥有130亿参数&#xff0c;新一代认知大模型&#xff0c;一经发布&#xff0c;众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便&#xff0c;科…

Golang | Leetcode Golang题解之第30题串联所有单词的子串

题目&#xff1a; 题解&#xff1a; func findSubstring(s string, words []string) (ans []int) {ls, m, n : len(s), len(words), len(words[0])for i : 0; i < n && im*n < ls; i {differ : map[string]int{}for j : 0; j < m; j {differ[s[ij*n:i(j1)*n]…

分布式的计算框架之Spark(python第三方库视角学习PySpark)

基本介绍 Apache Spark是专为大规模数据处理而设计的快速通用的计算引擎 。现在形成一个高速发展应用广泛的生态系统。 特点介绍 Spark 主要有三个特点&#xff1a; 首先&#xff0c;高级 API 剥离了对集群本身的关注&#xff0c;Spark 应用开发者可以专注于应用所要做的计…

牛客网刷题:BC48 牛牛的线段

输入描述&#xff1a; 第一行输入 x1 和 y1&#xff0c;用空格隔开。 第二行输入 x2 和 y2&#xff0c;用空格隔开。 其中 x1 &#xff0c; y1 &#xff0c;x2 &#xff0c;y2 都是整数 输出描述&#xff1a; 输出线段的长度的平方 解题思路&#xff1a; 定义四个变量 用…

【黑马头条】-day06自媒体文章上下架-Kafka

文章目录 今日内容1 Kafka1.1 消息中间件对比1.2 kafka介绍1.3 kafka安装及配置1.4 kafka案例1.4.1 导入kafka客户端1.4.2 编写生产者消费者1.4.3 启动测试1.4.4 多消费者启动 1.5 kafka分区机制1.5.1 topic剖析 1.6 kafka高可用设计1.7 kafka生产者详解1.7.1 同步发送1.7.2 异…

【C 数据结构】栈

文章目录 【 1. 基本原理 】栈的分类 【 2. 动态链表栈 】2.1 双结构体实现2.1.0 栈的节点设计2.1.1 入栈2.1.2 出栈2.1.3 遍历2.1.4 实例 2.2 单结构体实现2.2.0 栈的节点设计2.2.1 入栈2.2.2 出栈2.2.3 实例 【 3. 顺序栈 】3.1 入栈3.2 出栈3.3 实例 【 1. 基本原理 】 栈&…

操作系统:进程(二)

进程的状态 进程状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。在三态模型中&#xff0c;进程状态分为三个基本状态&#xff0c;即运行态&#xff0c;就绪态&#xff0c;阻塞态。 一个进程从创建而产生至撤销而消亡的整个生命期间&#xff0c;…

【图像分类】基于深度学习的轴承和齿轮识别(ResNet网络)

写在前面: 首先感谢兄弟们的关注和订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。(专栏订阅用户订阅专栏后免费提供数据集和源码一份,超级VIP用户不在服务范围之内,不想订阅专栏的兄弟们可以私信…