# -*- coding: utf-8 -*-
# @Date : 2017-08-19 20:19:56
# @Author : lileilei
'''那么算法和数据结构是什么呢，答曰兵法'''
'''a+b+c=1000 and a*a+b*b=c*c 求a,b,c'''
# import time
# start_time=time.time()
# for a in range(1000):#使用枚举法
# for b in range(1000):
# for c in range(1000):
# if a+b+c==1000 and a*a+b*b==c*c:
# print(a,b,c)
# print(time.time()-start_time)
# import time #方法2
# start_time=time.time()
# for a in range(1000):
# for b in range(1000):
# c=1000-a-b
# if a+b+c==1000 and a*a+b*b==c*c:
# print(a,b,c)
# print(time.time()-start_time)
class Stack(object):
"""栈"""
def __init__(self):
self.__items = []
def is_empty(self):
"""判断是否为空"""
return self.__items == []
def push(self, item):
"""加入元素"""
self.__items.append(item)
def pop(self):
"""弹出元素"""
return self.__items.pop()
def peek(self):
"""返回栈顶元素"""
return self.__items[len(self.__items)-1]
def size(self):
"""返回栈的大小"""
return len(self.__items)
# if __name__ == "__main__":
# stack = Stack()
# stack.push("hello")
# stack.push("world")
# stack.push("itcast")
# print (stack.size())
# print (stack.peek())
# print (stack.pop())
# print (stack.pop())
# print (stack.pop())
class Queue(object):
'''队列'''
def __init__(self):
self.__list=[]
def addqueue(slef,item):
#self.__list.append(item)
self.__list.insert(0,item)
def dequeue(self):
return self.__list.pop()
def is_empty(self):
return self.__list==[]
def size(self):
return len(self.__list)
class Dqueue(object):
'''双端队'''
def __init__(self):
self.__list=[]
def add_front(slef,item):
self.__list.insert(0,item)
def add_re(self,item):
self.__list.insert(item)
def dequeue(self):
return self.__list.pop()
def requeue(self):
return self.__list.pop(0)
def is_empty(self):
return self.__list==[]
def size(self):
return len(self.__list)
def buule_sor(alist):#冒泡
n=len(alist)
for i in range(n-1):
for j in range(n-1-i):
count=0
if alist[j]>alist[j+1]:
alist[j],alist[j+1]=alist[j+1],alist[j]
count+=1
if 0==count:
return
def select_sort(alist):#选择排序
n=len(alist)
for j in range(n-1):
min=j
for i in range(j+1,n):
if alist[min] > alist[i]:
min=i
alist[j],alist[min]=alist[min],alist[j]
def insert_sort(alist):'''插入排序'''
n=len(alist)
for j in range(1,n):
i=j
while i>0:
if alist[i]<alist[i-1]:
alist[i],alist[i-1]=alist[i-1],alist[i]
i-=1
def shell_sort(alist):'''希尔排序'''
n=len(alist)
gap=n//2
while gap>0:
for j in range(gap,n):
i=j
while i>0:
if alist[i]<alist[i-gap]:
alist[i],alist[i-gap]=alist[i-gap],alist[i]
i-=gap
else:
break
gap//=2
def quick_sort(alist,first,last):'''快速排序'''
if first>=last:
return
mid_value=alist[first]
low=first
high=last
while low<high:
while low <high and alist[high]>=mid_value:
high-=1
alist[low]=alist[high]
while low <high and alist[low]<mid_value:
low+=1
alist[high]=alist[low]
alist[low]=mid_value
quick_sort(alist,first,low-1)
quick_sort(alist,low+1,last)
def me_sort(alist):'''归并排序'''
n=len(alist)
if n<=1:
return alist
mid=n//2
left=me_sort(alist[:mid])
right=me_sort(alist[mid:])
left_point,right_porint=0,0
result=[]
while left_point<len(left) and right_porint<len(right):
if left[left_point] <right[right_porint]:
result.append(left[left_point])
left_point+=1
else:
result.append(right[right_porint])
right_porint+=1
result+=left[left_point:]
result+=right[right_porint:]
return result
def binary_search(alist,item):#二分查找 递归
n=len(alist)
if n>0:
mid=n//2
if alist[mid]==item:
return True
elif item<alist[mid]:
return binary_search(alist[:mid],item)
else:
return binary_search(alist[mid+1:],item)
return False
def brin_serce2(alist,item):#二分非递归
n=len(alist)
first=0
lasr=n-1
while first <=lasr:
mid = (first + lasr) // 2
if alist[mid]==item:
return True
elif item<alist[mid]:
lasr=mid-1
else:
first=mid+1
return False
if __name__ == '__main__':
listy=[54,67,76,23,34]
print(brin_serce2(listy,55))