一、分治法
1.逆序对的数目
def merge_and_count(nums, temp_arr, left, mid, right):
"""
在合并过程中计数逆序对。
:param nums: 原始数组
:param temp_arr: 辅助数组
:param left: 左子数组起始点
:param mid: 左子数组与右子数组分界点
:param right: 右子数组结束点
:return: 当前合并步骤中逆序对的数量
"""
i = left # Starting index for left subarray
j = mid + 1 # Starting index for right subarray
k = left # Starting index to be sorted
inv_count = 0
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp_arr[k] = nums[i]
i += 1
else:
temp_arr[k] = nums[j]
inv_count += (mid-i + 1)
j += 1
k += 1
while i <= mid:
temp_arr[k] = nums[i]
i += 1
k += 1
while j <= right:
temp_arr[k] = nums[j]
j += 1
k += 1
for i in range(left, right + 1):
nums[i] = temp_arr[i]
return inv_count
def merge_sort_and_count(nums, temp_arr, left, right):
"""
使用递归来执行归并排序并在排序过程中计数逆序对。
:param nums: 原始数组
:param temp_arr: 辅助数组
:param left: 排序起始点
:param right: 排序结束点
:return: 总逆序对的数量
"""
inv_count = 0
if left < right:
mid = (left + right)//2
inv_count += merge_sort_and_count(nums, temp_arr, left, mid)
inv_count += merge_sort_and_count(nums, temp_arr, mid + 1, right)
inv_count += merge_and_count(nums, temp_arr, left, mid, right)
return inv_count
def count_inversions(nums):
"""
计算给定数组中的逆序对数量。
:param nums: 整数数组
:return: 逆序对数量
"""
temp_arr = [0]*len(nums)
return merge_sort_and_count(nums, temp_arr, 0, len(nums) - 1)
# 输入接口
if __name__ == "__main__":
user_input = input()
# 去掉中括号并分割字符串
nums_str = user_input.strip('[]')
nums = list(map(int, nums_str.split(',')))
print(count_inversions(nums))
2.快速幂计算
def fast_pow(a, b):
"""
使用分治法计算 a 的 b 次方（快速幂算法）。
参数:
a (float): 底数。
b (int): 指数，可以是正数、负数或 0。
返回:
float: a 的 b 次方的值。
"""
# 处理负数幂
if b < 0:
return 1 / fast_pow(a, -b)
# 边界条件
if b == 0:
return 1.0 # 返回浮点数 1.0
if b == 1:
return a
# 分治法递归计算
half = fast_pow(a, b // 2) # 计算 a^(b//2)
# 如果 b 是偶数
if b % 2 == 0:
return half * half
# 如果 b 是奇数
else:
return half * half * a
# 输入接口
if __name__ == "__main__":
base_input = input()
exponent_input = input()
try:
a = float(base_input)
b = int(exponent_input)
result = fast_pow(a, b)
print(result)
except ValueError:
print("输入无效，请确保底数是浮点数，指数是整数。")
# # 输入接口
# if __name__ == "__main__":
# user_input = input()
# print(fast_pow(user_input))
3.众数
from collections import Counter
def find_modes(s):
"""
找出多重集合 S 中的众数及其重数。
参数:
s (list): 包含元素的列表。
返回:
tuple: 众数及其重数。
"""
# 统计每个元素的出现次数
count = Counter(s)
# 找到最大重数
max_count = max(count.values())
# 找到所有具有最大重数的元素
modes = [num for num, freq in count.items() if freq == max_count]
return modes, max_count
# 输入接口
if __name__ == "__main__":
user_input = input()
s = list(map(int, user_input.split()))
modes, max_count = find_modes(s)
print()
for mode in modes:
print(mode)
print(max_count)
4.最大子序和
def max_crossing_sum(nums, left, mid, right):
"""
计算跨越中间点的最大子数组和。
参数:
nums (list): 包含整数的列表。
left (int): 左边界索引。
mid (int): 中间索引。
right (int): 右边界索引。
返回:
int: 跨越中间点的最大子数组和。
"""
# 包括中间点左边的最大子数组和
left_sum = float('-inf')
sum = 0
for i in range(mid, left - 1, -1):
sum += nums[i]
if sum > left_sum:
left_sum = sum
# 包括中间点右边的最大子数组和
right_sum = float('-inf')
sum = 0
for i in range(mid + 1, right + 1):
sum += nums[i]
if sum > right_sum:
right_sum = sum
return left_sum + right_sum
def max_subarray_sum_divide_and_conquer(nums, left, right):
"""
使用分治算法计算具有最大和的连续子数组，并返回其最大和。
参数:
nums (list): 包含整数的列表。
left (int): 左边界索引。
right (int): 右边界索引。
返回:
int: 最大子数组和。
"""
# 基本情况：只有一个元素
if left == right:
return nums[left]
mid = (left + right) // 2
# 递归计算左半部分的最大子数组和
left_sum = max_subarray_sum_divide_and_conquer(nums, left, mid)
# 递归计算右半部分的最大子数组和
right_sum = max_subarray_sum_divide_and_conquer(nums, mid + 1, right)
# 计算跨越中间点的最大子数组和
cross_sum = max_crossing_sum(nums, left, mid, right)
# 返回三者中的最大值
return max(left_sum, right_sum, cross_sum)
def find_max_subarray_sum(nums):
"""
找到具有最大和的连续子数组，并返回其最大和。
参数:
nums (list): 包含整数的列表。
返回:
int: 最大子数组和。
"""
if not nums:
return 0
return max_subarray_sum_divide_and_conquer(nums, 0, len(nums) - 1)
# 输入接口
if __name__ == "__main__":
user_input = input()
nums = list(map(int, user_input.split()))
result = find_max_subarray_sum(nums)
print(result)
5.求中位数
def partition(arr, low, high):
"""
分区操作，将数组分区并返回枢轴位置。
参数:
arr (list): 包含整数的列表。
low (int): 起始索引。
high (int): 结束索引。
返回:
int: 枢纽位置。
"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickselect(arr, low, high, k):
"""
快速选择算法，用于查找第 k 小的元素。
参数:
arr (list): 包含整数的列表。
low (int): 起始索引。
high (int): 结束索引。
k (int): 查找第 k 小的元素。
返回:
int: 第 k 小的元素。
"""
if low == high:
return arr[low]
pivot_index = partition(arr, low, high)
if k == pivot_index:
return arr[k]
elif k < pivot_index:
return quickselect(arr, low, pivot_index - 1, k)
else:
return quickselect(arr, pivot_index + 1, high, k)
def find_median(arr):
"""
找到数组的中位数。
参数:
arr (list): 包含整数的列表。
返回:
int: 数组的中位数。
"""
n = len(arr)
if n % 2 == 1:
# 奇数长度，直接找中间的那个
return quickselect(arr, 0, n - 1, n // 2)
else:
# 偶数长度，返回第 [n/2] 大的元素
return quickselect(arr, 0, n - 1, n // 2)
# 输入接口
if __name__ == "__main__":
user_input = input()
nums = list(map(int, user_input.split()))
median = find_median(nums)
print(median)
6.集合划分问题
def stirling_second_kind(n, m):
"""
计算第二类斯特林数 S(n, m)，表示将 n 个元素划分为 m 个非空子集的方法数。
参数:
n (int): 元素数量。
m (int): 子集数量。
返回:
int: 第二类斯特林数 S(n, m)。
"""
# 创建一个二维数组来存储中间结果
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 设置边界条件
dp[0][0] = 1
# 填充 dp 数组
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]
return dp[n][m]
# 输入接口
if __name__ == "__main__":
user_input = input()
n, m = map(int, user_input.split())
result = stirling_second_kind(n, m)
print(result)
