Skip to content

Commit 0c08851

Browse files
heqin-zhuheqin-zhu
committed
Add computaional method
1 parent 0b1f116 commit 0c08851

54 files changed

Lines changed: 1221 additions & 50 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎.gitignore‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
.*
22
*.o
33
*.exe
4-
tree_link.py
54
__pycache__/**
65
!.gitignore
7-
todo

‎README.md‎

Lines changed: 52 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
# Algorithm and Data Structures
22
>Notes and codes for learning algorithm and data structures :smiley:
33
4-
Some pictures and idead are from `<<Introduction to Algotithm>>
4+
Some pictures and ideas are from `<<Introduction to Algotithm>>
55

66
I use python 3.6+ and c++ to implements them.
77
Since I used f-Strings in python, you may use python 3.6+ to run the following python scripts.
@@ -14,36 +14,67 @@ So,if you wannt to view the notes which contain latex math formulas and are in m
1414

1515
# Index
1616
* [.](.)
17-
* [notes](./notes)
18-
* [alg-general.md](./notes/alg-general.md)
19-
* [hashTable.md](./notes/hashTable.md)
20-
* [red-black-tree.md](./notes/red-black-tree.md)
21-
* [sort.md](./notes/sort.md)
22-
* [tree.md](./notes/tree.md)
23-
* [b-tree.md](./notes/b-tree.md)
24-
* [graph](./notes/graph.md)
25-
* [fibonacci-heap](./notes/fib-heap.md)
26-
* [algorithm](./algorithm)
27-
* [8Astar.py](./algorithm/8Astar.py)
28-
* [cantor.cc](./algorithm/cantor.cc)
29-
* [manacher.py](./algorithm/manacher.py)
30-
* [markov.py](./algorithm/markov.py)
31-
* [sort](./algorithm/sort)
32-
* [sunday.py](./algorithm/sunday.py)
17+
* [computationalMethod](./computationalMethod)
18+
* [interplotion.py](./computationalMethod/interplotion.py)
19+
* [iteration.py](./computationalMethod/iteration.py)
20+
* [least_square.py](./computationalMethod/least_square.py)
21+
* [linear_equation.py](./computationalMethod/linear_equation.py)
22+
* [numerical_differential.py](./computationalMethod/numerical_differential.py)
23+
* [numerical_integration.py](./computationalMethod/numerical_integration.py)
24+
* [README.md](./computationalMethod/README.md)
25+
* [solve-linear-by-iteration.py](./computationalMethod/solve-linear-by-iteration.py)
26+
* [tongyu_equation.py](./computationalMethod/tongyu_equation.py)
27+
* [vector_norm.py](./computationalMethod/vector_norm.py)
3328
* [dataStructure](./dataStructure)
34-
* [redBlackTree.py](./dataStructure/redBlackTree.py)
35-
* [bTree.py](./dataStructure/bTree.py)
36-
* [hashTable.py](./dataStructure/hashTable.py)
37-
* [splayTree.py](./dataStructure/splayTree.py)
3829
* [allOone](./dataStructure/allOone)
3930
* [binaryHeap.py](./dataStructure/binaryHeap.py)
4031
* [binaryTree.py](./dataStructure/binaryTree.py)
32+
* [bTree.py](./dataStructure/bTree.py)
4133
* [graph](./dataStructure/graph)
34+
* [hashTable.py](./dataStructure/hashTable.py)
4235
* [huffman](./dataStructure/huffman)
4336
* [leftHeap.py](./dataStructure/leftHeap.py)
4437
* [loserTree.py](./dataStructure/loserTree.py)
4538
* [map.cc](./dataStructure/map.cc)
4639
* [polynomial.cpp](./dataStructure/polynomial.cpp)
4740
* [polynomial.py](./dataStructure/polynomial.py)
41+
* [redBlackTree.py](./dataStructure/redBlackTree.py)
42+
* [splayTree.py](./dataStructure/splayTree.py)
4843
* [trie.py](./dataStructure/trie.py)
4944
* [winnerTree.py](./dataStructure/winnerTree.py)
45+
* [docs](./docs)
46+
* [algorithm-general.md](./docs/algorithm-general.md)
47+
* [b-tree.md](./docs/b-tree.md)
48+
* [fib-heap.md](./docs/fib-heap.md)
49+
* [graph.md](./docs/graph.md)
50+
* [hashTable.md](./docs/hashTable.md)
51+
* [README.md](./docs/README.md)
52+
* [red-black-tree.md](./docs/red-black-tree.md)
53+
* [sort.md](./docs/sort.md)
54+
* [tree.md](./docs/tree.md)
55+
* [dynamicProgramming](./dynamicProgramming)
56+
* [lcs.hs](./dynamicProgramming/lcs.hs)
57+
* [lcs.py](./dynamicProgramming/lcs.py)
58+
* [matrix-multiply.py](./dynamicProgramming/matrix-multiply.py)
59+
* [splitStripe.hs](./dynamicProgramming/splitStripe.hs)
60+
* [splitStripe.py](./dynamicProgramming/splitStripe.py)
61+
* [testVec2d.hs](./dynamicProgramming/testVec2d.hs)
62+
* [Vec2d.hs](./dynamicProgramming/Vec2d.hs)
63+
* [math](./math)
64+
* [cantor.cc](./math/cantor.cc)
65+
* [isPrime.py](./math/isPrime.py)
66+
* [num_weight.py](./math/num_weight.py)
67+
* [README.md](./README.md)
68+
* [search](./search)
69+
* [8Astar.py](./search/8Astar.py)
70+
* [sort](./sort)
71+
* [binaryTree.py](./sort/binaryTree.py)
72+
* [heapSort.py](./sort/heapSort.py)
73+
* [quickSort.py](./sort/quickSort.py)
74+
* [radixSort.py](./sort/radixSort.py)
75+
* [select.py](./sort/select.py)
76+
* [shellSort.py](./sort/shellSort.py)
77+
* [string](./string)
78+
* [manacher.py](./string/manacher.py)
79+
* [markov.py](./string/markov.py)
80+
* [sunday.py](./string/sunday.py)

‎algorithm/dynamic-programming/matrix-multiply.py‎

Lines changed: 0 additions & 4 deletions
This file was deleted.

‎computationalMethod/README.md‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# 计算方法
2+
>一些计算方法的算法，比如插值，拟合 近似计算，解方程组等
3+
有些功能numpy, sympy可能已经就有,但是为了学习各种计算方法,我就重新写了一遍,主要使用的是numpy的数组,矩阵,sympy的符号运算
4+
5+
# 需要
6+
* python3
7+
* python modules
8+
- sympy
9+
- numpy
10+
11+
# 目录说明
12+
## interplotion
13+
插值, 有Lagrange插值, Newton插值
14+
## iteration
15+
迭代, 二分迭代, 不动点迭代,差商迭代, 弦截法迭代
16+
## least_square
17+
最小二乘拟合, 解矛盾方程组
18+
## linear_equation
19+
解线性方程组,用到
20+
* doolittle分解
21+
* crout分解
22+
* ldlt分解
23+
* 列主元消元法
24+
## vector-norm
25+
计算向量,矩阵的各种范数
26+
## tongyu_equation
27+
解同余方程
28+
29+
30+
## LICENCE
31+
[MIT](LICENCE.txt)
32+
33+
## 联系我
34+
* mail: <img style="display:inline" src="http://ounix1xcw.bkt.clouddn.com/gmail.png"></img>
35+
* QQ : 414313516

‎computationalMethod/interplotion.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
''' mbinary
2+
#########################################################################
3+
# File : interplotion.py
4+
# Author: mbinary
5+
# Mail: zhuheqin1@gmail.com
6+
# Blog: https://mbinary.coding.me
7+
# Github: https://github.com/mbinary
8+
# Created Time: 2018-10-02 21:14
9+
# Description:
10+
#########################################################################
11+
'''
12+
13+
#########################################################################
14+
# File : interplotion.py
15+
# Author: mbinary
16+
# Mail: zhuheqin1@gmail.com
17+
# Blog: https://mbinary.github.io
18+
# Github: https://github.com/mbinary
19+
# Created Time: 2018-05-18 09:29
20+
# Description: 插值计算,有牛顿插值,拉格朗日插值,以及通过插值得到的多项式估计新的函数值
21+
#########################################################################
22+
23+
24+
import sympy
25+
from collections import namedtuple
26+
from functools import reduce
27+
from operator import mul
28+
29+
X = sympy.Symbol ('x')
30+
point = namedtuple('point',['x','y'])
31+
32+
class interplotion:
33+
def __init__(self,points):
34+
self.points = [point(x,y) for x,y in points]
35+
self.xs= [i for i,j in points]
36+
self.poly,self.rem = self.newton(self.points,0,len(self.points)-1)
37+
38+
def newton(self,li,a,b):
39+
'''li:[(x,f(x))...]'''
40+
41+
qs = [li[0].y]
42+
43+
def quoDiff(begin,end):
44+
if begin == end:return li[begin].y
45+
q = (quoDiff(begin+1,end)-quoDiff(begin,end-1))/(li[end].x-li[begin].x)
46+
if begin == a:qs.append(q)
47+
return q
48+
49+
quoDiff(a,b)
50+
poly ,base = 0, 1
51+
for i,q in enumerate(qs):
52+
poly += q*base
53+
base*= X-li[i].x
54+
return poly, base*qs[-1]
55+
def lagrange(self,points=None):
56+
xs = None
57+
if points is None:
58+
xs = self.xs
59+
points = self.points
60+
else: xs =[x for x,y in points]
61+
product = reduce(mul,[X-x for x in xs],1)
62+
poly = 0
63+
for x,y in points:
64+
tmp = product/(X-x)
65+
coef = y/(tmp.subs(X,x))
66+
poly+= coef *tmp
67+
return poly
68+
69+
def predict(self,val,poly = None):
70+
if poly is None:poly = self.poly
71+
return poly.subs(X,val) # note the func subs
72+
73+
74+
if __name__ == '__main__':
75+
f = interplotion([(81,9),(100,10),(121,11)])
76+
p = f.lagrange()
77+
print(p.subs(X,105))
78+
print(p)
79+
80+
intor = interplotion([(0,11),(0.02,9),(0.04,7),(0.06,10)])
81+
p = intor.lagrange()
82+
print(p)
83+
res = intor.predict(0.08)
84+
print(res)

‎computationalMethod/iteration.py‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
''' mbinary
2+
#########################################################################
3+
# File : iteration.py
4+
# Author: mbinary
5+
# Mail: zhuheqin1@gmail.com
6+
# Blog: https://mbinary.coding.me
7+
# Github: https://github.com/mbinary
8+
# Created Time: 2018-10-02 21:14
9+
# Description:
10+
#########################################################################
11+
'''
12+
13+
import sympy
14+
import numpy as np
15+
from math import sqrt
16+
17+
18+
def newton(y:sympy.core,x0:float,epsilon:float=0.00001,maxtime:int=50) ->(list,list):
19+
'''
20+
newton 's iteration method for finding a zeropoint of a func
21+
y is the func, x0 is the init x val: int float epsilon is the accurrency
22+
'''
23+
if epsilon <0:epsilon = -epsilon
24+
ct =0
25+
t = y.free_symbols
26+
varsymbol = 'x' if len(t)==0 else t.pop()
27+
x0= float(x0)
28+
y_diff = y.diff()
29+
li = [x0]
30+
vals = []
31+
while 1:
32+
val = y.subs(varsymbol,x0)
33+
vals.append(val)
34+
x = x0- val/y_diff.subs(varsymbol,x0)
35+
li.append(x)
36+
ct+=1
37+
if ct>maxtime:
38+
print("after iteration for {} times, I still havn't reach the accurrency.\
39+
Maybe this function havsn't zeropoint\n".format(ct))
40+
return li ,val
41+
if abs(x-x0)<epsilon:return li,vals
42+
x0 = x
43+
44+
45+
def secant(y:sympy.core,x0:float,x1:float,epsilon:float =0.00001,maxtime:int=50) ->(list,list):
46+
'''
47+
弦截法, 使用newton 差商计算,每次只需计算一次f(x)
48+
secant method for finding a zeropoint of a func
49+
y is the func , x0 is the init x val, epsilon is the accurrency
50+
'''
51+
if epsilon <0:epsilon = -epsilon
52+
ct =0
53+
x0,x1 = float(x0),float(x1)
54+
li = [x0,x1]
55+
t = y.free_symbols
56+
varsymbol = 'x' if len(t)==0 else t.pop()
57+
last = y.subs(varsymbol,x0)
58+
vals = [last]
59+
while 1:
60+
cur = y.subs(varsymbol,x1)
61+
vals.append(cur)
62+
x = x1-cur*(x1-x0)/(cur-last)
63+
x0 ,x1= x1,x
64+
last = cur
65+
li.append(x)
66+
ct+=1
67+
if ct>maxtime:
68+
print("after iteration for {} times, I still havn't reach the accurrency.\
69+
Maybe this function havsn't zeropoint\n".format(ct))
70+
return li,vals
71+
if abs(x0-x1)<epsilon:return li,vals
72+
x0 = x
73+
74+
75+
def solveNonlinearEquations(funcs:[sympy.core],init_dic:dict,epsilon:float=0.001,maxtime:int=50)->dict:
76+
'''solve nonlinear equations:'''
77+
li = list(init_dic.keys())
78+
delta = {i:0 for i in li}
79+
ct = 0
80+
while 1:
81+
ys = np.array([f.subs(init_dic) for f in funcs],dtype = 'float')
82+
mat = np.matrix([[i.diff(x).subs(init_dic) for x in li] for i in funcs ],dtype = 'float')
83+
delt = np.linalg.solve(mat,-ys)
84+
for i,j in enumerate(delt):
85+
init_dic[li[i]] +=j
86+
delta[li[i]] = j
87+
if ct>maxtime:
88+
print("after iteration for {} times, I still havn't reach the accurrency.\
89+
Maybe this function havsn't zeropoint\n".format(ct))
90+
return init_dic
91+
if sqrt(sum(i**2 for i in delta.values()))<epsilon:return init_dic
92+
93+
94+
if __name__ =='__main__':
95+
x,y,z = sympy.symbols('x y z')
96+
97+
res,res2= newton(x**5-9,2,0.01)
98+
print(res,res2)
99+
100+
101+
res,res2 = secant (x**3-3*x-2,1,3,1e-3)
102+
print(res,res2)
103+
104+
105+
funcs=[x**2+y**2-1,x**3-y]
106+
init = {x:0.8,y:0.6}
107+
res_dic = solveNonlinearEquations(funcs,init,0.001)
108+
print(res_dic)

0 commit comments

Comments
 (0)