||
Hello,大家好!要说声抱歉了,今天说好的K均值聚类推到明天了。
今天是递归算法,请查阅!谢谢。
递归算法是一种很有用的编程思想,特别是在函数编程中。有句话,我直接从文献中搬过来,太经典了。
函数不但可以调用自身(直接递归),还可以调用其他函数,其他函数也可以再调用该函数(间接递归)。
这句话需要深刻理解并不容易,我们先看直接调用。
一、阶乘
#阶乘 import math import time def my_factorial(n): s=1 for x in range(1,n+1): s*=x return s #下面用递归实现 def fact(n): if (n==0|n==1): return 1 else: return n*fact(n-1) #直接调用已有函数 start=time.clock() p=math.factorial(33) end=time.clock() print('调用math.factorial耗时:',end-start,'\n结果为:',p,'\n') start=time.clock() k=my_factorial(33) end=time.clock() print('for循环定义函数耗时:',end-start,'\n结果为:',k,'\n') start=time.clock() q=fact(33) end=time.clock() print('递归函数耗时:',end-start,'\n结果为:',q,'\n')
运行结果如下:
调用math.factorial耗时: 3.20782915615167e-06 结果为: 8683317618811886495518194401280000000 for循环定义函数耗时: 7.37800705916114e-06 结果为: 8683317618811886495518194401280000000 递归函数耗时: 1.2510533708987026e-05 结果为: 8683317618811886495518194401280000000
递归方法每一次都要调用函数,而且需要判断,而for循环调用一次,直接累积即可。
二、二项式系数练习
#用递归方法实现 import time def binomial(r,n): if r==n: return 1 elif r==1: return n else: return binomial(r,n-1)+binomial(r-1,n-1) start=time.clock() num=binomial(4,12) end=time.clock() print('自己编写的递归函数耗时',end-start,'\n结果为',num,'\n') def crn(r,n): if r==0: return 1 if n==0: return 0 return crn(r,n-1)+crn(r-1,n-1) start=time.clock() b=crn(4,12) end=time.clock() print('网上的递归函数耗时',end-start,'\n结果为',b,'\n')
运行结果如下:
自己编写的递归函数耗时 5.5495444401423894e-05
结果为 495
网上的递归函数耗时 0.0001988854076813984
结果为 495
还是我自己编写的函数厉害。很可能是我的计算步骤要少,
当r=n,肯定是1,r=1,结果肯定是n
三、请自己完成Fibonacci序列的编写。
四、折半查找法
#折半查找—递归方法实现 import numpy as np import pandas as pd np.random.seed(123) num_list=np.random.randn(12) num_list.sort() num=num_list.round(1) print(num) a=1.3 #最笨方法 def num_in(a,num): index=range(len(num)) left=min(index) right=max(index) while left <=right: mid=(left+right)//2 if a<num[mid]: right=mid-1 elif a>num[mid]: left=mid+1 elif a==num[mid]: return mid index=num_in(a,num) print('a是否在有序列表num里面\n返回数字则是索引,不在则为None\n',index) #采用递归改写上面方法 def num_in2(a,num,left,right): if (left<=right): mid=(left+right)//2 if compare(a,num[mid])==1: return num_in2(a,num,mid+1,right) elif compare(a,num[mid])==0: return mid elif compare(a,num[mid])==-1: return num_in2(a,num,left,mid-1) def compare(b,c): if b<c: return -1 elif b==c: return 0 else : return 1 ii=range(len(num)) left=min(ii) right=max(ii) index2=num_in2(a,num,left,right) print(index2)
两种方法结果是一样的,证明我的program没有问题。
欢迎持续关注,明天K均值聚类理论。
参考文献为:清华大学朱仲涛译《数据结构基础(C语言版)》
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-19 21:27
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社