首页分享数根与星际密码算法解析

数根与星际密码算法解析

来源：花匠小妙招时间：2025-04-01 19:08

题目：数根

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

输入描述: 输入包含多组数据。

每组数据数据包含一个正整数n（1≤n≤10E1000）。

输出描述: 对应每一组数据，输出该正整数的数根。

题解：
求正整数n的树根, n的范围为[1, 101000 ]
int和long都不在取值范围内，此时要接收输入的数据，只能考虑以下类型:
(1) BigDecimal
(2) String
题目要求是每一-位来相加，相对来说，使用String从0开始遍历以后相加更加容易
I
要注意的事项:
(1)相加后的结果可能还不是一位数,即还不满足树根的要求,需要再次相加，如759，则为7+5+9=21,不是一位数，还需要再次计算: 2+1=3,则树根为3
(2)字符串可以使用charAt(int index)方法获取字符,字符可以直接转换为int。特殊的，当字符是数字0-9时，可以使用字符与字符相减操作，即可得到数字的差值如’9’-‘6’，返回值即为9-6的结果3。所以字符’0’-‘9’,要取int值,使用字符- ‘0’即可。如字符’5’，要获取数字值5,使用’5’-'0’即可

import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan=new Scanner(System.in); while(scan.hasNext()){ String arr=scan.nextLine(); while(arr.length()>1){ int count=0; for(int i=0;i<arr.length();i++ ){ count=count+arr.charAt(i)-'0'; } arr=String.valueOf(count); } System.out.println(arr); } } }

1234567891011121314151617181920

在这里插入图片描述

题目：星际密码

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

输出描述:
对应每一组输入，输出一行相应的密码。

import java.util.*; public class Main{ public static void main(String[] args){ int[] nums=new int[10001]; nums[1]=1; nums[2]=2; for(int i=3;i<10001;i++){ nums[i]=nums[i-1]+nums[i-2]; nums[i]=nums[i]%10000; } Scanner scan=new Scanner(System.in); while(scan.hasNext()){ StringBuilder sb=new StringBuilder(); int n=scan.nextInt(); for(int i=0;i<n;i++){ int xi=scan.nextInt(); sb.append(String.format("%04d",nums[xi])); } System.out.println(sb); } } }

12345678910111213141516171819202122