求解最小生成元

朱雀 2022-05-28 03:18 179阅读 0赞

#### 前言 ####

因为看着刘汝佳的算法书学习的算法，今天聊聊最小生成元，关于这一点我觉得书上的方法有些不妥，因为就拿出来说说，这个算法相对还是比较简单的。

#### 最小生成元问题描述 ####

如果x加上x的各个位数字之和得到y，就说x是y的生成元；给出n，（1<=n<=100000），求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198 , 0, 1979。

#### 算法思路 ####

1、如果考虑到多次求解的话，那么就先把所有的数的最小生成元求解出来存放在数组中，后面求解的时候直接通过数组中获取。  
2、如果只是求解几次的话，那么就不用采用以上方法，例如我们求解216的最小生成元，根据描述我们可以知道，最小生成元一定是大于216-9\*3=189的。因为最小生成元+每个数字的和得到Y，那么当每个数字和最大的时候，最小生成元就是最小的。

#### 代码实现1 ####

#include<stdio.h>
    #include<string.h>
    #define MAX 100050
    int main() {
        int a[MAX];
        int sum;
        int num;
        int n;
        memset(a, 0, sizeof(a));
        for(int i=0; i<MAX; i++) {
            int temp = i;
            sum = 0;
            while(temp > 0) {
                sum += temp%10;
                temp /= 10;
            }
            if(!a[sum+i]) {
                 a[sum+i] = i;
            }
        }
        scanf("%d", &num);
        while(num--) {
            scanf("%d", &n);
            printf("%d\n", a[n]);
        }
        return 0;
    }

#### 代码实现2 ####

#include<stdio.h>
    #include<string.h>
    int main() {
        int num;
        int count = 0;
        int temp;
        int flag = 0;
        scanf("%d", &num);
        temp = num;
        while(temp > 0){
            count++;
            temp /= 10;
        }
        for(int i=num-count*9; i<num; i++) {
            int sum=0;
            temp = i;
            while(temp>0) {
                sum += temp%10;
                temp /= 10;
            }
            if(sum+i == num) {
                flag = 1;
                printf("%d", i);
                break;
            }
        }
        if(!flag) {
            printf("0");
        }
    }