알고리즘및실습 strt!

1.1 Sequential search

Complexity function

$$T(n) = 1+\sum_{i=1}^n 1 +1 =1 +((n-1)+1)+1 = n+2$$

Code

def sSearch(self, S, x):     # seq search, T(n) = n
    location = 1
    while location <= len(S) and S[location] != x:
        location += 1
    if location > len(S):
        location = -1
    return location

1.2 nth Fibonacci term in iterative

Complexity function

$$T(n) = 2+\sum_{i=2}^n 1 +1 = 2+((n-2)+1) +1 = n+2$$

Code

def fibonacciItr(n):
    arr = [0,1]
    for i in range(2,n+1):
        arr.append(arr[i-1] + arr[i-2])

    print(arr)
    return arr[len(arr)-1]

1.3 Tower of Hanoi

Complexity function

$$solving\, recurrences \,by\, Substitution \\ t_{n} = 2t_{n-1}+1 \\ t_{n-1} = 2t_{n-2}+1\\ ... \\ t_{2} = 2t_{1}+1\\ t_{1}=1 \\ So,\, t_{n} = 2(2t_{n-2}+1)+1\\ = 4(2t_{n-3}+1)+2+1\\ = 8(2t_{n-4}+1)+4+2+1\\ ...\\ =\sum_{i=0}^{n-1} 2^{i} = 2^{n} -1\\Thus, \,T(n) = 2^{n} -1$$

Code

def hanoi(disks, source, aux, target ):
    # if len(disks) == 1:
    if disks > 0:
        hanoi(disks-1, source, target, aux)
        print("move disk ", disks, "from ", source, " ??", target )
        hanoi(disks - 1, aux, source, target)

---

2.1 Add array members

def sumArray(S):
    sum =0
    for i in range(len(S)):
        sum += S[i]
    return sum

2.2 Matrix multiplication

import numpy as np

def matrixMultiplication(n, A, B):
    C = np.zeros((n,n))

    for i in range(n):
        for j in range(n):
            C[i,j] = 0
            for k in range(n):
                C[i,j] = C[i,j] + A[i,k] * B[k,j]

    return C

2.3 nth Fibonacci term in recursive

def fibonacciRec(n):
    if n<= 1:
        return n
    else:
        return fibonacciRec(n-1)+fibonacciRec(n-2)

2.4 Binary search in recursive

def bSearchRec(S,low, high, x):
    if low> high:
        return -1
    mid = int(low + (high-low)/2)
    if x == S[mid]:
        return mid
    elif x< S[mid]:
        return bSearchRec(S, low, mid-1, x)
    else:
        return bSearchRec(S, mid+1, high, x)

2.5 Exchange sort

def exchangeSort(S):
    for i in range(len(S)-1):
        for j in range(i,len(S)):
            if S[j] < S[i]:
                tmp = S[i]
                S[i] = S[j]
                S[j] = tmp
    return S

2.6 A recursive algorithm for computing the nth power of 2

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

Uploaded by N2T