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;
}

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