首页 > 编程语言 > 详细

《算法图解》源代码

时间:2019-12-23 19:42:13      阅读:177      评论:0      收藏:0      [点我收藏+]

二分查询:

def binary_search(list, item):
    low = 0
    high = len(list)-1


    while low <= high:
        mid = (low + high) / 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

选择排序:

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))

递归排序:

def countdown(i):
    print(i)
    if i <= 1:
        return
    else:
        countdown(i - 1)

调用栈:

def greet(name):
    print(hello,  + name + !)
    greet2(name)
    print(getting ready to say by...)
    bye()

def greet2(name):
    print(how are you,  + name + ?)

def bye():
    print(ok bye!)

递归调用栈:

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)

快速排序:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]

        greater = [i for i in array[1:] if i > pivot]

        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

散列表:

cache = {}


def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data



voted = {}


def check_voter(name):
    if voted.get(name):
        print(kick them out!)
    else:
        voted[name] = True
        print(let them vote!)

广度优先搜索:

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person +  is a mango seller!)
            else:
                search_queue += graph[person]
                searched.append(person)
    return False


search(you)

狄克斯特拉算法:

parents = {}
parents[a] = start
parents[b] = start
parents[fin] = None
processed = []


def find_lowest_cost_node(costs):
    lowest_cost = float(inf)
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node
    

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

贪婪算法:

stations = {}
stations[kone] = {id, nv, ut}
stations[ktwo] = {wa, id, mt}
stations[kthree] = {or, nv, ca}
stations[kfour] = {nv, ut}
stations[kfive] = {ca, az}

stations_needed = {mt, wa, or, id, nv, ut, ca, az}
final_stations = set()


while stations_needed:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = stations_needed & states_for_station
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered

    stations_needed -= states_covered
    final_stations.add(best_station)


print(final_stations)

《算法图解》源代码

原文:https://www.cnblogs.com/HannahGreen/p/12085052.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!