首页 > 试题广场 >

Fibonacci数列

[编程题]Fibonacci数列

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

Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

输入描述:

输入为一个正整数N(1 ≤ N ≤ 1,000,000)

输出描述:

输出一个最小的步数变为Fibonacci数"

示例1

输入

输出

算法知识视频讲解

Python

华科平凡

python solution:

num = int(input())
arr = [0, 1, 1]
while num > arr[-1]:
    arr.append(arr[-1] + arr[-2])

print(min(arr[-1] - num, num - arr[-2]))

发表于 2017-11-02 09:56:06 回复(3)

Python

wyy998

n = int(input())
a, b = 0, 1
while n >= b:
    a, b = b, a + b
print(min([b - n, n - a]))

发表于 2018-03-13 16:56:18 回复(1)

Miyagi11

很蠢的做法。。

#include <stdio.h>
int fi[100];
int main() {
    fi[0]=0;
    fi[1]=1;
    for(int i=2; i<=35; i++) {
        fi[i]=fi[i-1]+fi[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF) {
        int left_ans=n;
        int right_ans=n;
        int ans=0;
        bool flag=true;
        while(flag) {
            for(int i=0; i<=35; i++) {
                if(left_ans==fi[i]||right_ans==fi[i]) {
                    flag=false;
                    break;
                }
            }
            left_ans--;
            right_ans++;
            ans++;
        }
        printf("%d\n",ans-1);
    }
    return 0;
}

发表于 2018-02-21 11:26:54 回复(0)

卒子

#include<iostream>
 
using namespace std;
 
int main() {
    int N;
    cin>>N;
     
    // a, b, b, b
    // 0, 1, 1, 2
    int a = 0, b = 1;
    while(N > b) {
        int tmp = a;
        a = b;
        b += tmp;
    }
     
    //cout<<"a= "<<a<<" b = "<<b<<endl;
    cout<<min(N-a, b-N)<<endl;
     
    return 0;
}

发表于 2017-11-29 12:02:49 回复(0)

Java

指offer的剑在哪？

本题其实也就是寻找最短路径，给出一个值，找出F数中与该值相隔最小的数之间的距离值，通过将所有的F数进行依次判断并将距离值设置成正数进行比较即可找到最终结果

import java.util.Scanner;

public class Main {

    //F数
    public static void main(String[] args) {

        int f[] = new int[1000];
        f[0] = 0;
        f[1] = 1;

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int dis = n-f[1];
        if(dis < 0){
            dis = -dis;
        }
        int i = 2;
        while(true){
            f[i] = f[i-1] + f[i-2];
            int temp = n-f[i];
            if(temp < 0){
                temp = -temp;
            }
            if(temp > dis){
                System.out.println(dis);
                return ;
            }
            dis = temp;
            i++;
        }
    }

}

发表于 2017-08-31 10:56:08 回复(0)

AndyCui

#include<iostream>
#include<stdio.h>
using namespace std;

//定义Fibonacci数的函数
int Fibonacci(int N)
{
	if (N == 0)
		return 0;
	else if (N == 1)
		return 1;
	else
		return Fibonacci(N - 1) + Fibonacci(N - 2);
}

int main()
{
	int N;
	cin >> N;
	int num=0;
//这里i的值设置大一点没关系，因为Fibonacci函数必然在一个点大于N
	for (int i = 0; i < 100000; i++)
	{
		if (Fibonacci(i) - N > 0)
		{
			num = i;
			break;
		}
	}
//看前一个还是后一个Fibonacci数距离N近一些
	if (Fibonacci(num) - N < N - Fibonacci(num - 1))
		cout << Fibonacci(num) - N;
	else
		cout << N - Fibonacci(num - 1);
	return 0;
}

发表于 2016-08-16 16:19:15 回复(1)

C/C++

999JUICE999

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>


int Fibonacci(int n)
{
    if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

int main()
{
    int N = 0;
    scanf("%d", &N);
    int i = 0;
    int x = 0;
    int num = 0;
    for (i = 1; i < 100; i++)
    {
        if (N<Fibonacci(i + 1) && N>Fibonacci(i))
        {
            if ((Fibonacci(i + 1) - N) < (N - Fibonacci(i)))
            {
                while (N++)
                {
                    num++;
                    if (Fibonacci(i + 1) == N)
                    {
                        printf("%d", num);
                        return 0;
                    }
                }
            }
            else
            {
                while (N--)
                {
                    num++;
                    if (Fibonacci(i) == N)
                    {
                        printf("%d", num);
                        return 0;
                    }
                }
            }
        }
        else if (N == Fibonacci(i))
        {
            printf("%d", x);
            return 0;
        }
    }
    return 0;
}

发表于 2022-04-12 15:04:23 回复(0)

小周好饿

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int a=0,b=1,c=1,num=0;
        if(n<=2)
            num=0;
        else{
        while(c<n)
        {
            c=a+b;
            num=b;
            a=b;
            b=c;
        }
            num=(n-num)>(c-n)?(c-n):(n-num);
        }
        cout<<num<<endl;
    }
    return 0;
}

找到n前一个Fibonacci数和后一个Fibonacci数，比较差就好了

发表于 2019-11-12 20:05:41 回复(0)

fo0bar

好久不用三目了。。。

运行时间：10ms

占用内存：492k

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin>>N;
    int n1 = 0;
    int n2 = 1;
    int num=0;
    while(num<N)
    {
        num = n1 + n2;
        n1 = n2;
        n2 = num;
    }
    if(num == N)
        cout<<0;
    else // num > N
        cout << ((num-N > N-n1)? (N-n1):(num-N));
    return 0;
}

编辑于 2019-04-18 16:27:35 回复(0)

来啦来啦来啦

n = int(input())
fib = [1,1,2]
while fib[-1] < n:
fib.append(fib[-1]+fib[-2])
print(min(abs(n-fib[-1]), abs(n-fib[-2])))

发表于 2019-04-17 22:20:09 回复(0)

范尼斯特尔鲁一

import java.util.Scanner;

public class Main {

    public static void main(String[] args)
    {
        int i=0;
        int j=1;
        int sum=0;
        int k=2;
        int [] arr=new int[47];
        arr[0]=0;
        arr[1]=1;
        for(;(sum<2000000000)&&(k<47)&&(sum>=0);)
        {
            sum=i+j;
            arr[k++]=sum;
            i=j;
            j=sum;
        }
        Scanner s=new Scanner(System.in);
        int intaa=s.nextInt();
        int min=Integer.MAX_VALUE;
        for(int kk=0;kk<47;kk++)
        {
            if(Math.abs(intaa-arr[kk])<min)
            {
                min=Math.abs(intaa-arr[kk]);
            }
        }
        System.out.print(min);
    }
}

发表于 2018-08-26 10:44:11 回复(0)

YY-帆S

<?php
//题目就是为了求离$n最近的斐波那契数
$num = trim(fgets(STDIN));
//递推斐波那契数列
$one = 0;
$two = 1;
while(true){
    $three = $one + $two;
    if($three <= $num) $min = $three;
    else {
        $max = $three;
        break;
    }
    $one = $two;
    $two = $three;
}
echo ($num-$min)>($max-$num)?$max-$num:$num-$min;

发表于 2018-07-28 22:42:18 回复(0)

詹姆斯23号

#include<iostream>
using namespace std;

int fibonacci(int num){
if(num<=0) return -1;
if(num==1) return 0;
if(num==2) return 1;

int last2=0;
int last1=1;
int current=1;
for(int i=3;i<=num;i++){
current=last2+last1;
last2=last1;
last1=current;
}
return current;
}
int main(){
int N;
cin>>N;
int i=0;
while(true){
if(fibonacci(i)>N){
break;
}else{
i++;
}
}

cout<<min(N-fibonacci(i-1),fibonacci(i)-N);
return 0;
}

发表于 2018-06-30 18:14:31 回复(0)

Java

vic0707

---------------------------------------Java---------------------------------


import java.util.Scanner;
public class Main{
    public static void main(String[] args)
    {
        Scanner in =new Scanner(System.in);
        
        System.out.println(getResult(in.nextInt())); 
    }

    public static int getResult(int N)
    {
        int i=0,flag1=0,flag2=0;
        for(;;i++)
        {//寻找输入值N处于哪两个fibo数之间
            flag2=fibo(i);
            if(flag2>N)
                break;
            flag1=flag2;
        }
        return N-flag1>flag2-N?flag2-N:N-flag1;//输出结果
    }

    public static int fibo(int number)//递归斐波那契
    {
        if(number==0 || number == 1)
            return number;
        else
            return fibo(number-1)+fibo(number-2);
    }
}

编辑于 2018-05-04 18:28:42 回复(1)

童珉

#include <iostream>
using namespace std;

int main(){
    int N; cin>>N;
    int f1=0, f2=1;
    while(N>f2){
        f2=f1+f2;
        f1=f2-f1;
    }    
    cout<<min(f2-N, N-f1)<<endl;
    return 0;
}

发表于 2018-04-13 22:17:37 回复(0)

Python

LSur

def fibo(fi,x):
a = x-1
b = x-2
fi.append(fi[a] +fi[b])
return fi[x]

def minstep(fi,minsub):
for x in fi:
sub = abs(x-n)
if sub < minsub:
minsub = sub

return minsub

fi = [0,1]
maxfi = 1
index = 1
minsub = 99999999
n = int(input())
if n<=maxfi:
print(minstep(fi,minsub))
else:
while n>maxfi:
index += 1
maxfi = fibo(fi,index)

print(minstep(fi,minsub))

分享一个比较常规的解法，然后再去学习一些大神的解法

学习到的一个大道至简的写法，5行Python大法好：
n = int(input())
f1,f2 = 0,1
while n>f2:
    f1,f2 = f2,f1+f2
print(min(f2-n,abs(n-f1)))

编辑于 2018-04-07 09:11:13 回复(0)

我就是大蹭蹭

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s1 = 0, s2 = 1;
        while(s2 <= n){
            int s3 = s1 + s2;
            s1 = s2;
            s2 = s3;
        }
        System.out.println((s2-n)>(n-s1)?n-s1:s2-n);
    }

发表于 2018-02-24 17:49:23 回复(0)

但为君故沉吟至今

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = 0;
        int b = 1;
        int res = 0;
        while (true) {
            res = a + b;
            a = b;
            b = res;
            if (res > n)
                break;
        }
        System.out.println((res - n) > (n - a) ? (n - a) : (res - n));
    }
}

发表于 2018-01-31 21:26:13 回复(0)

Jason_liu


	import java.util.Scanner;



	public class Main {



	





	    public static void main(String[] args) {



	        Scanner sc=new Scanner(System.in);



	        while(sc.hasNext()) {



	            int n=sc.nextInt();



	            int a=0,b=1,x=a+b,y;



	            while(x<n) {



	                a=b;



	                b=x;



	                x=a+b;



	            }



	            System.out.println(Math.min(x-n, n-b));



	        }



	    }



	





	}

发表于 2018-01-31 09:24:31 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int N,a=0,b=1,c,left,right;     cin>>N;     while(1)     {         c = a + b;         a = b;         b = c;         if(c < N)             left = N - c;         else{             right = c - N;             break;         }     }     cout<<min(left, right)<<endl;     return 0;
}