【OJ】 星际密码、数根

1.星际密码

题目描述

  星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。OJ连接
|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”。

解题思路

  这个题目首先需要明确矩阵是固定的，其次是矩阵相乘的方法矩阵相乘 |a1 a2| * |c1 c2| = |a1c1 + a2d1 a1c2 + a2d2| |b1 b2| |d1 d2| |b1c1 + b2d1 b1d2 + b2d2|矩阵是|1 1|^2 = |1 1|*|1 1|=|2 1| |1 0| |1 0| |1 0| |1 1| n的取值：1 2 3 4 5 6 … 左上角值：1 2 3 5 8 13 … 是一个变式的斐波那契。
初始化斐波那契数列，每次获取对应数据，打印最后4位即可

// write your code here cpp
#include 
#include 
using namespace std;vector<int> ret = {1, 1};void data_init()
{for(int i = 2; i < 10001; ++i){ret.push_back((ret[i - 1] + ret[i - 2])%10000);}
}int main()
{data_init();int n;while(cin >>n){int num = 0;while(n--){cin >> num;printf("%04d", ret[num]);}printf("\n");}return 0;
}

2.数根

题目描述

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

// write your code here cpp
#include 
#include 
#include 
using namespace std;int main()
{string s;while(getline(cin, s)){int sum = 0;for(int i = 0; i < s.size(); ++i){int tmp = s[i] - '0';sum += tmp;}int n = sum;while((n / 10) != 0){vector<int> v;int tmp = n;while(tmp){v.push_back(tmp%10);tmp = tmp / 10;}int sum = 0;for(int i = 0; i < v.size(); ++i)sum += v[i];n = sum;}cout << n <<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！