拉格狼日查找算法

拉格狼日查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#coding=utf-8
'''
Created on 2019-03-31

@author: Administrator
'''

import time
def costTime(func):
def _costTime(finddata,findlist):
starttime=time.time()
func(finddata,findlist)
endtime=time.time()
print(endtime-starttime)
return _costTime


@costTime
def search(finddata,findlist):
for data in findlist:
if data==finddata:
print("find",data)
return
print("not find")


@costTime
def search2(finddata,findlist):
low=0 #第一个
high=len(findlist)-1 #代表最后一个

times=0
while low<=high: #不能重叠
times+=1
print("times",times)
mid=(low+high)//2 #取出中间索引
middata=findlist[mid] #取出中间数据
if finddata <middata: #小于 淘汰1半
high =mid-1
elif finddata >middata: #小于 淘汰1半
low =mid+1
else:
print("find",finddata,mid)
return mid
print("not find")
return -1



@costTime
def search2lr(finddata,findlist):
low=0 #第一个
high=len(findlist)-1 #代表最后一个

times=0
while low<=high: #不能重叠
times+=1
print("times",times)

#mid=(low+high)//2 #取出中间索引
#mid= int( low +(high-low)* 0.5)
datamid=((finddata-low)/(high-low))
#datamid=0.5
mid = int(low + (high - low) * datamid)
middata=findlist[mid] #取出中间数据
if finddata <middata: #小于 淘汰1半
high =mid-1
elif finddata >middata: #小于 淘汰1半
low =mid+1
else:
print("find",finddata,mid)
return mid
print("not find")
return -1




findlist=[x+0.1 for x in range(100000000)]
finddata=98009999
while True:
finddata=eval(input("data"))
search2lr(finddata,findlist) #2.5050623416900635

拉格狼日插值算法

逐步插值,整体来说还是挺简单的,关键在于算法的部分,这里我运用了二维数组的数据结构来存储每次迭代后的新值。角标的循环初看可能有些复杂,自己动手走一遍就会很清楚啦 ,拉格狼日算法效率是二分查找的几十倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#coding=utf-8
'''
Created on 2019-03-31

@author: Administrator
'''

def Neville(xt,m,n,x):
for i in range(1,n):
for j in range(1,n):
w[i-j][i]=(x-xt[i-j])/(xt[i]-xt[i-j])
m[i][j]=m[i-1][j-1]+w[i-j][i]*(m[i][j-1]-m[i-1][j-1])
for i in range(n):
for j in range(0,i+1):
if j%n==0:
print("\n")
print(' %f' %m[i][j])

n = int(input('插入节点个数:'))
x = float(input('输入x的值:'))
m = [[0 for i in range(n)] for j in range(n)] #创建n*n矩阵
w = [[0 for i in range(n)] for j in range(n)]
xt = [0]*n
for i in range(n):
m[i][0] = float(input('插入第%d个y值:' %(i+1)))
for i in range(n):
xt[i] = float(input('插入第%d个x值:' %(i+1)))
Neville(xt,m,n,x)

下面的是拉格朗日插值算法,十分简单,分享借鉴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#coding=utf-8
'''
Created on 2019-09-31

@author: Administrator
'''
def lagrange(x,xt,yt,n):
y = 0
for i in range(n):
t = 1
for j in range(n):
if i!=j:
t = t*(x-xt[j])/(xt[i]-xt[j])
y = y+t*yt[i]
print("结果为:%f" %y)

xt = []
yt = []
x = float(input("插值x;"))
n = int(input("节点数目;"))
for i in range(n):
xt.append(float(input("第%d个x的值" %(i+1))))
for i in range(n):
yt.append(float(input("第%d个x的值" %(i+1))))

lagrange(x,xt,yt,n)