Python简单算法

本文由Hobee原创，仅供各位小伙伴学习交流使用。

为避免不必要的纠纷，本文禁止以任何形式转载，谢谢配合。

如有问题请通过评论区或邮件联系作者。

本文封面图片来源于 Jim Zhang 。

算法

算法的定义：算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列。
计算机求解任何问题都要依赖于算法。
五项基本特征：有穷、确定、输入、输出、可行。
算法的描述：自然语言、计算机语言、图形化工具、伪代码。
数据结构是算法设计的基础。

枚举

定义

按问题本身的性质，通过多重循环一一列举出该问题所有可能的解（不能遗漏，也不能重复），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，采用这个解，否则，抛弃它。

基本思想

首先依据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的解逐一验证，直到全部验证完毕为止。

设计思路

明确枚举的对象：求解变量。
确定问题解的可能搜索的范围：用循环或循环嵌套结构实现。
写出符合问题的解的条件：采用if语句。
使用能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。

适用范围

解方程组、求极值，但数据量不大

举例

无线网络发射器选址

d=int(input())
n=int(input())
ditu=[]
ls=[]
ditu_str="0 "*(129+2*d)
for i2 in range(129+2*d):
    ditu.append(list(map(int,ditu_str.split())))
for i3 in range(n):
    x=list(map(int,input().split()))
    ditu[x[0]+d][x[1]+d]=x[2]
for i in range(129):
    for j in range(129):
        i_d=i+d
        j_d=j+d
        loc=ditu[i_d][j_d]
        for c in range(d):
            loc+=ditu[i_d+1+c][j_d]+ditu[i_d-1-c][j_d]
            loc+=ditu[i_d][j_d+1+c]+ditu[i_d][j_d-1-c]
            for a in range(d):
                loc+=ditu[i_d+1+c][j_d+1+a]+ditu[i_d+1+c][j_d-1-a]+ditu[i_d-1-c][j_d-1-a]+ditu[i_d-1-c][j_d+1+a]
        ls.append(loc)
maxout=max(ls)
count=ls.count(maxout)
print("{} {}".format(count,maxout))

递归

定义

函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象

基本思想

把原问题分解为更小的子问题，再从子问题里慢慢寻找原问题的解

设计思路

解题时首先列出递归表达式，然后用程序设计语言的方式把它表现出来
往往递归都可转化为循环或者模拟调用栈来实现，但是递归表达更利于理解

适用范围

问题的定义是递归的 Fibonacci函数
数据的结构是按递归定义的树的遍历
问题的建模策略需要使用递归法去实现分治法、回溯法

举例

逛超市

def f(x, y, n):
    if n == 1:
        return x, y
    else:
        return f(0.2*x+0.6*y, 0.8*x+0.4*y, n-1)
n = int(input())
x, y = map(int, input().split())
x, y = f(x, y, n)
print(int(x), int(y))

贪心

基本思想

将待求解的问题分解成若干个子问题进行分步求解，且每一步总是做出当前最好的选择，以期得到问题最优解。

设计思路

将待求解的问题分解成若干个子问题
每个子问题的解总是当前最好的选择

举例

我不是盘神

n = int(input())
File = []
XXXDownLoad = [0]
XXNetDisk = [0,0]
for i in range(n):
    File.append(int(input()))
File.sort()
print(sum(File[:len(File)//3]))
print(' '.join(list(map(str,File[:len(File)//3]))))

动归

定义

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

基本思想

将待求解的问题分解成若干相互联系的子问题，先求解子问题，然后根据子问题之间的关系来得到原问题的解在计算过程中每个子问题只求解一次，将其结果保存在一张表（最优决策表）中，以便在需要时直接使用。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，它们可能共享更小的子问题，即重叠子问题。

设计思路

将问题分解为若干相互联系的子问题。
写出状态转移方程，求解子问题。
根据子问题之间的关系来得到原问题的解。

适用范围

重叠子问题：子问题间不相互独立，包含公共子问题
最优子结构：问题的最优解包含其子问题的最优解，一个最优化策略的子策略总是最优的
无后效性：某阶段状态一旦确定，就不受这个状态以后决策的影响。即某状态以后的过程不会影响以前的状态，只与当前状态有关

举例

数字三角形

def best_road(n,a):
    ans = [[0]]
    for i in range(n):
        temp = []
        for j in range(i+1):
            if j == 0 :
                temp.append(a[i][j]+ans[i][j])
            elif j == i:
                temp.append(a[i][j]+ans[i][j-1])
            else:
                temp.append(a[i][j]+max(ans[i][j],ans[i][j-1]))
        ans.append(temp)
    return max(ans[-1])
n = int(input())
tri = []
for i in range(n):
    tri.append(list(map(lambda x:int(x),input().split())))
print(best_road(n,tri))

查找

从数据集合中找到某个或某些特定的数据，并提供它（或它们）所在的位置，这个过程称为查找。

查找是一个程序中最消耗时间的一部分。

线性查找

直接从头到尾搜索集合的查找键，直到找出与查找键相同的数据为止。

原理

从线性表的一端开始，顺序扫描线性表，依次将线性表中每个元素与查找键相比较，若当前扫描的元素与查找键相等，则查找成功，返回索引；若整个表扫描完毕都未能找到与查找键匹配的元素，则查找失败。

缺点

当数据量较大时，效率低下。

代码示例

def line_search(List):
	for i in range(len(List)):
    	if List[i] == value:
        	return i

二分查找

必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合的查找键。

原理

查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果待查找元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较；
如果在某一步骤数组为空，则代表找不到；

代码示例

def BinarySearch(List,value,n = 0):
    m = len(List)//2
    if List[m] == value:
        return n + m
    elif List[m] < value:
        return BinarySearch(List[m+1:],value,m)
    else:
        return BinarySearch(List[:m],value,0)

哈希查找

以线性表中每个元素的关键字key为自变量，计算哈希函数值，以该值作为地址，将元素存入哈希表中；查找某元素时，先计算其哈希函数值，再在哈希表中查找该地址对应的存储单元。

哈希查找算法是计算机中查找数据的最快的方法

原理

为每个待搜索的元素根据某个函数计算出一个存储地址（哈希地址），按地址将每个元素存入一个表中
当要查找某元素时，根据地址精确定位需要查找的元素

排序

将一组原始数据按递增或递减的规律进行重新排列的过程。

常见的排序算法有选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、堆排序、加速堆排序、梳排序等

选择排序

原理

首先在所有列表元素中找出最大值的元素，放在A[0]中；接着在不包含A[0]的余下的数组元素中再找出最大值的元素，放置在A[1]中；如此下去，一直到最后一个元素。

代码示例

def Choose(List):
    ans = []
    for i in range(len(List)):
        ans.append(max(List))
        List.remove(max(List))
    return ans

def choose(List):# 降序
    for i in range(len(List)):
        c = max(List[i:])
        d = List[i:].index(c)
        List[i],List[i+d] = List[i+d],List[i]

冒泡排序

原理

在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较和交换，将大的放前，小的放后，递减排序。对于n个数据，最多经过n-1轮的比较，即可按降序排序。

代码示例

def maopao(List):#升序
    for i in range(len(List)):
    	for j in range(len(List)-i-1):
        	if a[j]>a[j+1]:
        		a[j],a[j+1]=a[j+1],a[j]

def maopao_1(List):#升序
    for i in range(len(List)):
        flag = 0
    	for j in range(len(List)-i-1):
        	if a[j]>a[j+1]:
        		a[j],a[j+1]=a[j+1],a[j]
                flag = 1
        if not flag:
            break

归并排序

原理

可将大的数据集切分为N个子集合，将每一个子集合进行排序，这样就获得了N个已排好顺序的数据集，接下来，将排好序的数据集合并，并使合并后的数据集仍然保持有序，即可实现对整个数据集的排序。

时空复杂度

文章作者: hobee

文章链接: https://hobeedzc.github.io/2020/05/09/Python%E7%AE%80%E5%8D%95%E7%AE%97%E6%B3%95/

Python 算法