uplpa: 9月 2019

2019年9月29日星期日

廣度優先搜尋(breadth first search)

節點(node)
邊(edge)
有向圖(directed graph)
無向圖(undirected graph)
佇列(queue) FIFO(first in first out)
堆疊(stack) FILO (first in last out)

2019年9月10日星期二

快速排序法(quickSort)二

list 運用

list01=[88,5,3,77,33,22]

less=[i for i in list01 if i<=22]

larger=[j for j in list01 if j>22]

print(less)

print(larger)

==============
def qs(list):

if (len(list)<2):
return list
else:
pivot=list[0]
less=[i for i in list[1:] if i<=pivot]
larger=[i for i in list[1:] if i>pivot]
return qs(less)+[pivot]+qs(larger)
list01=[12,42,245,24,88,77]
print(qs(list01))

快速排序法

quick sort
wiki
https://zhuanlan.zhihu.com/p/21839027

原地排序
def quick_sort(alist, first, last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high= high - 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low =low + 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist, first, low-1)
quick_sort(alist, low+1, last)

numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)

===============
def quick_sort(alist, first, last):
print("alist是{},first是{},last是{}".format(alist,first,last))
if first >= last:
return
mid_value = alist[first]
print("mid_value是{}".format(mid_value))
low = first
print("low是{}".format(low))
high = last
print("high是{}".format(high))
while low < high:
while low < high and alist[high] >= mid_value:
high =high-1
print("high是{}".format(high))
alist[low] = alist[high]
print("alist[low]是{}".format(alist[high]))
while low < high and alist[low] < mid_value:
low =low+1
print("low是{}".format(low))
alist[high] = alist[low]
print("alist[higt]是{}".format(alist[high]))
alist[low] = mid_value
quick_sort(alist, first, low-1)
print("quick_sort(alist, first, low-1)是{}".format(alist))
quick_sort(alist, low+1, last)
print("quick_sort(alist, low+1, last)是{}".format(alist))
numbers = [9, 8, 7, 6, 99, 4, 3, 2, 56, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)

簡單版本

《Python cookbook 第二版》 from 知乎

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

一行語法


qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

2019年9月5日星期四

list 相關函數

list01=[3,5,33,55,8,12]
print(list01)
list01.append(list01.pop(2)) #即list01增加為 list01移除的第二索引值
print (list01)

執行後為

[3, 5, 33, 55, 8, 12]   
[3, 5, 55, 8, 12, 33]

===============

list01=[3,5,33,55,8,12]
list02=["蘋果","香蕉","柳丁","葡萄","鳳梨"]
print(list01)
print(list02)
list01.append(list02.pop(2))
print (list01)
print(list02)

執行後為

[3, 5, 33, 55, 8, 12]
['蘋果', '香蕉', '柳丁', '葡萄', '鳳梨']
[3, 5, 33, 55, 8, 12, '柳丁']
['蘋果', '香蕉', '葡萄', '鳳梨']

2019年9月2日星期一

遞迴演算法

遞迴演算法
定義：演算法(函式)中有呼叫自己(Self Calling)的敘述

from http://notepad.yehyeh.net/Content/DS/CH02/1.php
from https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-11ed5d300d3d
===========

def factorial(n):
if n==0 or n==1:
return 1
else:
return n*factorial(n-1)
print(factorial(5))

===========
def f(n):
if (n==1):
re=1
else:
re=n*f(n-1)
print(n,"階乘等於",re)
return re
n=int(input("enter number?"))
result=f(n)
print(n,"階乘等於",result)

==============from https://sites.google.com/site/zsgititit/home/python-cheng-shi-she-ji/di-hui-python

2019年9月29日 星期日