2019_Fibonacci数列与黄金分割

2019_初赛数列求值

day03

题目描述

Fibonacci数列与黄金分割

数列求和

给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求 第20190324 项的最后4 位数字。

题目分析

第一道题，黄金分割，经过测试，在n达到一定值的时候最后结果均为0.61803399

第二道题，变异的Fibonacci数列，只需要得到最终的结果

这两道题目都很类似，给出超大的数来求最终结果，用普通的递归肯定是不行的，

第二道题，既要保证时间不会太长，而且要占用内存要小

题解

###　Fibonacci数列与黄金分割

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

n = eval(input())

def f(n):
    if n==1:
        return 1
    if n==2:
        return 1
    return f(n-1) + f(n-2)

if n > 25:
    print('0.61803399')
else:
    print('%.8f'%(f(n)*1.0/f(n+1)))

数列求和

因为题目要求要最后4位数字，所以每次计算只需要对10000取余数即可，而且20190324是一个不小的数字，为了使内存占用足够小，每次数组中只保留前后三个数即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def f(n):
    F = [0,1,1,1]
    if n <=3:
        return F[n]
    else:
        for i in range(n-3):
            F.append((F[-1] + F[-2] + F[-3])%10000)
            del F[-4]
            if i%100000==0:
                print(i)
        return F[-1]
        
print(f(20190324))