Py_解决多元线性方程组以及线性筛

发布于 2019-10-14  18 次阅读


使用高斯消元法

def funGuas_1(ar_1 , n ) :
    #Gaussian elimination
    for i in range( len(ar_1) ):
        temp = ar_1[i][i]
        for j in range( len(ar_1[0]) ):
            ar_1[i][j] *= 1/temp
        for j in range(  i+1 , len(ar_1) ) :
            temp = ar_1[j][i]
            for k in range( len(ar_1[0] ) ):
                    ar_1[j][k] -= ar_1[i][k]*temp
    for i in range( len(ar_1[0])-2 , 0 , -1 ):
        for j in range(i):
            temp = ar_1[j][i]
            for k in range( len(ar_1[0]) ):
                    ar_1[j][k] -= ar_1[i][k]*temp
    i = 1 
    for item in ar_1 :
        print( 'x_%d = %.3f'%(i ,item[len(ar_1[0])-1]) )
        i += 1 

使用高斯约旦消元法

def funGuas_2( ar , n ):
    #Gaussian Jordan
    dis = 0
    for i in range( len(ar) ):
        if ar[i][i]==0 :
            for j in range( i+1 , n ):
                if not ar[j][i]==0 :
                    dis = j
                    break
            for j in range( len(ar) ):
                ar[dis][j],ar[i][j] = ar[i][j],ar[dis][j]
                #make sure Diagonal element is not 0
        if not ar[i][i]==0 and not ar[i][i]==1 :
            for j in range( i+1 , n+1 ):
                ar[i][j] /= ar[i][i]
            ar[i][i] = 1
        for j in range( len(ar) ):
            if i==j :
                continue
            temp = ar[j][i]/ar[i][i]
            for k in range( i , n+1 ):
                ar[j][k] -= ar[i][k]*temp
    for item in ar :
        print( item )

 

线性筛

def isPrime(n):
# Linear sieve
    visit = [1 for i in range(n * 10)]
    prime = [0 for i in range(n * 10)]  # temp
    num = 0
    for i in range(2, n + 1):
        if visit[i] == 1:
            num = num + 1
            prime[num] = i
        for j in range(1, num + 1):
            if i * prime[j] <= n:
                visit[i * prime[j]] = 0
                if i % prime[j] == 0: #Pruning
                    break
            else:
                break
    return prime

 

测试代码:

if __name__ == '__main__' :
    m = int(input())
    grid  = [[] for i in range(m)]
    Agrid = [[] for i in range(m)]
    Bgrid = [0 for i in range(m)]
    for i in range(m):
        line = input().split(' ')
        for j in range(len(line)-1):
                grid[i].append(int(line[j]))
                Agrid[i].append(int(line[j]))
        j+=1
        grid[i].append(int(line[j]))
        Bgrid.append(int(line[j]))
    Bgrid = Bgrid[m:]
    print( grid )
    print( Agrid )
    print( Bgrid )
    funGuas_1(grid, m)
    funGuas_2(grid, m)
    res = linalg.solve(Agrid, Bgrid)
    print(res)
    #两种解多元线性方程组的方法
    pri= []
    pri =isPrime(int(1e5+20))
    pri[0] = 1
    ans = 0
    for i in range(len(pri)):
        if pri[i]<100 :
            ans += pri[i]
        else :
            break
    print( ans )

 

喜欢这篇文章吗,不妨分享给朋友们吧!

科学是第一生产力