迭代器
迭代器是一个可以记住遍历的位置的对象。迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束，引发一个StopIteration。迭代器只能往前不会后退。迭代器有两个基本的方法：iter() 和 next()。
字符串，列表或元组对象都可用于创建迭代器：
>>> list=[1,2,3,4]
>>> it = iter(list) # 创建迭代器对象
>>> print (next(it)) # 输出迭代器的下一个元素
1
>>> print (next(it))
2
迭代器对象可以使用常规for语句进行遍历：
list=[1,2,3,4]
it = iter(list) # 创建迭代器对象
for x in it:
print (x, end=" ")
输出：1 2 3 4
也可以使用循环：
while True:
print (next(it))
也可以使用 list 方法，将迭代器转成列表全部输出。
创建迭代器：
把一个类作为一个迭代器使用需要在类中实现两个方法__iter__()与 __next__()。
__iter__()方法返回一个特殊的迭代器对象， 这个迭代器对象实现了 __next__()方法并通过 StopIteration 异常标识迭代的完成。
__next__()方法会返回下一个迭代器对象。
创建一个返回数字的迭代器，初始值为 1，逐步递增 1：
class MyNumbers:
def __iter__(self):
self.a = 1
return self
def __next__(self):
x = self.a
self.a += 1
return x
myclass = MyNumbers()
myiter = iter(myclass)
print(next(myiter))
输出：1
定义一个斐波那契数列：（1、1、2、3、5、8、13、21、34、······）
class Fibs():
def __init__(self):
self.a = 0
self.b = 1
def __iter__(self):
return self
def __next__(self):
self.a, self.b = self.b, self.a+self.b
return self.a
myclass = Fibs()
my = iter(myclass)
print(next(my))
print(next(my))
print(next(my))
for f in myclass:
if f>1000: break
print(f)
输出：1 1 2 3 5 8 13 ··· 987
生成器
在 Python 中，使用了 yield 的函数被称为生成器（generator）。
跟普通函数不同的是，生成器是一个返回迭代器的函数，只能用于迭代操作，更简单点理解生成器就是一个迭代器。
在调用生成器运行的过程中，每次遇到 yield 时函数会暂停并保存当前所有的运行信息，返回 yield 的值, 并在下一次执行 next() 方法时从当前位置继续运行。
调用一个生成器函数，返回的是一个迭代器对象。
以下实例使用 yield 实现斐波那契数列：
def fibonacci(n): # 生成器函数 - 斐波那契
a, b, counter = 0, 1, 0
while True:
if (counter > n):
return
yield a
a, b = b, a + b
counter += 1
f = fibonacci(10) # f 是一个迭代器，由生成器返回生成
生成器底层实现？
斐波那契数列
除了上文利用生成器构成斐波那契数列的方法，还可以利用循环或者递归。
循环：时间复杂度O(n)
def Fibonacci(n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a
递归：时间复杂度很大，有很多重复计算，最好不用
def Fibonacci(n):
if n == 0:
return 0
if n == 1 or n == 2:
return 1
return Fibonacci(n-1) + Fibonacci(n-2)
变形1：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解析：
初值 n=1，一种；n=2，两种（11，2）；可得 n>2：f(n)=f(n-1)+f(n-2)还是斐波那契数列，只是去掉最前面的1，将上面代码稍微修改即可。
def jumpFloor(n):
a, b = 1, 1
for i in range(n):
a, b = b, a+b
return a
变形2：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解析：这是一种排列问题，比如3级有 111，12，21，3四种，四级可以写出有8种，其实就是 2n-1种。类似的还有数字 n 有多少种组合方式，先后次序不同是不同的方式，常见于分物品物体。
def jumpFloorII(self, number):
if number == 0:
return 0
return 2 ** (number - 1)
变形3：
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
解析：大矩形高度固定为2，所以n=1时，只有一种放法，竖着放；n=2时，有两种，横着放或者竖着放，横着放的时候，一旦第一个矩形固定了，第二个也就跟着固定了，所以有两种；所以当 n>2 时，第一块竖着放时，剩下的相当于f(n-1)，第一块横着放时，由于第一块下面的只能横着放，所以剩下的相当于f(n-2)，所以f(n)=f(n-1)+f(n-2)还是斐波那契数列。
def rectCover(n):
if n < 1:
return 0
a, b = 1, 1
for i in range(n):
a, b = b, a+b
return a
