刷题_25：星际密码 and 数根

喜欢ヅ旅行 2023-09-30 21:53 23阅读 0赞

### 一.星际密码 ###

**题目链接：**

> [星际密码][Link 1]

**题目描述：**

> **星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。  
> |1 1|^n => |Xn …|  
> |1 0| |… …|  
> 例如n=2时，  
> |1 1|^2 => |1 1| \* |1 1| => |2 1|  
> |1 0| |1 0| |1 0| |1 1|  
> 即2对应的数是“0002”。**

**输入描述：**

> **输入有多组数据。  
> 每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)**

**输出描述：**

> **对应每一组输入，输出一行相应的密码。**

**示例1：**

> **输入：  
> 6  
> 18 15 21 13 25 27  
> 5  
> 1 10 100 1000 10000  
> 输出：  
> 418109877711037713937811  
> 00010089410135017501**

**个人总结：**

> **本质上是一个斐波那契数列，然后要求我们输出的时候如果不足四位，则补零输出四位，如果大于四位，则输出后四位，所以我们可以计算一个斐波那契数列的table，来计算每一个斐波那契数，因为题目要求，所以我们对大于四位的保留四位即可，最后可以根据输入的数据直接取到斐波那契数，还有一个点就是[String.format()用法][String.format]。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        static int[] table = new int[10001]; 
        public static void main(String[] args) {
        
            //获取table表
            getTable();
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                int n = sc.nextInt();
                StringBuilder s = new StringBuilder();
                while (n-- != 0) {
        
                    int idx = sc.nextInt();
                    System.out.print(String.format("%04d",table[idx]));
                }
                System.out.println();
            }
        }
        
        public static void getTable() {
        
            table[0] = 1;
            table[1] = 1;
            for (int i = 2; i <= 10000; i++) {
        
                table[i] = (table[i - 1] + table[i - 2]) % 10000;
            }
        }
    }

--------------------

### 二.数根 ###

**题目链接：**

> [数根][Link 2]

**题目描述：**

> **数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。  
> 比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。  
> 再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。  
> 现在给你一个正整数，输出它的数根。**

**输入描述：**

> **输入包含多组数据。  
> 每组数据数据包含一个正整数n（1≤n≤10E1000）。**

**输出描述：**

> **对应每一组数据，输出该正整数的数根。**

**示例1：**

> **输入：  
> 24  
> 39  
> 输出：  
> 6  
> 3**

**个人总结：**

> **题目不难，难点是数据很大，1000位的数据，大大的超过了int和long类型的表示范围，那么我们如何储存呢？我们可以使用字符串来储存，然后将每个字符相加得到一个总数，然后这个总数就会变成一个int类型可以储存的数了，最后就行常规计算就行了。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                String s = sc.nextLine();
                char[] chs = s.toCharArray();
                int sum = 0;
                for (int i = 0; i < chs.length; i++) {
        
                    sum += chs[i] - '0';
                }
                System.out.println(getNumRoot(sum));
            }
        }
    
        public static int getNumRoot(int n) {
        
            int res = 0;
            while (true) {
        
                res += n % 10;
                n /= 10;
                if (n == 0) {
        
                    if (res <= 9) {
        
                        return res;
                    } else {
        
                        n = res;
                        res = 0;
                    }
                }
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/34f17d5f2a8240bea661a23ec095a062
[String.format]: https://blog.csdn.net/lonely_fireworks/article/details/7962171
[Link 2]: https://www.nowcoder.com/questionTerminal/e2422543519249f292d8435394ab82fe