Algorithm

Quote from COMP90038_2021_SM1: Algorithms and Complexity courseware, by Dr. Michael Kirley

Find GCD(m, n) 求最大公约数

• Step 1: If n = 0, return the value of m as the answer and stop.
• Step 2: Divide m by n and assign the value of the remainder to r.
• Step 3: Assign the value of n to m, and the value of r to n; go to Step 1. ```python def gcd(m, n): while n != 0:

    r = m % n
    m = n
    n = r

  return m

def test(): print(gcd(67, 24))

if name == “main“: test()

当模块被直接运行时，以下代码块将被运行(当模块是被导入时，代码块不被运行)。

当前模块名=直接运行时模块名

<a name="MXg7c"></a>
## Find Elements in Array
```python
def find(A, x, low, high):
# initial call: find(A, x, 0, len(A)-1) 数列，查询值，队首，队尾
    if low>high:
        return -1
    elif A[low]==x:
        return lo
    else:
        return find(A, x, low+1, high)

def test():
    A=[1,2,3,4,6,47,357]
    print(find(A, 8, 0, len(A)-1))
    print(find(A, 6, 0, len(A)-1))

Find if there is value in LinkedList

class node:                        //创建一个类来表示链表
    def __init__(self, val=None):  //初始化
        self.val = val             //定义节点的值
        self.next = None           //定义列表的开始位置

    def __str__(self):             //返回一个对象的描述信息
        return str(self.val)       //返回字符串的值

def find(p, value):         
    while p != None:               
        if p.val == value:         
            return p
        p = p.next                 
    return None

def test():
    firstnode = node(50)
    secondnode = node(30)
    firstnode.next = secondnode
    print(find(firstnode, 30))
    print(find(firstnode, 1))

Binary Search 折半查找

def BinSearch(A, lo, hi, key):   //array, low, high, key to look for
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if A[mid] == key:
        return mid
    else:
        if A[mid] > key:
            return BinSearch(A, lo, mid - 1, key)
        else:
            return BinSearch(A, mid + 1, hi, key)

def test():
    A = [1, 2, 3, 5, 8, 13, 21, 34, 55]
    print(BinSearch(A, 0, len(A) - 1, 5))
    print(BinSearch(A, 0, len(A) - 1, 50))

N factorial 阶乘

def F(n):
    if n == 0:
        return 1
    else:
        return F(n - 1) * n

def test():
    print(F(7))

Matrix Multiplication

def MatrixMult(A, B):
    n = len(A)
    C = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] = C[i][j] + A[i][k] * B[k][j]  //C[i][j]指每个矩阵点位， A[i][k]每个左边矩阵的每行的某个点，B[k][j]右边矩阵的每列的某个点
    return C

def test():
    A = [[1,2,3], [4,5,6], [7,8,9]]
    B = [[3,6,9], [1,7,4], [5,2,8]]
    print(MatrixMult(A, B))

MaxElement

def MaxElement(A):
    if len(A) == 0:
        return None
    max = A[0]
    for i in range(len(A)):
        if A[i] > max:
            max = A[i]
    return max

def test():
    print(MaxElement([3, 1, 4, 1, 5, 9, 2, 6]))

SelSort

def SelSort(A):
    for i in range(len(A) - 1):
        min = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min]:
                min = j
        A[i], A[min] = A[min], A[i]  //前后两数互换

def test():
    A = [5,6,9,1,8,4,2,3,7]
    SelSort(A)
    print(A)

Review

Mastering Git

Version control in VS Code

Tip

Git in common use

A Working Directory: where files are created, edited, deleted, and organized
A Staging Area: where changes that are made to the working directory are listed
A Repository: where Git permanently stores changes as different versions of the project

cd /home
git init      //Initializing a Git Repository

git diff hello.txt        //Displaying Differences from working directory
diff --git a/hello.txt b/hello.txt   //and staging area in one specific file

git log    //Showing Git Commit Logs

git commit -m "log message here(Added About section to README)"  //Committ Your Code

git add filename
git add .    //. all files
git status   //add the filename file to the staging area

Backtrack in Git

git checkout HEAD filename:   //Discards changes in the working directory.
git reset HEAD filename:  //Unstages file changes in the staging area.
git reset commit_SHA:  //Resets to a previous commit in your commit history.

git add filename_1 filename_2:   //add multiple files to the staging area

Share

Orientation Week

Intro to Database Systems & Information Modelling

Timeline of Computer History