Python算法结构与常用库 Python algorithm structure and common libraries

python 算法模块与常用库

包括各种常用算法案例，以及常用库的使用说明

1.常用算法实例

1.1质数判断算法

基本思路：首先用if判断最特殊的0和1，它们都不是质数。

其次，再使用循环对每个数的可能因数全部进行判断，从2到x-1，如果循环途中发现有可以整除（即为x的因数），则返回False并跳出循环。

如果循环结束也没有跳出，那么说明没有因数，x是质数，返回True。

def isprime(x):
    if x==0 or x==1:
        return False
    else:
        for i in range(2,x):
            if x%i==0:
                return False
        return True

1.2进制算法

十进制转N进制

总思路为逆向取余法，对十进制数字反复除以进制数n，直至整除为0，将余数逆向排列，即可得到n进制转换结果。需要注意的是超过十进制转换时，需要把超过10的余数转换为字母表达。这一部分使用循环进行余数序列的对应替换。另一种算法是直接用列表解析生成对照序列，再利用序列的索引进行一一对应替换。

a=int(input("请输入要转换的十进制数"))
n=int(input("要转换为几进制数？"))
b=[]
Str=''
while True:
    b.append(a%n)
    a=a//n
    if a<n:
        b.append(a)
        break
for i in range(len(b)):
    for j in range(10,36):
        letter=chr(ord('a')+(j-10))
        if b[-1-i]==j:
            b[-1-i]=letter
    print(b[-1-i],end='')
--------------------------------------------------------------------------
a=int(input("请输入要转换的十进制数"))
n=int(input("要转换为几进制数？"))
b=[]
base=[str(x) for x in range(10)]+[chr(x) for x in range(ord('a'),ord('a')+26)]
while True:
    b.append(base[a%n-1])
    a=a//n 
    if a<n:
        b.append(base[a-1])
        break
for k in range(len(b)):
    print(b[-1-k],end='')

N进制转十进制

主要思路为：位权展开法，每一位乘上对应的权。

n=int(input("您将要输入N进制数N=？"))
a=input("请输入要转换为十进制的N进制数")
base=[str(x) for x in range(10)]+[chr(x) for x in range(ord('a'),ord('a')+26)]
a=list(a)
b=[]
s=0
for i in range(len(a)-1,-1,-1):
    a[i]=int(base.index(a[i]))
    s=s+int(a[i])*(n**(len(a)-1-i))
print(s)

1.3因子算法

最小公倍数算法：

设置循环从较大数开始找，直到找到最小公倍数跳出循环。

def gbs(a,b):
    if a<b:
        a,b=b,a
    for i in range(a+1,a*b+1):
        if i%a==0 and i%b==0:
            print("最小公倍数为",i)
            break

最大公约数算法：

设置循环从较小数开始倒序找，直到找到最大公约数跳出循环

def gys(a,b):
    if a<b:
        a,b=b,a
    for i in range(b,0,-1):
        if a%i==0 and b%i==0:
            return i
            break

辗转相除法：

更简洁高效的最大公约数算法。原理是以较大数除以较小数开始循环，每次将除数移交给被除数，再把余数移交给除数，辗转相除，直到余数为0，则最后一次的除数就是最大公约数。

def gys(a,b):
    if a<b:
        a,b=b,a
    while b: 
        a,b=b,a%b
return a

用最大公约数求最小公倍数：

两个数的最大公约数与最小公倍数的乘积，即为两个数的乘积：

axb=(最大公约数)x(最小公倍数)

1.4 回文算法

pythond的回文算法非常简单，转换为列表利用内置的颠倒函数便可轻松实现。

def hws(x):
    x=list(str(x))
    y=list(reversed(x))
    if x==y:
        return True
    else:
        return False

或者，也可以使用索引进行一一对比，采用递归思路：

从两端向中间递归，如果发现不同就触发return回False；如果一直递归到最中间也没找到不同，就返回Ture。每次递归把输入字符串去除首尾，进行下一轮迭代；返回结果时，反向从内向外报告。

def hws(x):
    if len(x)<2:
        return True
    if x[0]!=x[-1]:
        return False
    return hws(x[1:-1])

1.5 排序算法

Python自带有各种序列的排序方法函数，但是出于对算法的理解角度，也应该掌握各类排序算法。

冒泡排序法

双重循环结构，每次都将序列最左边的数向右进行冒泡（相邻比较，如果左边小于右边，就交换，等效于较大数向右移动）。此过程中较大数会慢慢“浮”到序列右端，很像冒泡。

外层循环：循环n=len(arr)次，确保每个值都会进行排序。

内层循环：跟外层循环进行的次数有关。外层循环每冒泡一次，则最右端就会确定一个较大值的位置，无需继续冒泡。

注意：列表在函数中相当于全局变量，被修改则会牵连原列表，因而无需返回值。

def bubbleSort(arr):
    n=len(arr)
    for i in range(n):
        for j in range(0,n-i-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]

插入排序法

类似于我们平时打牌时对扑克牌进行排序，每次插入一个新值，需要找到其适当的中间位置并插入。

def insertSort(arr):
    length=len(arr)
    for i in range(1,length):
        x=arr[i]
        for j in range(i,-1,-1):
            if x<arr[j-1]:
                arr[j]=arr[j-1]
            else:
                break
        arr[j]=x

这串代码的逻辑是，序列分为两个区域：左边为已排序区，右边为待排序区。第一层循环的参数i控制正在插空的被排序对象是第几个，第二层循环的参数j倒序变化，控制插空位移。首先，i从1开始取，0号元素已经默认为排序区；然后，指针i不断向右移动，先把待排序对象arr[i]单独取出来，和已排序区进行从右向左的插空判断：

如果待排序对象arr[i]过小，arr[j-1]向右移动来为将来的arr[i]插入提供空位。不必担心arr[i]本身会因为移动而被替换，因为已经用x来存储arr[i]。

如果待排序对象arr[i]过大，直接跳出循环，找到插入位置了，就把arr[i]=x放在arr[j]这个位置插入。内层循环结束，进入下一轮arr[i+1]的插入。

1.6 查找算法

二分查找法

对有序数组进行快速查找时，使用二分法可以大大提高效率，每次比较都可以使搜索范围缩小一半。

案例代码使用递归函数，输入：查找序列arr, 序列待查找对象x。l与r是函数内部的形参

def binarySearch(arr,l,r,x):
    if r>=l:
        mid=int(l+(r-l)/2)
        if arr[mid]==x:
            return mid
        elif arr[mid]>x:
            return binarySearch(arr,1,mid-1,x)
        else:
            return binarySearch(arr,mid+1,r,x)
    else:
        return -1

1.7 累加算法

这个就不写了，简单的循环即可。主要任务是找数列递推公式，比如下面这个斐波那契数列:

nterms=int(input("你需要几项斐波那契数列？"))
n1，n2=0，1
count=2
if nterms<=0:
    print("输入不合法，请输入一个正数")
elif nterms==1:
    print("斐波那契数列：")
    print(n1)
else:
    print("斐波那契数列：")
    print(n1,",",n2,end=' ')
    while count<nterms:
        nth=n1+n2
        print(",",nth,end=' ')
        n1，n2=n2，nth
        count+=1

2.常用库函数

库的使用：import 库名称; 使用库函数时为: 库名称.函数名()

2.1 math库

math库的函数主要用于数学计算，包含常用的数学常数以及常用数学函数：指对数、三角函数等

指对数

math.exp(x): 返回自然对数的x次幂

math.pow(x,y): 返回x的y次幂

math.sqrt(x): 返回x的平方根

三角函数

sin(x),cos(x),tan(x)：三角函数

asin(x),acos(x),atan(x)：反三角函数

数值表示函数

math.fabs(x): 返回x的绝对值

math.gcd(a,b): 返回a和b的最大公约数

math.floor(): 向下取整

math.ceil(): 向上取整

2.2 random库

randint(a,b): 返回一个a到b之间的随机整数

uniform(a,b): 返回一个a到b之间的随机小数

random(): 随机生成一个[0,1.0]之间的小数

2.3 os库

os.getcwd()： 获取当前工作目录，默认为程序所在目录

os.chdir(’新目录‘): 更改当前工作目录至新目录

os.listdir(): 列出当前工作目录下的文件或文件夹

os.rmdir(‘某目录’)：删除目录

os.remove(‘某文件’): 删除文件

2.4 datetime库

该库分为三个类：date , time , datetime

使用案例：

import datetime
newdt=datetime.datetime.now()
#代表datetime库中datetime类下的now方法，获取日期和时间
print(datetime.datetime.time(newdt))
#代表datetime库中datetime类下的time方法，拆出字符串中的时间
datetime.timedelta(weeks,days,hours,minutes,seconds)
#用于计算时间差的函数，该函数会自动计算某段时间前的时间。

此外，time库也有一些常用的函数，比如time.sleep()，可以使程序暂停休眠一段时间再继续运行

2.5 NumPy库

用于科学计算的基础包，可以处理矩阵和数组

NumPy 的主要对象：

同构多维数组（元素表）。所有类型都相同，由非负整数元组索引。在NumPy维度中称为轴。

​ 例如，3D空间中的点的坐标[1, 2, 1]具有一个轴。该轴有3个元素，所以我们说它的长度为3。在下面所示的例子中，数组有2个轴。第一轴的长度为2，第二轴的长度为3。

[[ 1, 0, 0],

[ 0, 1, 2]]

拥有数组创建、数组打印、数组操作等功能，可用于线性代数计算、矩阵操作等。

2.6 SciPy library库

基于NumPy的拓展模块，增加了数学和工程上的运算，比如拟合、积分、常微分方程求解、插值等。

简单的定积分：SciPy的子模块integrate中的quad()函数

quad(f,a,b)：对函数f从a积分到b

dblquad(f,a,b,g,h): 计算二重积分，二元函数f，x从a积分到b，y从g(x)积分到h(x)

2.7 Matplotlib 库

主要用于绘图，可以简单高效地将数据图形化，可视化。

最常用plot()命令

#pyplot生成可视化效果：
import matplotlib.pyplot as plt
plt.plot([1, 2, 3, 4])
plt.ylabel('some numbers')
plt.show()

可以设置绘图的各种参数，如线形、颜色、坐标轴等。

除此之外，还可以绘制各种统计图、三维曲线、曲面等。

2.8 Pandas库

主要用于数据挖掘和数据分析，大数据处理统计。

其主要的两大模块为：Series和DataFrame

Series是类似于一维数组的对象，是由一组数据以及一组一直相关的数据标签（索引）组成的。索引是默认从0开始的整数序列，Series是一种有序的变长字典。

DataFrame是一个表格型的数据结构，包含一组有序序列，并且同时拥有行索引和列索引。