程序员的算法趣题Q11: 斐波那契数列

1. 问题描述

已知斐波那契数列：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个最小的能被整除的数。

2. 解题分析

这道题比较简单。简单地进行迭代循环即可:

1. (以前两个1为初始条件开始)计算下一个斐波那契数Fk
2. 计算斐波那契数的各个数位的数字之和Fk_digitSum
3. 判断Fk是否能被Fk_digitSum整除

计算斐波那契数列的常用技巧是，只记忆两个斐波那契数（当前cur和上一个prev），然后据此计算下一个nxt，然后再更新为cur->prev, nxt->cur。在python可以很方便用一条语句完成（参见以下代码）。

在以下代码中用两种方法实现了计算各个数位的数字之和Fk_digitSum的方法。

方法一是非常python-style的实现方法。将整数变换为字符串，再变换为list，然后再将列表元素（字符）变换回整数并求和。

方法二是常规且通用的循环迭代方法。每个循环中取当前值的个位数并求和，然后将当前值整除10得到新的当前值，直到当前值为0为止。

以上两个小代码片段充分体现了python的灵活性能够写出非常简洁的代码。

3. 代码及测试

# -*- 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