# Python 数据结构和算法实用指南（四）（2）

Python 数据结构和算法实用指南（四）（1）https://developer.aliyun.com/article/1507636

## 好后缀启发式

1. 匹配的后缀在模式中有一个或多个出现。
2. 匹配后缀的某部分存在于模式的开头（这意味着匹配后缀的后缀存在于模式的前缀中）。

Boyer-Moore 算法在模式的预处理中需要O(m)的时间，进一步搜索需要O(mn)的时间复杂度。

## 实现 Boyer-Moore 算法

text[i+j+k:i+len(pattern)] not in pattern[0:len(pattern)-1]

Boyer-Moore 算法的完整实现如下所示：

text= "acbaacacababacacac"
pattern = "acacac"
matched_indexes = []
i=0
flag = True
while i<=len(text)-len(pattern):
for j in range(len(pattern)-1, -1, -1): #reverse searching
if pattern[j] != text[i+j]:
flag = False #indicates there is a mismatch
if j == len(pattern)-1: #if good-suffix is not present, we test bad character
if text[i+j] in pattern[0:j]:
i=i+j-pattern[0:j].rfind(text[i+j]) #i+j is index of bad character, this line is used for jumping pattern to match bad character of text with same character in pattern
else:
i=i+j+1 #if bad character is not present, jump pattern next to it
else:
k=1
while text[i+j+k:i+len(pattern)] not in pattern[0:len(pattern)-1]: #used for finding sub part of a good-suffix
k=k+1
if len(text[i+j+k:i+len(pattern)]) != 1: #good-suffix should not be of one character
gsshift=i+j+k-pattern[0:len(pattern)-1].rfind(text[i+j+k:i+len(pattern)]) #jumps pattern to a position where good-suffix of pattern matches with good-suffix of text
else:
#gsshift=i+len(pattern)
gsshift=0 #when good-suffix heuristic is not applicable, we prefer bad character heuristic
if text[i+j] in pattern[0:j]:
bcshift=i+j-pattern[0:j].rfind(text[i+j]) #i+j is index of bad character, this line is used for jumping pattern to match bad character of text with same character in pattern
else:
bcshift=i+j+1
i=max((bcshift, gsshift))
break
if flag: #if pattern is found then normal iteration
matched_indexes.append(i)
i = i+1
else: #again set flag to True so new string in text can be examined
flag = True
print ("Pattern found at", matched_indexes)

• 算法的分类
• 各种算法设计方法
• 各种重要算法的实现和解释

## 斐波那契数列

func(1) = 1
func(0) = 1
func(n) = func(n-1) + func(n-2)

## 记忆化技术

1 1 2 3 5

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

return fib(n-1) + fib(n-2)

def dyna_fib(n, lookup):
if n <= 2:
lookup[n] = 1
if lookup[n] is None:
lookup[n] = dyna_fib(n-1, lookup) + dyna_fib(n-2, lookup)
return lookup[n]

map_set = [None]*(1000)

if n <= 2:
lookup[n] = 1 

lookup[n]的条件写为以下内容：

if lookup[n] is None:
lookup[n] = dyna_fib(n-1, lookup) + dyna_fib(n-2, lookup)

## 表格法

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

results变量在索引 0 和 1 处存储值 1 和 1。这代表fib(1)fib(2)的返回值。要计算大于 2 的值的fib()函数的值，我们只需调用for循环，将results[i-1] + results[i-2]的和附加到结果列表中。

## 归并排序

def merge_sort(unsorted_list):
if len(unsorted_list) == 1:
return unsorted_list
mid_point = int((len(unsorted_list))//2)
first_half = unsorted_list[:mid_point]
second_half = unsorted_list[mid_point:]
half_a = merge_sort(first_half)
half_b = merge_sort(second_half)
return merge(half_a, half_b) 

first_half = unsorted_list[:mid_point]
second_half = unsorted_list[mid_point:] 

half_a = merge_sort(first_half)
half_b = merge_sort(second_half)

def merge(first_sublist, second_sublist):
i = j = 0
merged_list = []
while i < len(first_sublist) and j < len(second_sublist):
if first_sublist[i] < second_sublist[j]:
merged_list.append(first_sublist[i])
i += 1
else:
merged_list.append(second_sublist[j])
j += 1
while i < len(first_sublist):
merged_list.append(first_sublist[i])
i += 1
while j < len(second_sublist):
merged_list.append(second_sublist[j])
j += 1
return merged_list 

merge函数接受我们要合并的两个列表first_sublistsecond_sublistij变量被初始化为 0，并用作指针，告诉我们在合并过程中两个列表的位置。

while i < len(first_sublist) and j < len(second_sublist):
if first_sublist[i] < second_sublist[j]:
merged_list.append(first_sublist[i])
i += 1
else:
merged_list.append(second_sublist[j])
j += 1 

while循环开始比较first_sublistsecond_sublist中的元素。if语句选择两者中较小的一个，first_sublist[i]second_sublist[j]，并将其附加到merged_listij索引递增以反映我们在合并步骤中的位置。当任一子列表为空时，while循环停止。

merge(half_a, half_b)的最后调用将返回排序后的列表。

 步骤 first_sublist second_sublist merged_list 步骤 0 [4 6 8] [5 7 11 40] [] 步骤 1 [ 6 8] [5 7 11 40] [4] 步骤 2 [ 6 8] [ 7 11 40] [4 5] 步骤 3 [ 8] [ 7 11 40] [4 5 6] 步骤 4 [ 8] [ 11 40] [4 5 6 7] 步骤 5 [ ] [ 11 40] [4 5 6 7 8] 步骤 6 [] [ ] [4 5 6 7 8 11 40]

## 硬币计数问题

1. 我们对面额列表{a[1], a[2], a[3] ...a[n]}进行排序。
2. 我们得到小于 A 的{a[1], a[2], a[3]...a[n]}中的最大面额。
3. 我们通过将 A 除以最大面额来获得商。
4. 我们通过使用（A % 最大面额）来获得剩余金额 A。
5. 如果 A 的值变为 0，则返回结果。
6. 否则，如果 A 的值大于 0，我们将最大面额和商变量附加到结果变量中。并重复步骤 2-5。

def basic_small_change(denom, total_amount):
sorted_denominations = sorted(denom, reverse=True)
number_of_denoms = []
for i in sorted_denominations:
div = total_amount // i
total_amount = total_amount % i
if div > 0:
number_of_denoms.append((i, div))
return number_of_denoms

for i in sorted_denominations:
div = total_amount // i
total_amount = total_amount % i
if div > 0:
number_of_denoms.append((i, div)) 

def optimal_small_change(denom, total_amount):
sorted_denominations = sorted(denom, reverse=True)
series = []
for j in range(len(sorted_denominations)):
term = sorted_denominations[j:]
number_of_denoms = []
local_total = total_amount
for i in term:
div = local_total // i
local_total = local_total % i
if div > 0:
number_of_denoms.append((i, div))
series.append(number_of_denoms)
return series

for j in range(len(sorted_denominations)):
term = sorted_denominations[j:]
...     

Python 数据结构和算法实用指南（四）（3）https://developer.aliyun.com/article/1507647

|
2天前
|

【Python核心数据结构探秘】：元组与字典的完美协奏曲
【Python核心数据结构探秘】：元组与字典的完美协奏曲
11 0
|
2天前
|

【数据结构与算法】：手搓顺序表（Python篇）
【数据结构与算法】：手搓顺序表（Python篇）
8 1
|
2天前
|

Python零基础入门-5 数据结构（集合和字典）
Python零基础入门-5 数据结构（集合和字典）
7 1
|
2天前
|

Python零基础入门-5 数据结构（列表和元组
Python零基础入门-5 数据结构（列表和元组
8 1
|
3天前
|

10 3
|
3天前
|

12 2
|
3天前
|

12 1
|
3天前
|

13 2
|
2天前
|

**摘要：** 使用禁忌搜索算法解决旅行商问题（TSP），在MATLAB2022a中实现路径规划，显示优化曲线与路线图。TSP寻找最短城市访问路径，算法通过避免局部最优，利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
12 1
|
2天前
|

markdown 探索烟草香型分类：使用Matlab2022a中的BP神经网络结合小波变换。小波分析揭示香气成分的局部特征，降低维度，PCA等用于特征选择。BP网络随后处理这些特征，以区分浓香、清香和中间香型。 
6 1