破解25道数学难题，挑战你的智慧极限！

题目1：数列求和

题目描述

给定一个数列，求出该数列的和。

解题思路

使用循环结构遍历数列中的每个元素，将其累加到总和中。

代码示例

def sum_sequence(sequence):
    total = 0
    for number in sequence:
        total += number
    return total

# 测试
sequence = [1, 2, 3, 4, 5]
print(sum_sequence(sequence))  # 输出应为 15

题目2：最大公约数

题目描述

求两个正整数的最大公约数。

解题思路

使用辗转相除法（欧几里得算法）求解。

代码示例

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 测试
print(gcd(48, 18))  # 输出应为 6

题目3：斐波那契数列

题目描述

编写一个函数，计算斐波那契数列的第n项。

解题思路

使用递归或循环结构计算斐波那契数列。

代码示例

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

# 测试
print(fibonacci(10))  # 输出应为 55

题目4：二分查找

题目描述

在一个已排序的数组中，查找一个特定的元素。

解题思路

使用二分查找算法，不断缩小查找范围。

代码示例

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 测试
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5))  # 输出应为 2

题目5：汉诺塔

题目描述

编写一个函数，打印出将n个盘子从源塔移动到目标塔的步骤。

解题思路

使用递归方法，将问题分解为更小的子问题。

代码示例

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n-1, auxiliary, target, source)

# 测试
hanoi(3, 'A', 'C', 'B')

题目6：排列组合

题目描述

给定一个字符串，输出所有可能的排列。

解题思路

使用递归方法，将问题分解为更小的子问题。

代码示例

def permutations(s):
    if len(s) == 1:
        return [s]
    result = []
    for i in range(len(s)):
        m = s[i]
        rem = s[:i] + s[i+1:]
        for p in permutations(rem):
            result.append(m + p)
    return result

# 测试
print(permutations("abc"))  # 输出应为 ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

题目7：素数检测

题目描述

编写一个函数，判断一个数是否为素数。

解题思路

使用试除法，从2开始，检查到该数的平方根。

代码示例

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

# 测试
print(is_prime(29))  # 输出应为 True

题目8：汉明距离

题目描述

给定两个字符串，计算它们之间的汉明距离。

解题思路

使用异或运算，统计两个字符串对应位置上不同字符的数量。

代码示例

def hamming_distance(s1, s2):
    return bin(s1 ^ s2).count('1')

# 测试
print(hamming_distance("1001", "1110"))  # 输出应为 3

题目9：最长公共子序列

题目描述

给定两个字符串，找出它们的最长公共子序列。

解题思路

使用动态规划，构建一个二维数组来存储子问题的解。

代码示例

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    L = [[None] * (n + 1) for i in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i - 1] == Y[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])

    return L[m][n]

# 测试
print(longest_common_subsequence("AGGTAB", "GXTXAYB"))  # 输出应为 4

题目10：最大子数组和

题目描述

给定一个整数数组，找出一个具有最大子数组和的连续子数组。

解题思路

使用动态规划，记录到当前位置为止的最大子数组和。

代码示例

def max_subarray_sum(arr):
    max_so_far = max_ending_here = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

# 测试
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 输出应为 6

题目11：合并区间

题目描述

给定一个区间列表，合并所有重叠的区间。

解题思路

对区间进行排序，然后合并重叠的区间。

代码示例

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for current in intervals[1:]:
        prev_start, prev_end = merged[-1]
        curr_start, curr_end = current
        if prev_end >= curr_start:
            merged[-1] = (prev_start, max(prev_end, curr_end))
        else:
            merged.append(current)
    return merged

# 测试
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))  # 输出应为 [[1, 6], [8, 10], [15, 18]]

题目12：二叉树遍历

题目描述

编写一个函数，实现二叉树的先序、中序和后序遍历。

解题思路

使用递归方法，分别按照先序、中序和后序遍历的规则访问节点。

代码示例

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorder_traversal(root):
    if root:
        print(root.val, end=' ')
        preorder_traversal(root.left)
        preorder_traversal(root.right)

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val, end=' ')

# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Preorder traversal:")
preorder_traversal(root)
print("\nInorder traversal:")
inorder_traversal(root)
print("\nPostorder traversal:")
postorder_traversal(root)

题目13：图遍历

题目描述

编写一个函数，实现图的深度优先搜索（DFS）和广度优先搜索（BFS）。

解题思路

使用递归方法实现DFS，使用队列实现BFS。

代码示例

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            stack.extend(graph[vertex] - visited)

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            queue.extend(graph[vertex] - visited)

# 测试
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3, 2]
}

print("DFS:")
dfs(graph, 0)
print("\nBFS:")
bfs(graph, 0)

题目14：动态规划 - 斐波那契数列

题目描述

使用动态规划算法计算斐波那契数列的第n项。

解题思路

使用一个数组来存储已经计算过的斐波那契数，避免重复计算。

代码示例

def fibonacci_dp(n):
    if n <= 1:
        return n
    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])
    return fib[n]

# 测试
print(fibonacci_dp(10))  # 输出应为 55

题目15：动态规划 - 最长递增子序列

题目描述

给定一个无序数组，找出最长递增子序列的长度。

解题思路

使用动态规划，记录到当前位置为止的最长递增子序列长度。

代码示例

def longest_increasing_subsequence(arr):
    n = len(arr)
    lis = [1] * n
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)

# 测试
print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80]))  # 输出应为 6

题目16：动态规划 - 背包问题

题目描述

给定一个物品列表和背包容量，找出能够装入背包的物品的最大价值。

解题思路

使用动态规划，构建一个二维数组来存储子问题的解。

代码示例

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# 测试
weights = [1, 2, 4, 5]
values = [1, 4, 5, 7]
capacity = 8
print(knapsack(weights, values, capacity))  # 输出应为 9

题目17：贪心算法 - 最小硬币找零

题目描述

给定一个硬币的面额数组和一个找零金额，找出最少数量的硬币组合。

解题思路

使用贪心算法，从最大面额的硬币开始，尽量使用更多的硬币。

代码示例

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

# 测试
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出应为 3

题目18：贪心算法 - 活动选择

题目描述

给定一个活动列表，每个活动都有一个开始时间和结束时间，选择一个最大数量的不相交活动。

解题思路

使用贪心算法，选择结束时间最早的活动，然后从下一个活动的开始时间开始继续选择。

代码示例

def activity_selection(start_times, end_times):
    n = len(start_times)
    activities = sorted(range(n), key=lambda i: end_times[i])
    count = 1
    last_end_time = end_times[activities[0]]
    for i in range(1, n):
        if start_times[activities[i]] >= last_end_time:
            count += 1
            last_end_time = end_times[activities[i]]
    return count

# 测试
start_times = [1, 3, 0, 5, 8, 5]
end_times = [2, 4, 6, 7, 9, 9]
print(activity_selection(start_times, end_times))  # 输出应为 4

题目19：贪心算法 - 最短路径

题目描述

给定一个加权有向图，使用Dijkstra算法找到从源点到所有其他点的最短路径。

解题思路

使用贪心算法，每次选择当前未访问节点中距离源点最近的节点。

代码示例

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

# 测试
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {}
}
print(dijkstra(graph, 'A'))  # 输出应为 {'A': 0, 'B': 1, 'C': 3, 'D': 4}

题目20：贪心算法 - 股票买卖

题目描述

给定一个股票价格数组，找出最大利润的买卖点。

解题思路

使用贪心算法，每次卖出股票时，都要确保卖出价格高于买入价格。

代码示例

def max_profit(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit

# 测试
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # 输出应为 7

题目21：贪心算法 - 最长不重复子串

题目描述

给定一个字符串，找出最长的无重复字符子串的长度。

解题思路

使用贪心算法，使用一个滑动窗口来记录当前的最长不重复子串。

代码示例

def length_of_longest_substring(s):
    start = 0
    max_len = 0
    char_index = {}
    for end in range(len(s)):
        if s[end] in char_index:
            start = max(start, char_index[s[end]] + 1)
        char_index[s[end]] = end
        max_len = max(max_len, end - start + 1)
    return max_len

# 测试
s = "abcabcbb"
print(length_of_longest_substring(s))  # 输出应为 3

题目22：贪心算法 - 最小硬币找零

题目描述

给定一个硬币的面额数组和一个找零金额，找出最少数量的硬币组合。

解题思路

使用贪心算法，从最大面额的硬币开始，尽量使用更多的硬币。

代码示例

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

# 测试
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出应为 3

题目23：贪心算法 - 活动选择

###