首页 > 试题广场 >

小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

算法知识视频讲解

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

落日孤城

#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)

江街

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

段错误

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

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

#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)

池中物_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)

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

人间紫罗兰仙子

#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)