breadth first search

tree = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12],
        [13, 14], [], [], [], [], [], [], [], []]
data=[0]

while len(data)>0:
    pos=data.pop(0)
    print(pos,end=" ")
    for i in tree[pos]:
        data.append(i)

review tuple,list,dict

tuplefruits=("apple","banana","cherry","durain","eggplant")
fruits=list(tuplefruits)
fruits.pop(2) #把序號2拿掉
print(fruits) #['apple', 'banana', 'durain', 'eggplant']

fruits=list(tuplefruits)
fruits.remove("apple")  #把list fruists 內的 apple拿掉
print(fruits) #['banana', 'cherry', 'durain', 'eggplant']

fruits=list(tuplefruits)
fruits.append("fig")
print(fruits)   #['apple', 'banana', 'cherry', 'durain', 'eggplant', 'fig']

fruits=list(tuplefruits)
fruits.insert(3,"加入的水果")
print(fruits) #['apple', 'banana', 'cherry', '加入的水果', 'durain', 'eggplant']

fruits=list(tuplefruits)
fruits.append("只加在最後")
print(fruits) #['apple', 'banana', 'cherry', 'durain', 'eggplant', '只加在最後']

=================
dict

dictfruits={"apple":10,"banana":20,"cherry":30,"durain":40,"eggplant":50}
dictfruits["fig"]=60
print(dictfruits)

del dictfruits["fig"]
print(dictfruits)

binary search

def binary_search(data,value):

    left=0

    right=len(data)-1

    while left<=right:

        mid=(left+right)//2

        if data[mid]==value:

            return mid

        elif data[mid]<value:

            left=mid+1

        else:

            right=mid+1

    return -1

list02=[10,20,30,40,50,60]

found=binary_search(list02,50)

if found==(-1):

    print("此值在list內找不到")

else:

    print("此值{}在list內找到了".format(list02[found]))

Linear Search (線性搜尋)

 複雜度  O(n)

Linear Search 又叫 Sequential Search

linearlist=[10,20,30,40,50]
found=False
for i in range(len(linearlist)):
    if linearlist[i]==50:
        print("數字{}是在裡面".format(linearlist[i]))
        found=True
        break
if not found:
         print("數字{}不是在裡面".format(linearlist[i]))

<定義一個linear search 函式>

def linear_search(data,value):
    for i in range(len(data)):
        if data[i]==value:
            return i
    return -1
list01=[10,20,30,40,50]
found=linear_search(list01,40)
if found==(-1):
    print("該值沒在此list內")
else:
    print("此{}在list內".format(list01[found]))

fibonacci

def fibonacci(n):
    if (n==1) or (n==2):
        return 1
    return fibonacci(n-1)+fibonacci(n-2)
print (fibonacci(10))

以 set 來表示

memo1={1:1,2:1}
def fibonacci(n):
    if n in memo1:
        return memo1[n]
    memo1[n]=fibonacci(n-2)+fibonacci(n-1)
    return memo1[n]
print(fibonacci(6))

以 list 呈現

def fibonacci(n):
    fib=[1,1]
    for i in range(2,n):
        fib.append(fib[i-2]+fib[i-1])
    return fib[n-1]
print(fibonacci(6))

上小節驗算

fib=[1,1]
for i in range(2,6):
    fib.append(fib[i-2]+fib[i-1])
    print(fib)