首页 > 试题广场 >

小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

算法知识视频讲解

C++

Spectre_

#include<iostream>
using namespace std;

int main() {
    long n, cnt;
    cin >> n;
    while (cin >> n) {
        cnt = 0;
        while (n) {
            if (n & 1) ++cnt;
            n >>= 1;
        }
        cout << cnt << " " << (1l << cnt) - 1 << endl;
    }
    return 0;
}

发表于 2022-04-01 22:08:21 回复(0)

牛客688983736号

#include <stdio.h>
#include <math.h>

int main(){
    int t, count;
    long n;
    scanf("%d", &t);
    for(int i = 0; i < t; i++){
        scanf("%ld", &n);
        count = 0;
        while(n){
            count += n & 1 == 1? 1 : 0; //对应二进制1的个数  
            n >>= 1;           
        }
        printf("%d %ld\n", count, (long)pow(2, count) - 1);
    }
    return 0;
}
/*f(n)结果就是对应n二进制中1的个数，n’就是最早出现对应个数1的那个;
 (110 101 1010....都是两个1, 结果都是2，最早的应该是二进制为11);
eg : f(n) = 1 最早满足的就是二进制 1 ---- n' = 1    (2 ^ 1 - 1);
     f(n) = 2 最早满足的就是二进制11 ---- n' = 3    (2 ^ 2 - 1);
---> f(n) = x 最早满足的就是二进制为x个全1 ---- n' = (2 ^ x - 1); 
*/

发表于 2022-06-17 16:29:59 回复(1)

牛客618310257号

#include<stdio.h>

#include<math.h>

int main(){

long long int a,f[4000000]={};

scanf("%lld\n",&a);

for(long int c=1;c<=a;c++){

long int n;

scanf("%ld",&n);

long int sum=0;

while(n!=0){

sum+=n%2;

n/=2;

}

long int k=sum,aa=0,ab=0;

for(k=sum;k>=1;k--){

aa+=pow(2,ab);

ab++;

}

printf("%ld %ld\n",sum,aa);

}

return 0;

}

发表于 2025-08-19 23:46:55 回复(0)

Java

Sen🍓🍀

注释里有【】超时报错，不加就通过

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextInt();
 
        while (in.hasNextLong()) {  //  注意：超时是这里出问题
            long n = in.nextLong();
            String s = Long.toBinaryString(n);
            long fn = s.length() - s.replaceAll("1", "").length();
            // 1l(long) 或 1L(Long)    注意：结果不对是这里有问题
            long n1 = (1l << fn) - 1;
            System.out.println(fn + " " + n1);
        }
    }
}

发表于 2025-01-26 16:12:33 回复(0)

简小淼

//下面是解释

//我们先全部求解，发现偶数就是f[x/2]，奇数就是f[(x-1)/2]+1;

//然后很自然的想到递归函数fff

//然后接下来就是找位置了

//全部列出来，然后找规律，我们发现只要下一项拆解到了奇数就会有加一的操作，所以我们联想和奇数的关系

//然后就发现只要拆解到奇数

//1:2*1-1 2*次数-1

//3:2*2-1

//5:2*2-1

//7:2*2*2-1

//然后结合f15，f31就发现了规律

//由于偶数默认传递过来的时候，我们最后都会拆到1，但是1又没有实际作用，所以return mmm

//奇数拆到1还要加1，所以我们return mmm+1

//是不是很奇妙呢，我也这样觉得，求佛啊求佛，开始暴力计算，结果段错误，不允许我用这么长的数据 //闪开！
作者：简小淼
链接：https://www.nowcoder.com/discuss/698214049787514880
来源：牛客网

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

long search(long m,int step)

{

if(m==0||m==1)

return m;

if(m==2)

return 1;

long mmm=step;

long mm=m;

while(m!=0&&m!=1)

{

if(m/2%2==0)

{

m=m/2;

}

else

{

mmm++;

m=m/2;

}

if(mm%2==0)

return mmm;

else

return mmm+1;

}

long fff(long m)

{

if(m==0||m==1)

return m;

else if(m%2==0)

{

return fff(m/2);

}

else

{

return fff(m/2)+1;

}

int main() {

long a;

int m;

int step=0;

scanf("%d",&m);

while(m--)

{

scanf("%ld",&a);

step=0;

printf("%ld %ld\n",fff(a),(long)pow(2,(search(a,step)))-1);

}

return 0;

}

发表于 2024-12-16 16:54:45 回复(1)

saierhao

 void Series_Number(int* p,int t)
{
	int i = 0;
	for (i = 0; i < t;i++)
	{
		if (i < 2)
		{
			*(p + i) = i;
		}
		else if (i >= 2)
		{
			*(p + i) = *(p + (i / 2)) + *(p + (i % 2));
		}
	}
	for (i = 0; i < t; i++)
	{
		int red = 0;
		int ret = i;
		while (ret)
		{
			ret = ret & (ret - 1);
			red++;
		}
		printf("%d %ld", *(p + i),(long)pow(2,red)-1);
		printf("\n");
	}
}
int main()
{
	int arr[400000] = { 0 };
	int t = 0;
	scanf("%d", &t);
	int i = 0;
	for (i = 0; i < t; i++)
	{
		scanf("%d", &arr[i]);
	}
	Series_Number(arr,t);
	return 0;
}
//不是你这题，30几万的数字有什么意义吗，纯纯浪费时间

发表于 2024-09-03 18:25:15 回复(0)

Amity_L

#include <cmath>
#include <iostream>
#include <math.h>
using namespace std;

int main() 
{
    long a;
    long cnt;
    cin >> a;
    while(cin >> a)
    {
        cnt = 0;
        while(a)
        {
            if(a & 1)
                ++cnt;
            a >>= 1;
        }
        cout << cnt << " " << (long)pow(2, cnt) - 1 << endl;
    }
}

发表于 2024-05-15 21:00:36 回复(0)

Python3

牛客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)

落日孤城

#include <stdio.h>

int main() {
int n;
scanf("%d",&n);
int o[350000];
o[0]=0;
o[1]=1;
for(int i=2;i<=349958;i++){
if(i%2==0){
o[i]=o[i/2];
}else {
o[i]=o[i/2]+1;
}
}
while(n){
int a;
scanf("%d",&a);
for(int i=0;i<=a;i++){
if(o[i]==o[a]){
printf("%d %d\n",o[i],i);
break;
}
}
n--;
}
} 这个代码自己输入一些简单的，好像都对，但是提交它显示段错误，段错误是什么鬼啊

发表于 2024-04-05 16:00:34 回复(0)

JayneChou

#include <math.h>
#include <stdio.h>
int func(long num);

int main() {
    int round, value;
    long sequence_Num, first_num;
    scanf("%d", &round);
    while (round--) {
        scanf("%ld", &sequence_Num);
        value = func(sequence_Num);
        //由于value即sequence_Num二进制中1的个数,那么first_num最小值即为11...1全1的情况,且个数为value;
        first_num = pow(2.0, value*1.0) - 1;
        printf("%d %ld\n", value, first_num);
    }
    return 0;
}

int func(long num) {
    int value = 0;
    while (num) {
        //将num看成二进制,则value即为num二进制中1的个数,这很关键
        if (num & 1) {
            value++;
        }
        num >>= 1;
    }
    return value;
}

发表于 2024-01-12 13:01:12 回复(0)

keepyang

go 处理输入是真不行..

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    // "strings"
)

// fmt.Scan fmt.Fscan 都超时..
func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var n int
    fmt.Fscan(os.Stdin, &n)

    for i := 0; i < n; i++ {
        var t int
        // fmt.Fscan(os.Stdin, &t)
        s, _ := r.ReadString('\n')
        t,_ = strconv.Atoi(s[:len(s)-1])
        cnt := 0
        for t > 0 {
            if (t & 1) == 1 {
                cnt++
            }
            t >>= 1
        }
        //fmt.Fprintf(os.Stdout, "%d %d\n", cnt, (1<<cnt)-1)
        w.WriteString(strconv.Itoa(cnt))
        w.WriteByte(' ')
        w.WriteString(strconv.Itoa((1 << cnt) - 1))
        w.WriteByte('\n')
    }
}

编辑于 2023-12-26 06:36:35 回复(0)

江街

不知道为什么测试出现段错误

段错误

您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起

球球大佬帮帮孩子找找问题在哪里>-<

#include <stdio.h>

int main() {

long t, min = 0;

scanf("%ld", &t);

long f[40000] = {0,1};

for (int i = 2; i < 40000; i++) {

f[i] = f[i / 2] + f[i % 2];

}

for (int o = 0; o < t; o++) {

long n;

scanf("%ld", &n);

for (int i = 0; i <= n; i++) {

if (f[i] == f[n]) {

min = i;

break;

}

printf("%ld %ld\n", f[n], min);

}

return 0;

}

发表于 2023-07-21 10:49:49 回复(1)

追梦_浅暮之殇

#include <stdio.h>
#include<math.h>
long long num(long long n)
{
    if(n<2)
    return n;
    else
     return num(n/2)+num(n%2);
}
int main() {
    long long t=0;
    long long n=0;
    long long m=0;
    long long i=0;
    long long j=0;
    scanf("%lld",&t);
    for(i=0;i<t;i++)
    {
        scanf("%lld",&n);
        m=num(n);
        long long x=pow(2,m)-1;
        printf("%lld %lld\n",m,x);
    }
    return 0;
}

发表于 2023-02-22 21:51:06 回复(0)

Python3

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)

池中物_2024

#include <stdio.h>
long f(long x)
{
    long f[400000];
    f[0] = 0;
    f[1] = 1;
    for(long i = 0; i <= x; i++)
    {
        f[i] = f[i/2]+f[i%2];
    }
    return f[x];
}

long n_min(long x, long l)
{
    long f[400000];
    f[0] = 0;
    f[1] = 1;
    long i;
    for(i = 0; i <= l; i++)
    {
        f[i] = f[i/2]+f[i%2];
        if(f[i] == x)
        {
            break;
        }
    }
    return i;
}

int main()
{
    long t;
    long n[400000];
    scanf("%ld", &t);
    for(long i = 0; i < t; i++)
        scanf("%ld", &n[i]);
    for(long i = 0; i < t; i++)
    {
        long f_out, n_1;
        f_out = f(n[i]);
        n_1 = n_min(f_out, i);
        printf("%ld %ld\n", f_out, n_1);
    }
    return 0;
}

发表于 2022-07-06 14:47:37 回复(2)

人间紫罗兰仙子

#include<stdio.h>

int main(void)
{
    long long i, j, t, temp, n, m, s;
    scanf("%lld", &t);
    for (i = 0; i < t; i++) {
        scanf("%lld", &temp);
if(temp<0){break;}
        n = 0, m = 0;
        while (temp) {
            if (temp % 2 == 1) { n++; }
            temp /= 2;
        }
        s = 1;
        for (j = 0; j < n; j++) {
            m += s;
            s *= 2;
        }
        printf("%lld %lld\n", n, m);
    }
}

发表于 2022-03-15 17:20:26 回复(0)

阿金要努力

#include<stdio.h>
#include<math.h>
int main()
{
    long long t=0;
    scanf("%lld",&t);
    long long n=0;
    while(t--)
    {
        scanf("%lld",&n);
        long long count=0;
        while(n)
        {
            n&=(n-1);
            count++;//每次n&n-1，就会消去一个1，所以当n=0,与运算几次，二进制中有几个1；
        }
        printf("%lld %lld\n",count,((long long)pow(2,count)-1));
    }//而n'就是2的二进制中1的个数次方再减1；
    return 0;
}

发表于 2022-03-10 17:28:34 回复(0)

C++

happy天堂

#include <stdio.h>

int main()
{
    long long i = 0;
    long long t = 0;
    long long sum=0;
    long long num=0;
    long long temp = 0;
    long long min = 0;
    scanf("%d", &t);
    while (t--)
    {
        sum=0;
        num=0;
        scanf("%lld", &temp);
        while(temp)             //temp的二进制形式中1的个数即为f(temp)的值，每一位都找一下
		{
			if(temp&1)
            {
                sum++;
            }
			temp=temp>>1;
		}
        for(i=0;i<sum;i++)     //最早出现的项与二进制中1的个数有关
        {
            num=num*2+1;
        }
        printf("%lld %lld\n",sum,num);
    }
    return 0;
}

发表于 2022-03-06 23:11:52 回复(0)

C++

virteki73

#include <iostream>
using namespace std;
typedef long long ll;
ll lowbit(ll x)
{
    return x & -x;
}
int main()
{
    ll t, n;
    scanf("%lld", &t);
    while (t -- )
    {
        scanf("%lld", &n);
        ll res = 0;
        while (n) n -= lowbit(n), res ++;
        cout << res << ' ';
        ll n_hat = 1;
        while (res -- ) n_hat *= 2;
        cout << n_hat - 1 << endl;
         
    }
}

发表于 2022-02-26 20:59:38 回复(0)