Java题目训练——星际密码和数根

本是古典何须时尚 2023-09-30 22:24 3阅读 0赞

**目录**

一、星际密码

二、数根

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

### **一、星际密码** ###

题目描述：

> 星际战争开展了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)

输出描述：

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

示例

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

**题目解析：**

> 该题目有更简单的方法就是找到规律，发现左上角的数是按照斐波那契数列的规律增长的，可以直接根据斐波那契数的规律得出答案，这里给出了这道题目的常规思路，就是按照矩阵相乘的规则，得到每次乘n次方后矩阵左上角的数，对其进行长度判断如果大于4位则取后四位，不足4位则在输出时补0。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int[][] x = {
       {1, 1}, {1, 0}};
            while (scanner.hasNext()){
                int n = scanner.nextInt();
                int[] arr = new int[n];
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    arr[i] = scanner.nextInt();
                    String temp = Integer.toString(fun(x, arr[i]));
                    if(temp.length() < 4){
                        int num = 4 - temp.length();
                        for (int j = 0; j < num; j++) {
                            sb.append("0");
                        }
                    }
                    sb.append(temp);
                }
                System.out.println(sb);
            }
        }
    
        public static int fun(int[][] x, int a){
            int[][] x1 = new int[2][2];
            int[][] x2 = new int[2][2];
            int[][] res = new int[2][2];
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    x1[i][j] = x[i][j];
                    x2[i][j] = x[i][j];
                    res[i][j] = x[i][j];
                }
            }
    
            for (int i = 1; i < a; i++) {
                res[0][0] = (x1[0][0] * x2[0][0] + x1[0][1] * x2[1][0])%10000;
                res[0][1] = (x1[0][0] * x2[0][1] + x1[0][1] * x2[1][1])%10000;
                res[1][0] = (x1[1][0] * x2[0][0] + x1[1][1] * x2[1][0])%10000;
                res[1][1] = (x1[1][0] * x2[0][1] + x1[1][1] * x2[1][1])%10000;
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 2; k++) {
                        x1[j][k] = res[j][k];
                    }
                }
            }
            return res[0][0];
        }
    }

### **二、数根** ###

题目描述：

> 数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些 数字加起来。如此进行下去，直到得到是一位数为止。 比如，对于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

**题目解析：**

> 由于要考虑数字可能会超出范围，这里用了字符串进行相关操作，只要字符串的长度大于1（不是一位），就说明还没求得树根，继续求各位和，再将这个结果赋给字符串继续判断，直到位数为1，求得树根。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while(scanner.hasNext()){
                String s = scanner.nextLine();
                System.out.println(numRoot(s));
            }
        }
    
        public static String numRoot(String s){
            while(s.length() > 1){
                int sum = 0;
                for (int i = 0; i < s.length(); i++) {
                    sum += s.charAt(i) - '0';
                }
                s = Integer.toString(sum);
            }
            return s;
        }
    }

如有建议或想法，欢迎一起讨论学习~