目錄
1. 問題描述
2. 解題分析
3. 代碼及測驗
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為初始條件開始)計算下一個斐波那契數Fk
- 計算斐波那契數的各個數位的數字之和Fk_digitSum
- 判斷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 ansif __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
上一篇：Q10: 輪盤的最大值
下一篇：
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296500.html
標籤：其他