神奇的数列

[编程题]神奇的数列

热度指数：572 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

定义数列 f_n+2 = f_n+1 + f_n，数列中任何一个元素都是正整数。从定义可以看出，不同的f₁、f₂会产生不同的数列。

假设给定一个数字x（2 <= x <= 2³²)，给出这个数字出现在位置i（i >= 3, 数列下标从1开始）的数列个数。

输入描述:

数字x

输出描述:

每行为两个数字，空格分隔，第一个数字为x在数列中的位置i，第二个数字为符合条件的数列个数，即f₁、f₂的组合种数。若存在多行，则按照i由小到大的顺序输出

示例1

输入

输出

3 2
4 1

说明

以下数列包含3，分别为
1 1 2 3 5 ...
1 2 3 5 8 ...
2 1 3 4 7 ...

其中3出现在数列第三位的数列有两个，出现在第四位的数列有一个，因此输出为：
3 2
4 1

算法知识视频讲解

import sys
import collections

line = sys.stdin.readline().strip()
line = int(line)

dic = collections.defaultdict(int)
a,b = 1,1
for i in range(1,line):
    for j in range(1,line-a + 1):
        flag = 3
        c = i+j
        b = j
        while c < line:
            flag+=1
            tmp = c
            c = c + b
            b = tmp
        if c == line:
            dic[flag] += 1

for key in sorted(dic.keys()):
    print key,dic[key]

发表于 2022-03-27 16:21:35 回复(0)

步将-武德

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
long x;
long i = 1,j=1,start = 3;
Scanner sc = new Scanner(System.in);
x = sc.nextLong();
while (true){
long p=1;
while ((((x-i*p)%j)!=0) &&((i*p)<x)){
p+=1;
}
if ((i*p)>=x){
break;
}
System.out.println(start+" "+(long)Math.ceil((x-i*p)*1.0/(i*j)));
long tmp;
tmp=j;
j=i+tmp;
i =tmp;
start+=1;
}
}
}

发表于 2020-09-05 18:06:38 回复(0)

C/C++

201908121817285

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long x,i=1,j=1,start=3;
    cin>>x;
    while(true)
    {
        long long p=1;
        while((((x-i*p)%j)!=0)&&((i*p)<x))
            p+=1;
        if((i*p)>=x)
            break;
        cout<<start<<" "<<(long long)(ceil((x-i*p)*1.0/(i*j)))<<endl;
        long long tmp;
        tmp=j;
        j=i+tmp;
        i=tmp;
        start+=1;
    }
    return 0;
}

发表于 2020-07-28 11:27:01 回复(0)

usename6

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=47;
LL f[MAXN],n;
void init()
{
    f[1]=f[2]=1;
    for(int i=3;i<MAXN;i++)f[i]=f[i-1]+f[i-2];
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    LL tx,ty;
    LL d=exgcd(b,a%b,tx,ty);
    x=ty;
    y=tx-(a/b)*ty;
    return d;
}
int main()
{
    init();
    scanf("%lld",&n);
    for(int i=3;i<MAXN;i++)
    {
        LL x,y;
        if(f[i-2]>=n)break;
        LL d=exgcd(f[i-2],f[i-1],x,y);
        if(n%d)continue;
        LL dy=f[i-2]/d,dx=f[i-1]/d;
        bool flag1=false,flag2=false;
        x=x*(n/d);
        LL b=f[i-1];
        b=b/d;
        if(b<0)b=-b;
        x=x%b;
        if(x<=0)x+=b;
        y=(n-f[i-2]*x)/f[i-1];
        LL xx=n/f[i-2],yy=n/f[i-1];
        if(x>xx||y>yy)continue;
        if(n%f[i-2]==0)flag1=true;
        if(n%f[i-1]==0)flag2=true;
        LL mm=0,tp1,tp2;
        tp1=x/dx;tp2=abs(yy-y)/dy;
        if(flag2&&(abs(yy-y)%dy==0))tp2--;
        mm=mm+min(tp1,tp2);
        tp1=abs(xx-x)/dx,tp2=y/dy;
        if(flag1&&(abs(xx-x)%dx==0))tp1--;
        mm=mm+min(tp1,tp2);
        mm++;
        if(mm>0)printf("%d %lld\n",i,mm);
    }
    return 0;
}

发表于 2020-07-17 10:10:43 回复(2)

石郎

参见https://zhuanlan.zhihu.com/p/159238355

发表于 2020-07-14 02:33:54 回复(0)

谂小云

50%，之后应该是大数处理时，逻辑不能这么写，求大神指点。

import java.util.*;
public class Main{
    public static void main(String[] args){
    Scanner s = new Scanner(System.in);
    //System.out.println("请输入数字：");
    double sum = s.nextDouble();
    if(sum<2 || sum > (Math.pow(2,32))){
        System.out.println("输入超出界限");
    }
    else{
        
        Map<Integer ,Integer> map = new HashMap<Integer,Integer>();
        map = FeiBo(sum);
        for(int key : map.keySet()){
            int value = map.get(key);
    	    System.out.println(key+" "+value);
    	  }
    }
    }
    public static Map<Integer ,Integer> FeiBo(double sum){
        Map<Integer ,Integer> map = new HashMap<Integer,Integer>();
        int index = 0;
        int count = 0;
        for(double i = sum-1;i>sum/2;i--)//小于sum 1/2的数是不会有下一层的
                {
            index = 3;
            if(map.get(index)!=null){
                count = map.get(index);
            }
            else{
                count = 0;
            }
            map.put(index,count+1);
            //System.out.println("i是"+i+"index是"+index+"现在map3对应的是"+map.get(index));
            double j = sum - i;
            double temp = 0;
            double temp_i = i;
            while((temp_i-j)>0 && j >0){
                index++;
                if(map.get(index)!=null){
                    count = map.get(index);
                    }
                else{
                    count = 0;
                    }
                temp = temp_i - j;
                temp_i = j;
                j = temp;
                map.put(index,count+1);
                //System.out.println("temp_i是"+temp_i+"index是"+index+"现在map"+(index)+"对应的是"+map.get(index));
            }
        }
        return map;
    }
}

编辑于 2020-07-09 10:47:53 回复(1)

小朋友608

水平有限50%

#include<iostream>
#include<map>
using namespace std;
void getfib(int n, int i,map<int,int> &m){
    int index=2;
    int b=i;
    int l=n;
    int tmp=l-b;
    while(tmp>0){
        index++;
        l=b;
        b=tmp;
        if(m.count(index)){
            m[index]++;
        }else{m[index]=1;}
        tmp=l-b;
    }
}


int main(){
    int n; 
    cin>>n;
    map<int,int> m;
    for(int i=1;i<n;i++){
        getfib(n, i,m);
    }
    for(int i=2;i<=n+1;i++){
        if(m.count(i))
            cout<<i<<" "<< m[i]<<endl;
    }
    system("pause");
    return 0;
}

发表于 2020-07-08 22:25:44 回复(0)