本文主要是介绍“生成元”问题——穷举生成“查找表”，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。
【题目来源】
刘汝佳《算法竞赛入门经典 第2版》 例题3-5 生成元（Digit Generator, ACM/ICPC Seoul 2005, UVa1583）
【解析】
一、原书代码：
本题的新知识点就是用程序生成一个“查找表”，方法是一次性枚举100000内的所有正整数m，它肯定是“m加上m的各个数字之和（即y）”的一个生成元，所以可以用数组ans[]建立一个查找表，取ans [y]的值为最的小m，即ans[y]的值为y的最小生成元，最后查表即可。
建立查找表的好处就是只需要完整地遍历一次，以后在数据范围内求任何数的最小生成元都能通过查找表快速查找，几乎不需要任何计算。
代码如下：
#include<stdio.h>
#include<string.h>
#define maxn 100005
int ans[maxn];
int main() {int T, n;memset(ans, 0, sizeof(ans));for(int m = 1; m < maxn; m++) {int x = m, y = m;while(x > 0) { y += x % 10; x /= 10; }//取ans[y]的值为最小的mif(ans[y] == 0 || m < ans[y]) ans[y] = m;}scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", ans[n]);}return 0;
}二、老金代码
老金没想那么多，上来就是“穷举”一波。穷举思路和原书基本一样，代码如下：
#include<stdio.h>
int main(){int n;scanf("%d", &n);for(int i=1; i<n; i++){int sum=i, t=i;//将数字t分离求和while(t){sum+=t%10;t/=10;}if(sum==n){printf("%d\n", i);return 0;}}printf("0\n");return 0;
}这篇关于“生成元”问题——穷举生成“查找表”的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
