已知斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...(从第3个数字开始,每个数字等于它前两个数字之和)。如下例所示,斐波那契数列中的有些数可以被它各个数位上的数字之和整除(前几个斐波那契数本身是个位数,这个结果是显而易见的)。
2 --> 2÷2
3 --> 3÷3
5 --> 5÷5
8 --> 8÷8
21 --> 21÷3 ... 2+1=3,因而除以3
144 --> 144÷9 ... 1+4+4=9,因而除以9
请继续例中的计算,求出后续5个最小的能被整除的数。
这道题比较简单。简单地进行迭代循环即可:
计算斐波那契数列的常用技巧是,只记忆两个斐波那契数(当前cur和上一个prev),然后据此计算下一个nxt,然后再更新为cur->prev, nxt->cur。在python可以很方便用一条语句完成(参见以下代码)。
在以下代码中用两种方法实现了计算各个数位的数字之和Fk_digitSum的方法。
方法一是非常python-style的实现方法。将整数变换为字符串,再变换为list,然后再将列表元素(字符)变换回整数并求和。
方法二是常规且通用的循环迭代方法。每个循环中取当前值的个位数并求和,然后将当前值整除10得到新的当前值,直到当前值为0为止。
以上两个小代码片段充分体现了python的灵活性能够写出非常简洁的代码。
- # -*- coding: utf-8 -*-
- """
- Created on Tue Aug 31 08:23:22 2021
-
- @author: chenxy
- """
-
- import sys
- import time
- import datetime
- # import random
- from typing import List
- # from queue import Queue
- # from collections import deque
-
- class Solution:
- def fibonacci(self, N: int) -> List:
- """
- :N: The number of fibonacci number satisfying the condition to be searched
- :ret: The list of fibonacci number satisfying the condition
- """
-
- def digitSum(num):
- """
- :num: Input integer
- :ret: The sum of the digits of the input integer
- """
- # Alternative 1
- rslt = sum([int(s) for s in list(str(num))])
- # # Alternative 2
- # rslt = 0
- # while num > 0:
- # rem = num % 10
- # num = num // 10
- # rslt += rem
- return rslt
-
- ans = []
- prev,cur = 1,1
- k = 2
- cnt = 0
- while cnt < N:
- prev,cur = cur,prev+cur
- k = k + 1
- curDigitSum = digitSum(cur)
- if cur%curDigitSum == 0:
- ans.append((k,cur))
- cnt = cnt + 1
- return ans
- if __name__ == '__main__':
-
- sln = Solution()
-
- tStart = time.time()
- N = 11
- ans = sln.fibonacci(N)
- tCost = time.time() - tStart
- print('N={0}, tCost = {1:.3f}(sec)'.format(N,tCost))
- for item in ans:
- print('k={0:2d}, fibonacci={1}'.format(item[0],item[1]))
运行结果:
k= 8, fibonacci=21
k=12, fibonacci=144
k=18, fibonacci=2584
k=36, fibonacci=14930352
k=54, fibonacci=86267571272
k=72, fibonacci=498454011879264
k=84, fibonacci=160500643816367088