美文网首页程序员
UVa1583 Digit Generator -- Java

UVa1583 Digit Generator -- Java

作者: adonis_stan | 来源:发表于2019-01-18 18:36 被阅读2次

我在 github 上建立了一个 repo,专门记录自己对刘汝佳的《算法竞赛入门经典(第二版)》中每个 UVa 例题和习题的解答,目前刚刚开始,会不断更新,本人水平不高,如有错误,欢迎大家指正。当然更希望大家能提供更优的解法,共同提高进步,满意的话给个 star 啊(●ˇ∀ˇ●)

github repo 传送门

QQ: 1583801169

【原题链接】点击即达

不过UVa OJ需要科学上网才能访问,故此处贴出百度云链接,有原题的pdf文档,需要的直接下载。失效的话可以私信或者评论留下邮箱。
链接:https://pan.baidu.com/s/1xV44H0SF0Ik45G515hSMGA
提取码:3n8v

【题意】
  生成元:给出两个正数 x 和 y,若 y 等于 x 加上 x 的各个数字之和,则称 x 是 y 的生成元。例如,216 的最小生成元是 198,121 的最小生成元是 0。
  此题要求你能求出一个给定正整数 n(1 <= n <= 100000) 的最小生成元,即若一个正整数 n 有多个生成元,你需要求出的是最小的那个生成元,若没有生成元,你需要打印出 0。

【输入】
  首先输入一个正整数 T,表示你需要输入 T 个正整数,并求出它们的最小生成元。

【输出】
每行输出对应正整数的最小生成元。

【代码】

       代码通过事先计算范围内所有正整数的最小生成元,存放在一个数组中,该下标对应的数组中的数值就是该下标的最小生成元。最后,通过查数组就能找到。

在 if 判断中,请大家仔细判别哦,此处需要体会一下。
y < MAXN:这个条件是防止数组越界的,如果你用的 C/C++ 此处不需要这个判断,但是 Java 此处需要。或者可以捕捉这个异常,但是此处我没有这么做。(这涉及语言自己处理的问题了)
i < ans[y]:这个条件是找出最小生成元啊!(o゚v゚)ノ

import java.util.Scanner;

/**
 * @author Adonis
 * @Email 1583801169@qq.com
 * @Date 2019-01-18 10:24:57
 * @Version V1.0
 */

public class Main {

    private static final int MAXN = 100005;
    
    public static void main(String[] args) {
        int[] ans = new int[MAXN];  // automatically initialized to 0
        int n = 0, c = 0;
        Scanner in = new Scanner(System.in);
        
        for (int i=1; i<MAXN; i++) {
            int x = i, y = i;
            
            while (x > 0) { // get the sum of the numbers of x and x
                y += x % 10;
                x /= 10;
            }
            if (y < MAXN && (ans[y] == 0 || i < ans[y])) {  // y<MAXN: avoid exceeding the length of array ans
                ans[y] = i;
            }
        }
        
        c = in.nextInt();
        for (int i=0; i<c; i++) {
            n = in.nextInt();
            System.out.println(ans[n]);
        }
        in.close();
    }

}

相关文章

网友评论

    本文标题:UVa1583 Digit Generator -- Java

    本文链接:https://www.haomeiwen.com/subject/fcngdqtx.html