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)的值是一样的，所以我们不会存后面字典序小的数据。我们最要先将数据进行排序。
这里我们光速搓一个快排出来
在计算之前排好序就行了。
最终的代码
原文地址：https://blog.csdn.net/2301_80772499/article/details/137749981
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！