2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

时间:12-26来源:作者:点击数:40

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门