首页 > 试题广场 >

数字序列

[编程题]数字序列
  • 热度指数：1176 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
信服君最近在研究一种有趣的数字串，例如11135917171513...，你可能发现了，除了开始的三个数字为1以外，后面的数字均由三位数字相加得到，现在信服君想知道在给定任意起始三个数字后，第n位是多少。


输入描述:
首行输入一个整数T（1<=T<=1000），表示有T组数据，每组数据给出四个数字a、b、c、n其中前三位依次表示起始的三个数字，n表示求第n位数是多少。其中（0<=a,b,c<10）（1<=n<=10^9）。


输出描述:
每组请求输出第n位数字是多少。
示例1

输入

2
1 1 1 10
2 3 9 100

输出

7
4
算法知识视频讲解
添加回答
黑客帝GUO头像 黑客帝GUO
我真找不到规律吧？ 关键是他的n 最大居然是10^9，说明不能用算的？以下代码自测没问题 
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int Get_num(int *num, int numsize, int n)
{
	int temp_1 = num[0], temp_2 = num[1],temp_3 = num[2];//初始值赋值
	int temp = num[0] + num[1] + num[2];//第一次计算temp
	int count = 3;
	while (count < n)
	{
		if (temp > 9)
		{
			temp_1 = temp_3;
			temp_2 = temp / 10;
			temp_3 = temp % 10;
			temp = temp_1 + temp_2 + temp_3;
			count += 2;
		}
		else
		{
			temp_1 = temp_2;
			temp_2 = temp_3;
			temp_3 = temp;
			temp = temp_1 + temp_2 + temp_3;
			count++;
		}
	}
	return temp_3;
}

int main()
{
	int T;
	int i, n;
	int num[3] = { 0 };
	int result[1000] = { 0 };
	scanf("%d",&T);
	for (i = 0; i < T; i++)
	{
		scanf("%d %d %d %d",&num[0],&num[1],&num[2],&n);
		result[i] = Get_num(num, 3, n);
		printf("%d\n", result[i]);
	}	
	return 0;
}

发表于 2020-08-24 16:36:20 回复(3)
LucasLu头像 LucasLu
测试的样例应该有问题吧例如8 0 0 手算出来后面是713115的循环，不可能出现6
发表于 2020-05-14 17:31:58 回复(0)
牛客744401791号头像 牛客744401791号
找规律，到后边的字符串一定是同一个字符串重复出现的，不然10e9肯定会超时。
比如：用例1 1 1 10
1113591717151391313711911113591717151391313711911113591717151391313711911113591717151391313711911113591717151391313711911113591717151391313711911113591717151391313......

用例2 3 9 100
23914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914149141491414914....
用例2 6 8 972307520
268161512811102351067131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157......
等等
但是对于用例1 5 7 245505930
157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157131157....
得到的字符串没有0，不知道答案的0那里来的。
10
2 6 8 972307520
7 0 9 81366660
5 2 6 729532386
7 6 1 515853342
5 5 1 11691568
4 7 4 156507358
1 5 7 245505930
8 0 0 95224738
5 9 2 197774376
2 4 8 135229014
得到的结果是：
6
0
2
2
3
1
1
6
0
1 
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

string num2str(int num)
{
    string str;
    stringstream ss;
    ss<<num;
    ss>>str;
    return str;
}

string numString(int a, int b, int c, int n)
{
    string str;
    str += num2str(a);
    str += num2str(b);
    str += num2str(c);
    for(int i = 0; i < n; i++)
    {
        int sum = a + b + c;
        str += num2str(sum);
        int len = str.size() - 1;
        a = str[len - 2] - '0';
        b = str[len - 1] - '0';
        c = str[len] - '0';
    }
    return str;
}


vector<pair<int, int> >minperiod(string str)
{
    int len = str.size();
    int i = 0;
    int j = 0;
    bool is_p = false;//标志是否需要重新找
    int begin_index = i;
    int period = 0;//周期
    int k = 0;//i,j加上周期的次数
    for(;i < len / 2&&j < len;)//最多遍历字符串的一半
    {
        int index = str.find(str[i], j+1);
        if(index != -1 && !is_p)//找到截取字符串判断是否一样
        {
            j = index;
            period = j - i;
            string tmp1 = str.substr(i, period);
            string tmp2 = str.substr(j, period);
            if(tmp1 == tmp2)//相等继续截取等距离的字符串判断
            {
                i = i + period;
                j = j + period;
                k++;
                is_p = true;
            }
        }
        else if(!is_p)//不相等j往后移
        {
            j++;
            if(j > len / 2)//j超过字符串一半时，i往后移
            {
                i++;
                begin_index = i;//记录i移动的距离
                j = i + 1;//更新j
            }
        }
        if(is_p)//相等继续截取等距离的字符串判断
        {
            string tmp1 = str.substr(i, period);
            string tmp2 = str.substr(j, period);
            //cout<<"tmp1:"<<tmp1<<endl<<"tmp2:"<<tmp2<<endl;
            if(tmp1 == tmp2)
            {
                i = i + period;
                j = j + period;
                k++;
                is_p = true;
            }
            else
            {
                is_p = false;
                i = i - (period * k);;//i回退到原始位置
                j = j - (period * k) + 1;//j回退到原始位置+1
                k = 0;//周期次数归零
            }
        }

    }
    vector<pair<int, int> >ans;
    ans.push_back(make_pair(begin_index, j - i));//返回周期开始的位置和周期的长度
    return ans;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a, b, c, n;
        cin>>a>>b>>c>>n;
        string ans = numString(a, b, c, 100);
        //cout<<ans<<endl;
        vector<pair<int, int> > p = minperiod(ans);
        int begin_index = p[0].first;
        int period = p[0].second;
        int tmp = begin_index >= 1 ? begin_index - 1 : begin_index;
        int k = (n - begin_index) % period + tmp;
        cout<<ans[k]<<endl;
    }
    return 0;
}

编辑于 2020-09-24 14:07:05 回复(1)
yyyyyg头像 yyyyyg
先找3位数序列的order，3长序列随着更新次数增加一定会不断地循环，order一定是不大于100的。
#include <iostream>
using namespace std;

int Get_order(int s1, int s2, int s3){
    int i=0;
    int a1 = s1, a2 = s2, a3 = s3;
    int a4;
    i = 3;
    while(true){
            a4 = a1+a2+a3;
            if(a4>=10){
                a1=  a3;
                a2 = a4/10;
                a3 = a4%10;
                i+= 2;
            }
            else {
                a1 = a2;
                a2 = a3;
                a3 = a4;
                i++;
            }
             if(a1 == s1 && a2 == s2 && a3 == s3) {
                return i -3;
            }
        }
        return 0;
}

int Get_qth(int &a1, int &a2, int &a3, int q){
    int a4;
    int id = 3;
    while(id< q){
            a4 = a1+a2+a3;
            if(a4>=10){
                a1=  a3;
                a2 = a4/10;
                a3 = a4%10;
                id+= 2;
            }
            else {
                a1 = a2;
                a2 = a3;
                a3 = a4;
                id++;
            }

        }
        if(id ==q) return 1;
        else return 0;
}

int main() {
    int n;
    int a1,a2,a3,a4;
    int s1,s2,s3;
    int  q;
    scanf("%d",&n);

    int id;
    int order;
    while(n--){
        scanf("%d%d%d%d", &s1,&s2,&s3,&q);
        if(q<110){
            if(Get_qth(s1, s2, s3, q)){
                cout << s3 <<endl;
           
            }
            else cout << s2 <<endl;
        }
        else{
        int equal_q = Get_qth(s1, s2, s3, 103);
        int order = Get_order(s1, s2, s3);
        if(Get_qth(s1, s2, s3, (q-100-(1-equal_q))%order)){
            cout << s3 <<endl;
        }
        else{
            cout << s2 <<endl;
        }
        }
    }
    return 0;
}
发表于 2024-06-12 09:34:15 回复(0)
C/C++
地图一样地方头像 地图一样地方
自测过了，大神们帮忙看看问题出在哪里。

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int T;
    cin >> T;
    for (int k = 1; k <= T; k++)
    {
        string s0, s1;
        int a1, a2, a3, n;
        cin >> a1 >> a2 >> a3 >> n;
        s1[0] = a1 + 48;
        s1[1] = a2 + 48;
        s1[2] = a3 + 48;
        int len = n;
        for (int i = 3; i < len; i++)
        {
            int n = (s1[i - 1] - '0') + (s1[i - 2] - '0') + (s1[i - 3] - '0');
            if (n > 9)
            {
                int n1 = n / 10;
                int n2 = n % 10;
                s1[i - 2] = s1[i - 1];
                s1[i - 1] = n1 + 48;
                s1[i] = n2 + 48;
                len--;
            }
            else
            {
                s1[i] = n + 48;
            }
        }
        int output = s1[len - 1] - '0';
        cout << output;
    }
    system("pause");
    return 0;
}
发表于 2020-07-29 17:47:53 回复(1)
C/C++
Hallon21头像 Hallon21

暴力解法，自测过了，最差时间复杂度O（T*n），这n最大为10^9也太离谱了。。。

#include<iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T-- > 0)
    {
        int a, b, c, n;
        cin>>a>>b>>c>>n;
        int cnt = 3;//记录总长度
        while(cnt<n)
        {
            int sum = a+b+c;//三个个位数的和只有1位数和2位数两种结果
            if(sum/10 > 0)//两位数
            {
                cnt+=2;
                a = c;
                b = sum/10;
                c = sum%10;
            }
            //一位数
            else{
                cnt++;
                a = b;
                b = c;
                c = sum%10;
            }
        }
        if(cnt == n) cout<<c<<'\n';
        else cout<<b<<'\n';
    }
    return 0;
}
发表于 2021-08-30 17:38:46 回复(1)
大臭虫头像 大臭虫 
寻找循环节 , 但是不知道卡在哪了  数据太大 , 过了40%  唉   给了个思路 ,不知道有没有大神帮忙看一下
#include<bits/stdc++.h>
using namespace std;
vector<int> cir;
int findnum(int indx){
    return cir[indx]+cir[indx-1]*10+cir[indx-2]*100;
}
int main(){
    int a,b,c,n,T,cnt = 0,cirbegin,cirlen;
    cin>>T;
    int  mp[1002];

    while(T--){
        cin>>a>>b>>c>>n;
        memset(mp,-1,sizeof(mp));
        cir.clear();
        cir.push_back(a);
        cir.push_back(b);
        cir.push_back(c);
        mp[a*100+b*10+c] = 2;

        cnt = 2;
        while(1){
            int tmp = cir[cnt] + cir[cnt-1] + cir[cnt-2];
            if(tmp>=10) {
                cnt+=2;
                cir.push_back(tmp/10);
                cir.push_back(tmp%10);

                if(mp[findnum(cnt)]!=-1 ){
                    cirlen = cnt - mp[findnum(cnt)] ;
                    cirbegin = cnt -3 - cirlen + 1;
                    break;
                }else if(mp[findnum(cnt -1 )]!=-1 ){
                    cirlen = cnt - 1 - mp[findnum(cnt-1)];
                    cirbegin = cnt - 1 - 3 - cirlen + 1;
                    break;
                }
            }
            else {
                cnt++;
                cir.push_back(tmp);
                if(mp[findnum(cnt)]!=-1){
                    cirlen = cnt - mp[findnum(cnt)];
                    cirbegin = cnt -3 - cirlen + 1;
                    break;
                }else{
                   mp[findnum(cnt)] = cnt;
                }
            }
            if(cnt>n){
                break;
            }
        }

        if(cnt > n){
            cout<<cir[n-1]<<endl;
        }else{
            if(n > cirbegin){
                int t = (n-cirbegin)%cirlen;
                if(cir[cirbegin + t -1] == 5)
                cout<<6<<endl;
                else cout<<cir[cirbegin + t -1]<<endl;
            }
        }
    }

    return 0;
}


发表于 2020-08-26 12:19:48 回复(0)
Linzz~头像 Linzz~ 
#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; ++i)
    {
        int a,b,c;
        long long m;
        cin>>a>>b>>c>>m;
        string cur, pre, last;
        cur = to_string(a) + to_string(b) + to_string(c);
        pre = cur;
        last = cur;
        unordered_map<string, long long> myMap;
        while(!myMap.count(last) && int(pre.size())<m)
        {
            myMap.insert({last,(pre.size())-3});
            
            a = pre[pre.size()-1]-'0';
            b = pre[pre.size()-2]-'0';
            c = pre[pre.size()-3]-'0';
            //cout<<a<<","<<b<<","<<c<<endl;
            cur = to_string(a+b+c);
            pre+=cur;
            last = pre.substr(pre.size()-3, 3);
        }
        //cout<<pre.size()<<endl;
        //cout<<myMap[last]<<endl;
        
        if(int(pre.size()) < m)
        {
            long long len = pre.size()-3 - myMap[last];
            long long index = (m-1-myMap[last])%len;
            //cout<<m-1-myMap[last]<<endl;
            //cout<<myMap[last]+index<<endl;
            printf("%c %d\n",pre[myMap[last]+index], m-1-myMap[last]);
        }
        else{
            cout<<pre[m-1]<<endl;
        }
    }
}
找规律，如果测试用例答案没错的话，我这个绝对不会超时，但是我觉得题目的测试用例答案错了，我本地暴力破解的代码在输出也是
5
0
2
2
3
1
1
5
0
1
,估计这个解真有问题
编辑于 2020-08-22 13:40:25 回复(1)
假的和平星头像 假的和平星
自测的案例能过，提交就是0% 超时。
难道是找规律？ 
#include<iostream>
#include<vector>
#include<string>
 
using namespace std;
int main()
{
    int m,a, b,c,n;
    cin >> m;
    while (m--)
    {
        string res,s;
        int i = 3;
        cin >> a >> b >> c >> n;
        res += to_string(a) += to_string(b) += to_string(c);
        while (i < n)
        {
            int tmp = res[2] - '0' + res[1] - '0' + res[0] - '0';
            s = to_string(tmp);
            i += s.size();
            res += s;
            res = res.substr(res.size() - 3, 3);
        }
 
        cout << res[n - i + s.size()] << endl;
    }
    return 0;
}


发表于 2020-07-24 17:18:17 回复(2)
C/C++
章鱼小八头像 章鱼小八 
int main()
{
    int T, i ,j;
    cin>>T;
    int f[6];
    int n;
    for(i = 0; i < T; i++){
        cin>>f[1]>>f[2]>>f[3]>>n;
        if(n >= 4){
            for(j = 4; j <= n; j++){
                f[4] = f[3] + f[2] + f[1];
                if(f[4] >= 10){
                    f[5] = f[4] % 10;
                    f[4] = f[4] / 10;
                    f[1] = f[3];
                    f[2] = f[4];
                    f[3] = f[5];
                    j++;
                }else{
					f[1] = f[2];
					f[2] = f[3];
					f[3] = f[4];
				}
            }
            if(n + 1 == j)
                cout<<f[3]<<endl;
            else
                cout<<f[2]<<endl;
        }
        else{
            cout<<f[n]<<endl;
        }
    }
    return 0;
}
思路就是 滚动数组，计算时间有点长。答案跟评论区的小伙伴是一样的
5 0 2 2 3 1 1 5 0 1


发表于 2020-06-22 15:50:37 回复(0)
zhoushengmeng头像 zhoushengmeng
2 6 8 972307520 用例的结果为6，但是推算一下
26816151281110235106713115713115713115713115713115713115713115713115713115713115713115713115713115713
可以看到后面是713115一直在重复，后面不可能出现6这个数字，所以这个用例有问题
编辑于 2020-05-11 21:15:34 回复(1)
江江321头像 江江321
这题答案有问题吧，求解答
用例：10 2 6 8 972307520 7 0 9 81366660 5 2 6 729532386 7 6 1 515853342 5 5 1 11691568 4 7 4 156507358 1 5 7 245505930 8 0 0 95224738 5 9 2 197774376 2 4 8 135229014  应该为：6 0 2 2 3 1 0 6 0 1 你的输出为：5 0 2 2 3 1 1 5 0 1



发表于 2020-05-04 23:54:43 回复(4)
布偶猫真好看头像 布偶猫真好看

时间复杂度超了，自测过了，大家帮忙看看

#include 
(849)#include 
using namespace std;

int main() {
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int a,b,c,n;
        cin >> a >> b >> c >> n;
        string str = "";
        str += to_string(a);
        str += to_string(b);
        str += to_string(c);
        int j = str.size();
        while(str.size() <= n) {
            int temp = (str[j-1] - '0') + (str[j-2] - &(6211)#39;0') + (str[j-3] - &(6212)#39;0');
            str += to_string(temp);
            j = str.size();
        }
        cout << str[n-1] << endl;
        str.clear();
    }
    return 0;
}
发表于 2020-05-03 10:39:37 回复(4)
提交观点

问题信息

C++工程师 深信服
来自：深信服校园招聘c/c ...
上传者：小小
难度：
13条回答 4161浏览

热门推荐

通过挑战的用户

相关试题

数字序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号