首页 > 试题广场 >

小q的数列

[编程题]小q的数列
  • 热度指数：9621 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：

f[0]=0 f[1]=1;
f[i]=f[i/2]+f[i%2];(i>=2)

现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n'] = f[n] = f[x/2]+f[x%2] = f[x]...（n'<n<x） 他们的值都相等，这里需要你输出最小的那个n'的值)(n<10^18)

输入描述:
输入第一行一个t
随后t行，每行一个数n，代表你需要求数列的第n项，和相应的n'
(t<4*10^5)


输出描述:
输出每行两个正整数
f[n]和n'，以空格分隔
示例1

输入

2
0
1

输出

0 0
1 1
算法知识视频讲解
添加回答
Python3
牛客783938631号头像 牛客783938631号
#对Python不是很友好
t = int(input())
for i in range(t):
    s = "{:b}".format(int(input()))
    f = s.count("1")
    print(f, end=" ")
    if f == 0:
        print(0)
    else:
        print(int("1" * f, base=2))
编辑于 2024-04-15 14:17:08 回复(0)
Python3
hyperal头像 hyperal
#运行超时，大家有好的办法吗
t = int(input())
for i in range(t):
    n = int(input())
    f = [0, 1]
    for j in range(2, n+1):
        f.append(f[j // 2] + f[j % 2])
    print(f[n], f.index(f[n]))
发表于 2022-12-17 17:29:57 回复(0)
提交观点

问题信息

递归
难度：
2条回答 1977浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小q的数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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