首页 > 试题广场 >

Fibonacci数列

[编程题]Fibonacci数列
  • 热度指数：37894 时间限制：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

输入

15

输出

2
算法知识视频讲解
添加回答
Python
spongebob7头像 spongebob7
n = int(input())
a,b=0,1
while True:
    tmp=a
    a=b
    b=a+tmp
    if b>=n:
        print(min(b-n,n-a))
        break

    
编辑于 2021-04-01 17:38:33 回复(0)
Python
12313242头像 12313242 
num = eval(input())
step = 0
f1 = 0
f2 = 1
f3 = f1 + f2
while f3 < num:
    f1, f2 = f2, f3
    f3 = f1 + f2
print(min(num-f2, f3 - num))


编辑于 2021-02-16 20:13:30 回复(0)
Python
cavature头像 cavature 
k = int(input())

l=[0,1]
while l[-1] < k:
    l.append(l[-1]+l[-2])

diff = []
for i in l:
    diff.append(abs(k-i))
    
print (min(diff))

发表于 2019-09-14 10:01:50 回复(0)
Python
Dayanghe头像 Dayanghe

就是求离inputs最近的斐波拉契数，之后求这个数与inputs距离多远 

while True:
    try:
        inputs = int(input())
        a,b= 0,1
        while inputs > b:
            a,b = b,b+a
        print (min(inputs-a,b-inputs))
    except:break
编辑于 2019-07-14 09:35:33 回复(0)
Python
lx的流星头像 lx的流星 
while True:
    try:
        num=int(input().strip())
        #print(num)
        f1=0
        f2=1
        f=f1+f2
        if num==1:
            print(0)
        else:
            while f<num:
                f=f1+f2
                f1=f2
                f2=f
                if f<num:
                    min_num=num-f
                else:
                    max_num=f-num
                    break
            result=min(min_num,max_num)
            #list1=[]
            print(result)
    except:
        break
发表于 2019-06-04 13:06:37 回复(0)
Python
不上岸就不改名头像 不上岸就不改名 
n=input()
n=int(n)
f=[0,1]
derta=[]
i=1 while f[i]<1000000:
    i = i + 1  f.append(f[i-1]+f[i-2])
    derta.append(abs(f[i]-n))
derta=sorted(derta) print(derta[0])
发表于 2018-12-30 22:15:45 回复(0)
Python
WhiteGL头像 WhiteGL 
n = int(input())
s = 0
b = 1
new = 0
while new < n:
    new = s + b
    s = b
    b = new

print(min((new - n), (n - s)))
在循环里生成fib数，不需要储存数列，只要寻找到n附近的fib数就可以，然后比较n与较大和较小数之间的差就可以
发表于 2018-10-06 15:43:31 回复(0)
Python
三三四四萨达头像 三三四四萨达 
n = input()
x, y = 0, 1
while y < n:
 x, y = y, x + y
 print(min(y - n, n - x))

编辑于 2018-10-03 17:57:04 回复(0)
Python
Prominent头像 Prominent 
num = int(input().strip())
fib = [1,1]
while True:
    if fib[1] >= num:
        print(min(fib[1]-num,num-fib[0]))
        break
    else:
        fib[1],fib[0] = fib[1]+fib[0],fib[1]

编辑于 2018-09-07 20:53:07 回复(0)
Python
诸葛小愚头像 诸葛小愚 
#分别算出n前后的斐波拉契数，然后返回差值最小的
n=int(input())
def fib(n):
    Max,Min=0,0
    a,b=0,1
    while a<=n:
        Min=a
        a,b=b,a+b
    Max=a
    return min(n-Min,Max-n)
print(fib(n))

发表于 2018-08-12 16:39:56 回复(0)
Python
Zoom内推助手头像 Zoom内推助手 
def Fibonacci():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a+b


n = int(input())
pre, cur = 1, 1    
for each in Fibonacci():
    cur = each
    if cur > n:
        break
    pre = cur
print(min(abs(n-pre), abs(n-cur)))

发表于 2018-08-02 13:30:17 回复(0)
Python
离疏头像 离疏 
N=int(input())

x = 0
y = 1
while y<N:
    x,y=y,x+y
ans=min(y - N, N - x)
print(ans)

发表于 2018-04-30 13:01:38 回复(0)
Python
LSur头像 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)
Python
wyy998头像 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)
Python
杨云同学头像 杨云同学 
n = int(input())
x = y= 2
for i in range(1000000):
    x,y = y,x+y
    if n>=x & n<=y:
         break
print(min(n-x,y-n))

发表于 2018-02-28 12:05:44 回复(0)
Python
RhythmLian头像 RhythmLian 
"""看到dalao们什么最短路啊 快速幂的 有点受惊吓 这就是道水题啊"""
def judge(n):
    x,y=0,1
    while y<n:
        x,y=y,x+y
    print(min(y-n,n-x))
judge(int(input()))


"""也可以这样嘛“”“


	def dfs(a,b,c):





	    if c<b:





	        print(min(c-a,b-c))





	    else:





	        dfs(b,a+b,c)





	num=int(input())





	dfs(0,1,num)

编辑于 2018-03-04 21:49:22 回复(0)
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
人民的名义头像 人民的名义
python：利用常规求斐波那契数的方法求得大于和小于N的数，然后比较哪个更近 
def nStep(N):
    fn0=0
    fn1=1
    fn=0
    #计算斐波那契数，直到大于当前值才停止 ，由于使用 的是迭代 方法求得的斐波纳，因此容易得知小于N的斐波那契数
    while  N>fn:
        fn=fn0+fn1
        fn0=fn1
        fn1=fn
    df1=N-fn0
    df2=fn-N
    #判断前后两个斐波纳数哪个离N比较近
    if N==fn:
        return 0
    elif df1>df2:
        return df2
    else:
        return df1
if  __name__=='__main__':
    n=int(input())
    print(nStep(n))

编辑于 2017-10-20 16:05:57 回复(0)
Python
L.W.M头像 L.W.M 
n = int(input())
left =0   #构造三个中间变量
mid = 1
right = 0
if n ==1:
    print(0)
if n>=2:
    for i in range(2,n+1):
        right = left+mid   #为了不内存溢出  采用换数操作
        left = mid
        mid = right
        if right>=n:    #中止循环条件
            break
    print(min(n-left,right-n))  #求最小值，这里用left  因为left来自于原始的mid

发表于 2017-09-13 21:01:54 回复(0)
Python
langwangsong头像 langwangsong 
跟有人的方法类似：原理就是找到两个连续的Fibonacci数，
并且我们输入的那个数就是在这两个Fibonacci数之间，
然后输出较小的绝对值
s=int(input())
m=0
n=1
while n <= s:
    b=m+n
    m=n
    n=b
if abs(s-m) > abs(s-n):
    print (abs(s-n))
else:
    print (abs(s-m))

编辑于 2017-09-05 20:08:19 回复(0)
提交观点

问题信息

模拟 数学
来自：网易2017内推笔试编...
难度：
22条回答 34798浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Fibonacci数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号