精华内容
下载资源
问答
  • Python 递归算法指归.pdf
  • 主要介绍了浅谈Python 递归算法指归,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • Python 递归算法指

    千次阅读 多人点赞 2019-07-16 16:23:57
    递归( recursion)是一种编程技巧,某些情况下,甚至是无可替代的技巧。递归可以大幅简化代码,看起来非常简洁,但递归设计却非常抽象,不容易掌握。...那么,究竟什么是递归呢?让我们先从生活中找一个栗子。

    1. 递归概述

    递归( recursion)是一种编程技巧,某些情况下,甚至是无可替代的技巧。递归可以大幅简化代码,看起来非常简洁,但递归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是自下而上的解决问题——这就是递归看起来不够直观的原因。那么,究竟什么是递归呢?让我们先从生活中找一个栗子。

    我们都有在黑暗的放映厅里找座位的经验:问问前排的朋友坐的是第几排,加上一,就是自己当前所处位置的排号。如果前排的朋友不知道自己是第几排,他可以用同样的方法得到自己的排号,然后再告诉你。如果前排的前排的朋友也不知道自己是第几排,他就如法炮制。这样的推导,不会无限制地进行下去,因为问到第一排的时候,坐在第一排的朋友一定会直接给出答案的。这就是递归算法在生活中的应用实例。

    关于递归,不太严谨的定义是“一个函数在运行时直接或间接地调用了自身”。严谨一点的话,一个递归函数必须满足下面两个条件:

    1. 至少有一个明确的递归结束条件,我们称之为递归出口,也有人喜欢把该条件叫做递归基。
    2. 有向递归出口方向靠近的直接或间接的自身调用(也被称作递归调用)。

    递归虽然晦涩,亦有规律可循。掌握了基本的递归理论,才有可能将其应用于复杂的算法设计中。

    2. 线性递归

    我们先从最经典的两个递归算法开始——阶乘(factorial)和斐波那契数列(Fibonacci sequence)。几乎所有讨论递归算法的话题,都是从从它们开始的。阶乘的概念比较简单,唯一需要说明的是,0的阶乘是1而非0。为此,我专门请教了我的女儿,她是数学专业的学生。斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列是这样定义的:

    	F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N,N为正整数集)
    

    阶乘和斐波那契数列的递归算法如下:

    def factorial(n):
    	if n == 0: # 递归出口
    		return 1
    	return n*factorial(n-1) # 向递归出口方向靠近的自身调用
    
    def fibonacci(n):
    	if n < 2: # 递归出口
    		return 1
    	return fibonacci(n-1) + fibonacci(n-2) # 向递归出口方向靠近的自身调用
    

    这两个函数的结构都非常简单,递归出口和自身调用清晰明了,但二者有一个显著的区别:阶乘函数中,只用一次自身调用,而斐波那契函数则有两次自身调用。

    阶乘递归函数每一层的递归对自身的调用只有一次,因此每一层次上至多只有一个实例,且它们构成一个线性的次序关系。此类递归模式称作“线性递归”,这是递归最基本形式。非线性递归(比如斐波那契递归函数)在每一层上都会产生两个实例,时间复杂度为 O ( n 2 ) O(n^2) O(n2),极易导致堆栈溢出。

    其实,用循环的方法同样可以简洁地写出上面两个函数。的确,很多情况下,递归能够解决的问题,循环也可以做到。但是,更多的情况下,循环是无法取代递归的。因此,深入研究递归理论是非常有必要的。

    3. 尾递归

    接下来,我们将上面的阶乘递归函数改造一下,仍然用递归的方式实现。为了便于比较,我们把两种算法放在一起。

    def factorial_A(n):
    	if n == 0: # 递归出口
    		return 1
    	return n*factorial_A(n-1) # 向递归出口方向靠近的自身调用
    
    def factorial_B(n, k=1):
    	if n == 0: # 递归出口
    		return k
    	k *= n
    	n -= 1
    	return factorial_B(n,k) # 向递归出口方向靠近的自身调用
    

    比较 factorial_A() 和 factorial_B() 的写法,就会发现很有意思的问题。factorial_A() 的自身调用属于表达式的一部分,这意味着自身调用不是函数的最后一步,而是拿到自身调用的结果后,需要再做一次乘法运算;factorial_B() 的自身调用则是函数的最后一步。像 factorial_B() 函数这样,当自身调用是整个函数体中最后执行的语句,且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归(Tail Recursion)。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

    分别使用 factorial_A() 和 factorial_B() 计算5的阶乘,下图所示的计算过程,清晰展示了尾递归的优势:不用花费大量的栈空间来保存上次递归中的参数、局部变量等,这是因为上次递归操作结束后,已经将之前的数据计算出来,传递给当前的递归函数,这样上次递归中的局部变量和参数等就会被删除,释放空间,从而不会造成栈溢出。

    factorial_A(5)
    5 * factorial_A(4)
    5 * 4 * factorial_A(3)
    5 * 4 * 3 * factorial_A(2)
    5 * 4 * 3 * 2 * factorial_A(1)
    5 * 4 * 3 * 2 * 1 * factorial_A(0)
    5 * 4 * 3 * 2 * 1
    5 * 4 * 3 * 2
    5 * 4 * 6
    5 * 24
    120
    
    factorial_B(5, k=1)
    factorial_B(4, k=5)
    factorial_B(3, k=20)
    factorial_B(2, k=60)
    factorial_B(1, k=120)
    factorial_B(0, k=120)
    120
    

    尾递归虽然有低耗高效的优势,但这一类递归一般都可转化为循环语句。

    4. 单向递归

    前文中两个递归函数,不管是阶乘还是斐波那契数列,递归总是向着递归出口方向进行,没有分支,没有反复,这样的递归,我们称之为单向递归。在文件递归遍历等应用场合,搜索完一个文件夹,通常要返回至父级目录,继续搜索其他兄弟文件夹,这个过程就不是单向的,而是有分叉的、带回溯的。通常复杂递归都不是单向的,算法设计起来就比较困难。

    import os
    
    def ergodic(folder):
    	for root, dirs, files in os.walk(folder):
    		for dir_name in dirs:
    			print(os.path.join(root, dir_name))
    		for file_name in files:
    			print(os.path.join(root, file_name))
    

    上面是借助于 os 模块的 walk() 实现的基于循环的文件遍历方法。虽然是循环结构,如果不熟悉 walk() 的话,这个函数看起来还是很不直观。我更喜欢下面的递归遍历方法。

    import os
    
    def ergodic(folder):
    	for item in os.listdir(folder):
    		obj = os.path.join(folder, item)
    		print(obj)
    		if os.path.isdir(obj):
    			ergodic(obj)
    

    5. 深度优先与广度优先

    遍历文件通常有两种策略:深度优先搜索 DFS(depth-first search) 和广度优先搜索BFS(breadth-first search) 。顾名思义,深度优先就是优先处理本级文件夹中的子文件夹,递归向纵深发展;广度优先就是优先处理本级文件夹中的文件,递归向水平方向发展。

    import os
    
    def ergodic_DFS(folder):
    	"""基于深度优先的文件遍历"""
    	
    	dirs, files = list(), list()
    	for item in os.listdir(folder):
    		if os.path.isdir(os.path.join(folder, item)):
    			dirs.append(item)
    		else:
    			files.append(item)
    	
    	for dir_name in dirs:
    		ergodic(os.path.join(folder, dir_name))
    	for file_name  in files
    		print(os.path.join(folder, file_name))
    
    def ergodic_BFS(folder):
    	"""基于广度优先的文件遍历"""
    	
    	dirs, files = list(), list()
    	for item in os.listdir(folder):
    		if os.path.isdir(os.path.join(folder, item)):
    			dirs.append(item)
    		else:
    			files.append(item)
    	
    	for file_name  in files
    		print(os.path.join(folder, file_name))
    	for dir_name in dirs:
    		ergodic(os.path.join(folder, dir_name))
    
    展开全文
  • Python算法特点

    2018-08-17 16:37:26
    算法是解题方案的准确而完整的描述,是一系列解决问题的清晰指令...算法是Python开发中重要知识技能,不可避免的要使用到该技能,那么,Python算法什么特点呢? 一个Python算法应该具有以下七个重要的特征: ...

    算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。算法是Python开发中重要知识技能,不可避免的要使用到该技能,那么,Python算法有什么特点呢?

    一个Python算法应该具有以下七个重要的特征:

    1. 有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;

    2. 确切性(Definiteness):算法的每一步骤必须有确切的定义;

    3. 输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输     入是指算法本身定出了初始条件;

    4. 输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没       有输出的算法是毫无意义的;

    5. 可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行       的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);

    6. 高效性(High efficiency):执行速度快,占用资源少;

    7. 健壮性(Robustness):对数据响应正确。

    Python算法除了具有以上特征,还和时间和空间有关系,不同的算法可能用不同的时间、空间或效率来完成同样的任务,因此,一个Python算法的优劣可以用空间复杂度与时间复杂度来衡量。

    展开全文
  • 哦,我的Python 《剑提供》中的面试题的Python解决方案及总结,包含unittest单元测试; Python数据结构与算法等常见知识汇总。使用的Python版本为3.6。如有问题欢迎指出〜 目录 剑offer题解 常见算法
  • python算法之迭代算法

    千次阅读 2020-01-26 21:24:55
    前言 迭代法也叫辗转法,是一种...迭代关系式是如何从变量的前一个值推出下一个值的公式或者关系。 对迭代过程进行控制 所需的迭代次数是确定的,可以计算出来,可以构建一个固定次数的循环来实现对迭代过程的控...

    前言

    迭代法也叫辗转法,是一种不断用变量的旧值递推新值的过程,在解决问题时总是重复利用的一种方法。

    迭代算法基础

    确认迭代变量

    在可以使用迭代算法解决的值中至少存在一个迭代变量。可以直接或者间接的用旧值推出新值。

    建立迭代关系式

    迭代关系式是指如何从变量的前一个值推出下一个值的公式或者关系。

    对迭代过程进行控制

    1. 所需的迭代次数是确定的,可以计算出来,可以构建一个固定次数的循环来实现对迭代过程的控制
    2. 所需的迭代次数无法确定,需要进一步分析出用来结束迭代过程的条件。

    解决“非线性方程”问题

    求ex-cos( π \pi πx)=0

    import math  #为了使用cos函数
    
    def takeStep(Xcur):
        Xnex=[0,0,0];
        Xnex[0]=math.cos(Xcur[1]*Xcur[2])/3.0+1.0/6
        Xnex[1]=math.sqrt(Xcur[0]*Xcur[0]+math.sin(Xcur[2])+1.06)/9.0-0.1
        Xnex[2]=-1*math.exp(-1*Xcur[0]*Xcur[1])/20.0-(10*math.pi-3)/60
        return Xnex
        
    def initialize():
        X0=[0.1,0.1,-0.1]
        return X0
    
    def ColculateDistance(Xcur,Xnew):
        temp=[Xcur[0]-Xnew[0],Xcur[1]-Xnew[1],Xcur[2]-Xnew[2]]    
        dis=math.sqrt(temp[0]*temp[0]+temp[1]*temp[1]+temp[2]*temp[2])
        return dis
        
    def iteration(eps,maxIter):
        cur_eps=10000
        Xcur=initialize()
        Xnew=[0,0,0]
        iterNum=1
        print("--------------------------开始迭代--------------------------")
        print("  迭代次数  |    Xk1    |    Xk2    |    Xk3    |    eps    ")
    
        while (cur_eps>eps and iterNum<maxIter) :
            Xnew=takeStep(Xcur);
            cur_eps=ColculateDistance(Xcur,Xnew)
            print("     %d       %.8f  %.8f  %.8f  %8.8f"%(iterNum,Xcur[0],Xcur[1],Xcur[2],cur_eps))
            iterNum+=1
            Xcur=Xnew
        return 0
        
    
    iteration(10**-10,200)
    

    运行结果截图

    递归与迭代算法的区别

    递归是从上向下逐步拓展需求,最后从下向上运算,即有f(n) ~ f(1),再由 f(1) ~ f(n)。迭代算法是直接从下向上运算,由f(1) ~ f(n),

    展开全文
  • python算法引入

    千次阅读 2019-06-29 20:26:04
    这里主要是介绍算法的介绍以及一些判断算法好坏的标准和方式


    这里主要是介绍算法的介绍以及一些判断算法好坏的标准和方式

    引入

    如果a+b+c = 1000,且a^2 + b^2 = c^2,如何求出所有a,b,c可能的组合?

    第一次尝试:

    import time
    print(
    展开全文
  • python算法有哪些特征

    千次阅读 2018-06-01 18:38:23
    算法是解题方案的准确而完整的描述,是一系列解决问题的清晰指令...算法是Python开发中重要知识技能,不可避免的要使用到该技能,那么,Python算法什么特点呢?一个Python算法应该具有以下七个重要的特征:1. 有...
  • 本文为大家讲解了python算法表示概念,供大家参考,具体内容如下 常数阶O(1) 常数又称定数,是一个数值不变的常量,与之相反的是变量 为什么下面算法的时间复杂度不是O(3),而是O(1)。 int sum = 0,n = 100; /*...
  • Python基础算法/剑offer

    万次阅读 多人点赞 2016-07-30 10:50:28
    之前完成了个人的Python编写,包括常见的一些基础算法,剑offer的绝大多数算法的编写。都上传到github上了,很多里面都有自己几个测试用例,不过都注释掉了,直接去掉注释就好。如果对你有帮助,请记得点击github...
  • offer算法python

    2020-12-22 12:35:46
    递归与循环 斐波那契数列 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39 解题思路:找规律 设函数f(n) 当 n=0时 f(0) =0 当 n=1时 f(1) =1 ...
  • 内容来源:廖雪峰的官方教程/菜鸟教程/ CSDN / github /《流畅的Python》 :变量/字符串/数字和运算符 :列表/元组 :字典/套 :如果/循环 :调用函数/定义函数/函数的参数 :/列表生成式/生成器/迭代器 :高...
  • 算法复杂度分为时间复杂度和空间复杂度,简单而讲时间复杂度的是语句执行次数,空间复杂度的是算法所占的存储空间,本文通过代码给大家介绍Python算法的时间复杂度和空间复杂度问题,感兴趣的朋友一起看看吧
  • Python算法- 剪绳子

    万次阅读 2020-08-01 12:21:33
    offer 有这样一道编程题 给你一根长度为 n 的绳子,请把绳子剪成整数长的 m 段(m、n 都是整数,n>1 并且 m>1,m<=n),每段绳子的长度记为 k [1],…,k [m]。请问 k [1] x…xk [m] 可能的最大乘积是...
  • Python算法基础题目

    千次阅读 2019-04-06 15:06:31
    回数是从左到右和从右到左的数值一样,例如:像12321这样的数,从左边1-2-3-2-1,从右边1-2-3-2-1. 要求:从100到1000的回数个数 思路:反转,列表中的三种反转分别是reversed(),sorted(),切片,而字符串中没有...
  • Python入门简单、功能强大...什么是算法算法(Algorithm)是解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有...
  • 硬币找零问题 ...所谓贪心选择性质,是应用同一规则,将原问题变为一个相似的但规模更小的子问题,后面的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的选择。从全局来看,运
  • python算法

    千次阅读 2018-06-23 10:44:47
    Hanoi塔问题,算法分析如下,设A上有n个盘子(编号由上到下:1、2、3……、n)。A:初始塔,B:中转塔,C:目标塔  a、如果n=1,则将盘子从A塔直接移动到C塔(借助B塔)。  b、如果n=3,则:  (1)将A塔上编号1...
  • Python 凸包算法

    2017-10-28 09:11:45
    凸包问题是在n个点中,寻找一个凸多边形,使所有的点在凸多边形的边界或者内部。实现语言:Python
  • Python算法系列-双指针问题

    千次阅读 多人点赞 2020-04-11 19:05:44
    python算法-双指针问题一、数组合并1. 使用模拟指针和并两个有序数组2.模拟指针说明:二、二分法(折半查找法)1.有序数组的二分法查找2. 二分法说明三、链表(双链表和单链表区别) 一、数组合并 1. 使用模拟指针和...
  • 给大家带来的一篇关于机器学习相关的电子书资源,介绍了关于Python机器学习算法方面的内容,本书是由电子工业出版社出版,格式为PDF,资源大小30.1 MB,赵志勇编写,目前豆瓣、亚马逊、当当、京东等电子书综合评分为...
  • 最全Python算法入门

    千次阅读 2020-03-30 09:02:00
    本文经AI新媒体量子位(ID:QbitAI)授权转载,转载请联系出处问耕 发自 凹非寺【导读】Github上超过6.8万星标:最全算法Python实现...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,440
精华内容 40,976
关键字:

python算法是指什么

python 订阅