拉格狼日查找算法

数据结构与算法 拉格狼日 评论

拉格狼日查找算法

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)

YanChen

Personal profile