page contents

python基础编程100例:第86期-基础算法:递归 3的幂

本文讲述了python基础编程100例:第86期-基础算法:递归 3的幂!具有很好的参考价值,希望对大家有所帮助。一起跟随六星小编过来看看吧,具体如下:

attachments-2022-04-Y8llHQZC624a51a406fc4.png

本文讲述了python基础编程100例:第86期-基础算法:递归 3的幂!具有很好的参考价值,希望对大家有所帮助。一起跟随六星小编过来看看吧,具体如下:

第86期-基础算法:递归 3的幂

1 问题描述

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false 。

整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x


示例 1:

输入: n = 27

输出: true


示例 2:

输入: n = 0

输出: false


示例 3:

输入: n = 9

输出: true


示例 4:

输入: n = 1

输出: true


初始代码

from typing import List

class Solution:

    def isPowerOfThree(self, n: int) -> bool:

        #在此之间填写代码


print(Solution().isPowerOfThree(27))

print(Solution().isPowerOfThree(0))

print(Solution().isPowerOfThree(9))

print(Solution().isPowerOfThree(1))


2 解题思路

标签:递归

判断该数是否可以整除3,若可以,再判断除以3后得到的数是否也可以整除3

若可以一直下去直到结果为1,则返回True

其他情况则返回False


3 解题方法

from typing import List

class Solution:

    def isPowerOfThree(self, n: int) -> bool:

        if n==0:return False

        if n==1:return True

        return n%3==0 and self.isPowerOfThree(n/3)


print(Solution().isPowerOfThree(27))

print(Solution().isPowerOfThree(0))

print(Solution().isPowerOfThree(9))

print(Solution().isPowerOfThree(1))

第1-3,8-11行: 题目中已经给出的信息,运行代码时要根据这些代码进行编辑

第4行: 判断若a等于0,则返回False

第5行: 判断若a等于1,则返回True

第6行: 其他情况下,若n除以3的余数为0且除之后得到的数也是3的幂,则返回True,若有一者不满足,则返回False


代码运行结果为:

attachments-2022-04-eMRFA3ch624a4695b3d5c.png

算法讲解

这里用到了基础算法:递归,简单讲解下这个算法:

什么是递归

程序调用自身的编程技巧称为递归

递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题:

(1)数据的定义是按递归定义的。(Fibonacci函数)

(2)问题解法按递归算法实现。

(3)数据的结构形式是按递归定义的。

递归函数特征

必须有一个明确的结束条件;

每次进入更深一层递归时,问题规模相比上次递归都应有所减少

相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。

递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出)

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言,推荐大家关注一个微信公众号:Python编程学习圈。每天分享行业资讯、技术干货供大家阅读,关注即可免费领取整套Python入门到进阶的学习资料以及教程,感兴趣的小伙伴赶紧行动起来吧。

attachments-2022-05-4xZGmEHD62908564ad8fc.jpeg

  • 发表于 2022-04-04 09:16
  • 阅读 ( 526 )
  • 分类:Python开发

0 条评论

请先 登录 后评论
轩辕小不懂
轩辕小不懂

2403 篇文章

作家榜 »

  1. 轩辕小不懂 2403 文章
  2. 小柒 1490 文章
  3. Pack 1135 文章
  4. Nen 576 文章
  5. 王昭君 209 文章
  6. 文双 71 文章
  7. 小威 64 文章
  8. Cara 36 文章