Python_算法汇总

1. 约瑟夫环：

# 约瑟夫环：共31个数，每隔9个删除一个，要求输出前15个号码

a=[x for x in range(1,31)]  #生成编号
del_number = 8 #该删除的编号
for i in range(15):
    print(a[del_number])
    del (a[del_number])
    del_number = (del_number + 8)%(len(a))

2.斐波拉切数列：

class Fibs:
    def __init__(self, n=10):
        self.a = 0
        self.b = 1
        self.n = n
    def __iter__(self):
        return self
    def __next__(self):
        self.a, self.b = self.b, self.a + self.b
        if self.a > self.n:
            raise StopIteration
        return self.a

fibs = Fibs(100)
for each in fibs:
    print(each)

#------------------------------------------------------------

def fibo(num):
    numList = [0,1]
    for i in range(num - 2):
        numList.append(numList[-2] + numList[-1])
    return numList

fibs=fibo(10)
for each in fibs:
    print(each)
    
#----------------------------------------------------------------

def fibo(n):
    x, y = 0, 1

    while(n):
        x,y,n = y, x+y, n - 1
    return x

# print(fibo(1))

for i in range(1,10):
    print(fibo(i))
    
#-----------------------------------------------------------------

3.快排 / 快速排序：

def quickSort(num,l,r):  
    if l>=r:#如果只有一个数字时，结束递归  
        return  
    flag=l  
    for i in range(l+1,r+1):#默认以第一个数字作为基准数，从第二个数开始比较，生成索引时要注意右部的值  
        if num[flag]>num[i]:  
            tmp=num[i]  
            del num[i]  
            num.insert(flag,tmp)  
            flag+=1  
    quickSort(num,l,flag-1)#将基准数前后部分分别递归排序  
    quickSort(num,flag+1,r)  
  
num=[1,-2,4,7,6,3,2,3]  
quickSort(num,0,7)  
print(num)  

4.冒泡排序

#encoding:utf-8
l=[5,3,6,2,1,4,8,7,9]
for j in range(len(l)-1):
    if l[j] > l[j+1]:
        l[j],l[j+1] = l[j+1],l[j]
print(l)

5.二分法查找

def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low < height:
        mid = (low+height)/2
        if array[mid] < t:
            low = mid + 1

        elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]

    return -1


if __name__ == "__main__":
    print BinarySearch([1,2,3,34,56,57,78,87],57)