首页 > 试题广场 > 计算斐波那契数最小差值
[编程题]计算斐波那契数最小差值
  • 热度指数:1222 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个正整数n,计算n与斐波那契数的最小差值(绝对值)

说明:
斐波那契数定义:
                          从0,1开始后面的数值为前面两者之和, 即第三个数为第一和第二个数之和
                          形如:0,1,1,2,3,5,8,13,21。。。。  其中3为1与2的和,5为2与3的和,8为3与5的和等等
要计算的数值案例:
                          输入15,与斐波那契数相减,与13相减的绝对值是2,与21相减的绝对值是6,与众多斐波那契数相减的最小差值为2
                          因此输入15,输出2






输入描述:
输入任意正整数


输出描述:
数组正整数
示例1

输入

15

输出

2

说明

15与“0,1,1,2,3,5,8,13,21。。。。”当中的13差值的绝对值最小,与21的差值为6,与8的差值为7
n = int(input())
a = 0
b = 1
pre = min(abs(n - a),abs(n - b))
while True:
    c = a+b
    t = abs(n - c)
    if t > pre:
        print(pre)
        break
    else:
        pre = t
    a = b
    b = c    


发表于 2019-07-14 19:39:18 回复(0)
n = int(input())
fib = [0, 1]  # 保存两个值,方便做比较
while fib[1] < n:  # 当第二个fib大于或等于n时,退出循环
    temp_fib = fib[0] + fib[1]
    fib[0] = fib[1]
    fib[1] = temp_fib
print(min(n - fib[0], fib[1] - n))  # 选出较小的差值作为结果

发表于 2019-09-24 15:13:54 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,a,b;
    cin>>n;
    a = 0;
    b = 1;
    while(!(a<=n && n<=b)){
        int t = b;
        b = a + b;
        a = t;
    }
    cout<<min(n-a, b-n)<<endl;

    return 0;
}

发表于 2019-09-04 23:19:33 回复(0)
n = int(input())
a, b = 0, 1
while b < n:
    a, b = b, a + b
print(min(n - a, b - n))

发表于 2019-09-03 03:30:09 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,i=1,res=0;
    cin>>n;
    vector<int>num;
    num.push_back(0);
    num.push_back(1);
    if(n<=3)
    {
        cout<<0<<endl;
        return 0;
    }
    while(num[i]<n)
    {        
        i++;
        num.push_back(num[i-1]+num[i-2]);
    }
    res=min(abs(n-num[num.size()-2]),abs(n-num[num.size()-1]));
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-13 16:40:57 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] a){
        int n=new Scanner(System.in).nextInt();
        ArrayList<Integer> list=new ArrayList();
        for(int i=1;i<=n;i++){
            Integer num=i<=2?1:list.get(i-2)+list.get(i-3);
            list.add(num);
        }
        int cha=n;
        for(int i=0;i<n;i++){
            int abs=Math.abs(list.get(i)-n);
            if(abs<cha)
                cha=abs;
        }
        System.out.print(cha);
    }
}

发表于 2019-10-18 17:46:46 回复(0)
def fib(a):
    if a==0:
        return 0
    elif a==1:
        return 1
    else:
        f=fib(a-1)+fib(a-2)
        return f
n=int(input('输入一个正整数:'))
flag=0
while n>fib(flag):
    flag+=1
s0=abs(n-fib(flag))
s1=abs(n-fib(flag-1))
s=min(s0,s1)
print('{0}与第{1}和{2}位的斐波那契数最接近'.format(n,flag-1,flag))
print('{0}与斐波那契数的最小差值:{1}'.format(n,s))
发表于 2019-10-16 12:57:22 回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int a = 2, b = 3, c = 5;
    int n;
    cin>>n;
    if(n <= 3)
        cout<<0<<endl;
    else{
        while(n > c){
            c = a + b;
            a = b;
            b = c;
        }
        cout<<min(c-n, n-a)<<endl;
    }
    return 0;
}

发表于 2019-08-20 19:21:36 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int i=0,j=1;
        if(n==0){
            System.out.println(0);
            return;
        }
        while(true){
            int temp=j;
            j=i+j;
            i=temp;
            if(n>=i&&n<=j){
                System.out.println(Math.min(n-i,j-n));
                return;
            }
            
        }
        
    }
}

发表于 2019-08-08 13:51:20 回复(0)
import java.util.Scanner;
/*
 * 计算斐波那契数的最小差值
 */
public class Main {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int number = input.nextInt();
		if(number == 0) {
			System.out.println(0);
            return;
		}
		int a = 0;
		int b = 1;
		int n = a + b;
		while(n < number) {
			a = b;
			b = n;
			n = a + b; 
		}
		int result = (n - number) < (number - b) ? (n - number) : (number - b);
		System.out.println(result);
	}
}

编辑于 2019-08-05 20:13:58 回复(0)
#include<iostream>
using namespace std;
int main(){
    int f1 = 0,f2=1;
    int n = 0;
    while(cin>>n){
        while(f2<n){
            int temp = f2;
            f2 = f2+f1;
            f1 = temp;
        }
        cout<<((f2-n>n-f1)?(n-f1):(f2-n))<<endl;
    }
}

发表于 2019-07-28 20:53:07 回复(0)
n = int(input())
num = [0, 1]
i = 2
while num[-1] < n:
    m = num[i-1] + num[i-2]
    num.append(m)
    i += 1
res = min(abs(num[-1]-n), abs(num[-2]-n))
print(res)

发表于 2019-07-18 15:17:16 回复(0)