【算法】算法学习八：图解算法书中全部代码总结（含源代码）

ゝ一世哀愁。 2023-10-12 08:33 54阅读 0赞

#### 文章目录 ####

*  一、二分查找
 *  二、选择排序
 *  三、递归
 *  四、调用栈
 *  五、递归调用栈
 *  六、分而治之
 *  七、快速排序
 *  八、散列表
 *  九、广度优先搜索
 *  十、深度优先搜索
 *  十一、狄克斯特拉
 *  十二、贪婪算法
 *  十三、动态规划

## 一、二分查找 ##

def binary_search(lst, target):
        low = 0
        high = len(lst) - 1
        while low <= high:
            mid = (low + high) // 2
            guess = lst[mid]
            if guess < target:
                low += 1
            elif guess > target:
                high -= 1
            else:
                return mid
        return None
    
    lst = [1, 2, 3, 4, 5, 6]
    target = 6
    binary_search(lst, target)

输出结果为：

## 二、选择排序 ##

# 获取最小的数字的索引
    def get_small_idx(lst):
        small_num = lst[0]
        small_idx = 0
        for i in range(1, len(lst)):
            if lst[i] < small_num:
                small_num = lst[i]
                small_idx = i
        return small_idx
    
    # 选择排序
    def selection_sort(lst):
        new_lst = []
        for i in range(len(lst)):
            small_idx = get_small_idx(lst)
            new_lst.append(lst.pop(small_idx))
        return new_lst
    
    lst = [5, 3, 8, 4, 1, 0, 2]
    selection_sort(lst)

输出结果为：

[0, 1, 2, 3, 4, 5, 8]

## 三、递归 ##

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

输出结果为：

5
    4
    3
    2
    1

## 四、调用栈 ##

def greet2(name):
        print("How are you? " + name + " !")
    
    def bye():
        print("OK, bye!")
    
    def greet(name):
        print("Hello, " + name + " !")
        greet2('Mike')
        bye()
        print('Bye!')
    
    greet('Tom')

输出结果为：

Hello, Tom !
    How are you? Mike !
    OK, bye!
    Bye!

## 五、递归调用栈 ##

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

输出结果为：

120

## 六、分而治之 ##

# 编写求和的函数
    def get_sum(lst):
        if lst == []:
            return 0
        else:
            return lst[0] + get_sum(lst[1:])
    
    get_sum([1, 2, 3, 4, 5])

输出结果为：

## 七、快速排序 ##

def get_quick_sort(lst):
        if len(lst) < 2:
            return lst # 基线条件
        else:
            base_num = lst[0]
            less = [i for i in lst[1:] if i < base_num]
            more = [i for i in lst[1:] if i > base_num]
        return get_quick_sort(less) + [base_num] + get_quick_sort(more)
    
    lst = [5, 3, 8, 4, 1, 0, 2]
    get_quick_sort(lst)

输出结果为：

[0, 1, 2, 3, 4, 5, 8]

## 八、散列表 ##

phone_book = dict()
    phone_book['Mike'] = 123456
    phone_book['Tom'] = 23456
    phone_book

输出：

{
        'Mike': 123456, 'Tom': 23456}

voted = {
        }
    def check_vote(name):
        if voted.get(name):
            print("Kick him out!")
        else:
            voted[name] = True
            print('Let he vote!')
    check_vote('Tom')

输出：

Let he vote!

check_vote('Tom')

输出：

Kick him out!

## 九、广度优先搜索 ##

from collections import deque
    
    def bfs(graph, start, target):
        queue = deque()  # 创建一个空队列
        visited = set()  # 记录已访问过的节点
        queue.append((start, [start]))  # 初始节点入队
    
        while queue:
            node, path = queue.popleft()  # 出队一个节点
            visited.add(node)  # 将节点标记为已访问
    
            if node == target:
                return path  # 找到目标节点，返回路径
    
            neighbors = graph[node]  # 获取当前节点的邻居节点
            for neighbor in neighbors:
                if neighbor not in visited:
                    queue.append((neighbor, path + [neighbor]))  # 邻居节点入队，将路径更新
    
        return None  # 没有找到路径
    
    # 测试代码
    graph = {
        
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    start_node = 'A'
    target_node = 'F'
    shortest_path = bfs(graph, start_node, target_node)
    if shortest_path:
        print(f"Shortest path from {
          start_node} to {
          target_node}: {
          ' -> '.join(shortest_path)}")
    else:
        print(f"There is no path from {
          start_node} to {
          target_node}.")

输出结果为：

Shortest path from A to F: A -> C -> F

from collections import deque
    
    queue = deque()  # 创建一个空队列
    
    # 入队
    queue.append(1)
    queue.append(2)
    queue.append(3)
    
    # 出队
    while queue:
        item = queue.popleft()
        print("Dequeued:", item)

输出结果为：

Dequeued: 1
    Dequeued: 2
    Dequeued: 3

## 十、深度优先搜索 ##

def dfs(graph, node, visited):
        visited.add(node)  # 将节点标记为已访问
        print("Visited node:", node)
    
        neighbors = graph[node]  # 获取当前节点的邻居节点
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs(graph, neighbor, visited)  # 递归调用DFS
    
    # 测试代码
    graph = {
        
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    visited = set()  # 记录已访问过的节点
    dfs(graph, 'A', visited)

输出结果为：

Visited node: A
    Visited node: B
    Visited node: D
    Visited node: E
    Visited node: F
    Visited node: C

## 十一、狄克斯特拉 ##

import sys
    
    def dijkstra(graph, source):
        # 初始化距离字典
        dist = {
        node: sys.maxsize for node in graph}
        dist[source] = 0
    
        # 初始化访问过的节点集合
        visited = set()
    
        while len(visited) < len(graph):
            # 选择距离最短的节点
            min_dist = sys.maxsize
            min_node = None
            for node in graph:
                if node not in visited and dist[node] < min_dist:
                    min_dist = dist[node]
                    min_node = node
    
            # 将选择的节点标记为已访问
            visited.add(min_node)
    
            # 更新与选择节点相邻节点的最短距离
            for neighbor, weight in graph[min_node].items():
                new_dist = dist[min_node] + weight
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
    
        return dist
    
    # 定义图的邻接表表示
    graph = {
        
        1: {
        2: 5, 4: 4},
        2: {
        3: 3},
        3: {
        },
        4: {
        2: 2, 5: 1},
        5: {
        3: 6, 6: 4},
        6: {
        }
    }
    
    source_node = 1
    distances = dijkstra(graph, source_node)
    
    # 打印最短路径
    for node, distance in distances.items():
        if distance == sys.maxsize:
            distance = "无穷大"
        print(f"节点 {
          source_node} 到节点 {
          node} 的最短距离为：{
          distance}")

输出结果为：

节点 1 到节点 1 的最短距离为：0
    节点 1 到节点 2 的最短距离为：5
    节点 1 到节点 3 的最短距离为：8
    节点 1 到节点 4 的最短距离为：4
    节点 1 到节点 5 的最短距离为：5
    节点 1 到节点 6 的最短距离为：9

## 十二、贪婪算法 ##

state_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])
    stations = {
        }
    stations['kone'] = set(['id', 'nv', 'ut'])
    stations['ktwo'] = set(['wa', 'id', 'mt'])
    stations['kthree'] = set(['or', 'nv', 'ca'])
    stations['kfour'] = set(['nv', 'ut'])
    stations['kfive'] = set(['ca', 'az'])
    final_stations = set()
    while state_needed:
        best_station = None
        station_covered = set()
        for station, states_for_station in stations.items():
            covered = state_needed & states_for_station
            if len(covered) > len(station_covered):
                best_station = station
                station_covered = covered
        state_needed -= station_covered
        final_stations.add(best_station)

final_stations

输出结果为：

{
        'kfive', 'kone', 'kthree', 'ktwo'}

## 十三、动态规划 ##

def knapsack_dynamic_programming(weights, values, capacity):
        n = len(weights)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
        for i in range(1, n + 1):
            for j in range(1, capacity + 1):
                if weights[i - 1] <= j:
                    dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
                else:
                    dp[i][j] = dp[i - 1][j]
    
        # 构造最优解
        selected_items = []
        i, j = n, capacity
        while i > 0 and j > 0:
            if dp[i][j] != dp[i - 1][j]:
                selected_items.append(i - 1)
                j -= weights[i - 1]
            i -= 1
    
        return dp[n][capacity], selected_items
    
    
    # 示例用法
    weights = [4, 3, 1]
    values = [3000, 2000, 1500]
    capacity = 4
    
    max_value, selected_items = knapsack_dynamic_programming(weights, values, capacity)
    print("Max Value:", max_value)
    print("Selected Items:", selected_items)

输出结果为：

Max Value: 3500
    Selected Items: [2, 1]

一个语法的展示：

n = 3
    capacity = 4
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    dp

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

最长公共子串：

def longest_common_substring(str1, str2):
        m = len(str1)
        n = len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_length = 0
        end_index = 0
    
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    if dp[i][j] > max_length:
                        max_length = dp[i][j]
                        end_index = i
    
        longest_substring = str1[end_index - max_length:end_index]
        return longest_substring
    
    
    # 示例用法
    str1 = "abcdefg"
    str2 = "xyzabcd"
    result = longest_common_substring(str1, str2)
    print("Longest Common Substring:", result)

Longest Common Substring: abcd

最长公共子序列：

def longest_common_subsequence(str1, str2):
        m = len(str1)
        n = len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
    
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
        # 构造最长公共子序列
        i, j = m, n
        longest_subsequence = ""
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                longest_subsequence = str1[i - 1] + longest_subsequence
                i -= 1
                j -= 1
            elif dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
    
        return longest_subsequence
    
    
    # 示例用法
    str1 = "ABCD"
    str2 = "ACDF"
    result = longest_common_subsequence(str1, str2)
    print("Longest Common Subsequence:", result)

输出结果为：

Longest Common Subsequence: ACD