计算机科学和Python编程导论week3

递归

In [1]: def factl(n):
   ...:     res = 1
   ...:     while n > 1:
   ...:         res = res * n 
   ...:         n -= 1
   ...:     return res
   ...: 

# 写成递归函数
In [2]: def factR(n):
   ...:     if n == 1:
   ...:         return n
   ...:     return n*factR(n-1)
   ...: 

In [3]: factl(5)
Out[3]: 120

In [4]: factR(5)
Out[4]: 120

In [5]: factl(10)
Out[5]: 3628800

In [6]: factR(10)
Out[6]: 3628800

# 汉诺塔
In [7]: def printMove(fr, to):
   ...:     print('move from ' + str(fr) + ' to ' + str(to))
   ...: 
   ...: def Towers(n, fr, to, spare):
   ...:     if n == 1:
   ...:         printMove(fr, to)
   ...:     else:
   ...:         Towers(n-1, fr, spare, to)
   ...:         Towers(1, fr, to, spare)
   ...:         Towers(n-1, spare, to, fr)

元组、字符串、列表、字典练习

元组

元组用圆括号标记。组中只包含一个元素时，需要在元素后面添加逗号。元组的一个特性是没有重复的元素。其他特性如下：

>>> tup1 = ()
>>> tup1
()
>>> tup1 = (12,)
>>> tup1
(12,)

# 元组和字符串类似，可以通过下标来进行索引和切片
>>> tup1 = ('physics', 'chemistry', 1997, 2000)
>>> tup2 = (1, 2, 3, 4, 5, 6, 7 )
>>> tup1[2]
1997
>>> tup1[1:3]
('chemistry', 1997)

# 元组中的元素不允许修改，但是可以进行连接组合以及删除整个元组
>>> tup3 = (12,34,'abc','xyz')
>>> tup3[0] = 33
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> tup4 = (56,33)
# 可以用+号来进行连接
>>> tup5 = tup3+tup4
>>> tup5
(12, 34, 'abc', 'xyz', 56, 33)
# 元组删除后，再打印会进行报错
>>> del tup5
>>> tup5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'tup5' is not defined


#元组的一些内置函数如下：
len(tuple)
计算元组元素个数。
max(tuple)
返回元组中元素最大值。
min(tuple)
返回元组中元素最小值。 

字符串

在python中字符串是最常见的类型，可以用单引号或双引号来创建。

# 可以对字符串进行索引和切片
#需要在字符中使用特殊字符时，python用反斜杠(\)转义字符。
>>> str1 = 'hellopython'
>>> str1[1]
'e'
>>> str1[2:5]
'llo'
>>> str1[5:] = 'timekiller'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment
>>> str1[:5] + 'timekiller'
'hellotimekiller'

# 字符串还可以进行运算等
>>> a = 'hello'
>>> b = 'timekiller'
>>> a + b 
'hellotimekiller'
>>> a * 2
'hellohello'

列表

列表中的每个元素都分配一个数字 - 它的位置，或索引，第一个索引是0，第二个索引是1，依此类推。

>>> list1 = ['my','python',12, 23]
>>> list1[0]
'my'
>>> list1[2]
12
>>> list1[1:3]
['python', 12]

# 使用append来添加元素，只能单个追加
>>> list = []
>>> list.append('Google')
>>> list.append('Tecent')
>>> list
['Google', 'Tecent']

# 还可以进行删除列表元素
>>> del list[1]
>>> list
['Google']

# 列表的一些其他操作
>>> len([1,2,3])
3
>>> [1,2,3]+[4,5,6]
[1, 2, 3, 4, 5, 6]
>>> ['Hi'] * 4
['Hi', 'Hi', 'Hi', 'Hi']
>>> 3 in [1,2,3]
True
>>> for x in [1,2,3]:
...     print (x)
... 
1
2
3

其他一些列表中的方法如下：

方法	说明
list.append(obj)	在列表末尾添加新的对象
list.count(obj)	统计某个元素在列表中出现的次数
list.extend(seq)	在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）
list.index(obj)	从列表中找出某个值第一个匹配项的索引位置
list.insert(index, obj)	将对象插入列表
list.pop([index=-1])	移除列表中的一个元素（默认最后一个元素），并且返回该元素的值
list.remove(obj)	移除列表中某个值的第一个匹配项
list.reverse()	反向列表中元素
list.sort(cmp=None, key=None, reverse=False)	对原列表进行排序

字典

字典是另一种可变容器模型，且可存储任意类型对象。
字典的每个键值 key=>value 对用冒号 : 分割，每个键值对之间用逗号 , 分割，整个字典包括在花括号 {} 中。

>>> dict = {'alice':1992,'bob':1989,'beth':1995}
>>> dict
{'alice': 1992, 'bob': 1989, 'beth': 1995}
>>> type(dict)
<class 'dict'>

# 通过键来访问字典中的元素
>>> dict['alice']
1992
# 通过增加键值对增加字典中的元素
>>> dict['dylan']=1997
>>> dict
{'alice': 1992, 'bob': 1989, 'beth': 1995, 'dylan': 1997}
# 通过键删除字典中的元素
>>> del dict['bob']
>>> dict
{'alice': 1992, 'beth': 1995, 'dylan': 1997}
# 创建时如果同一个键被赋值两次，后一个值会被记住
>>> dict1 = {'name':'zara','age':7,'name':'manni'}
>>> dict1
{'name': 'manni', 'age': 7}

其他需要记住的是：键不允许出现两次，键值必须不可变。

生成器和迭代器

1、生成器。

在Python中，这种一边循环一边计算的机制，称为生成器：generator。要创建一个generator，可以通过把一个列表生成式的[]改成()，就创建了一个generator：

In [1]: L = [x * x for x in range(10)]
In [2]: L
Out[2]: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

In [5]: g = (x * x for x in range(10))
In [6]: g
Out[6]: <generator object <genexpr> at 0x000000001137A7D8>

In [7]: next(g)
Out[7]: 0
In [8]: next(g)
Out[8]: 1

# 可以通过for循环来进行调用
In [9]: for n in g:
   ...:     print(n)
   ...:     
4
9
16
25
36
49
64
81

要理解generator的工作原理，它是在for循环的过程中不断计算出下一个元素，并在适当的条件结束for循环。对于函数改成的generator来说，遇到return语句或者执行到函数体最后一行语句，就是结束generator的指令，for循环随之结束。

# 请注意区分普通函数和generator函数，普通函数调用直接返回结果：
In [10]: f = abs(-6)

In [11]: f
Out[11]: 6

# generator函数的“调用”实际返回一个generator对象：
In [13]: def fib(max):
    ...:     n, a, b = 0, 0, 1
    ...:     while n < max:
    ...:         yield b
    ...:         a, b = b, a + b
    ...:         n = n + 1
    ...:     return 'done'
    ...: 
In [14]: g =fib(6)
In [15]: g
Out[15]: <generator object fib at 0x0000000011139D58>

2、迭代器

直接作用于for循环的对象统称为可迭代对象：Iterable，一类是集合数据类型，如list、tuple、dict、set、str等；一类是generator，包括生成器和带yield的generator function。

可以被next()函数调用并不断返回下一个值的对象称为迭代器：Iterator，它们表示一个惰性计算的序列。

# 集合数据类型如list、dict、str等是Iterable但不是Iterator，不过可以通过iter()函数获得一个Iterator对象。
In [16]: it = iter([1,2,3,4,5])

In [17]: it
Out[17]: <list_iterator at 0x113a7710>

In [18]: next(it)
Out[18]: 1

3、列表生成式

In [19]: [x * x for x in range(1,11)]
Out[19]: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

In [21]: [x * x for x in range(1,11) if x % 2 == 0]
Out[21]: [4, 16, 36, 64, 100]

In [22]: L = ['Hello','World','IBM','Apple']

In [23]: [s.lower() for s in L]
Out[23]: ['hello', 'world', 'ibm', 'apple']

map、reduce、filter、sorted 以及匿名函数

map的功能：map(f, [x1,x2,x3]) = [f(x1), f(x2), f(x3)]，3.x的版本返回的是个迭代器

In [24]: def f(x):
    ...:     return x*x
    ...: 
In [25]: a = map(f,[1,2,3,4,5])

In [26]: a
Out[26]: <map at 0x113a6978>

In [28]: for x in a:
    ...:     print (x)
    ...:     
1
4
9
16
25

reduce()的用法：reduce(f, [x1, x2, x3]) = f(f(f(x1,x2),x3),x4).

#在 Python3 中，reduce() 函数已经被从全局名字空间里移除了，它现在被放置在 fucntools 模块里，
#如果想要使用它，则需要通过引入 functools 模块来调用 reduce() 函数：
In [29]: def add(x,y):
    ...:     return x+y
    ...: print(reduce(add,[1,2,3,4,5]))
    ...: 
Traceback (most recent call last):

  File "<ipython-input-29-9ad4364ab3ea>", line 3, in <module>
    print(reduce(add,[1,2,3,4,5]))

NameError: name 'reduce' is not defined


In [30]: from functools import reduce

In [31]: def add(x,y):
    ...:     return x+y
    ...: print(reduce(add,[1,2,3,4,5]))
    ...: 
15

filter的用法

filter(f, [x1,x2,x3]) = [x1], f(x1)=True, f(x2)=False, f(x3)=False
注意: filter参数中f函数返回的是布尔类型的值， filter根据f(x1)返回的值是否是True而决定是否返回x1.

In [32]: def is_odd(n):
    ...:     return n % 2 == 1
    ...: 

In [33]: newlist = filter(is_odd, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

In [34]: newlist
Out[34]: <filter at 0x1139f780>

In [35]: i = []

In [36]: for x in newlist:
    ...:     i.append(x)
    ...: print (i)
    ...: 
[1, 3, 5, 7, 9]
'''
关于filter()方法, python3和python2有一点不同
python2中返回的是过滤后的列表, 而python3中返回到是一个filter类
filter类实现了__iter__和__next__方法, 可以看成是一个迭代器, 有惰性运算的特性, 相对python2提升了性能, 可以节约内存.
'''

sorted() 函数对所有可迭代的对象进行排序操作。

# 如果是数字，默认按从小到到的顺序排列.
In [40]: sorted([36,5,11,9,22])
Out[40]: [5, 9, 11, 22, 36]

# 如果是字符串，默认先比较大写字符串的大小，然后再比较小写字符创的大小。都是从小到大顺序排列。
In [41]: sorted(['I','Hello','Gim', 'you', 'him', 'apple', 'banana'])
Out[41]: ['Gim', 'Hello', 'I', 'apple', 'banana', 'him', 'you']

匿名函数

关键字lambda表示匿名函数，冒号前面的x表示函数参数。
匿名函数有个限制，就是只能有一个表达式，不用写return，返回值就是该表达式的结果。

In [42]: list(map(lambda x: x*x,[1,2,3,4,5,6,7,8]))
Out[42]: [1, 4, 9, 16, 25, 36, 49, 64]

In [43]: result = filter(lambda x: x>3, [1,2,3,4,5])
# 返回的是个可迭代对象
In [44]: result
Out[44]: <filter at 0x1139f588>

In [45]: list1 = []
    ...: for i in result:
    ...:     list1.append(i)
    ...:     

In [46]: list1
Out[46]: [4, 5]

'''
匿名函数的几个规则：
1. 不用函数名
2. 可以没有参数，可以有多个参数，参数可以带默认值。
3. 函数中只能写一个表达式。
4. 不用写return, 返回值就是表达式的结果

应用：
匿名函数一般应用于函数式编程。常和map, reduce 和 filter函数结合使用。
'''

对于视频中的做错题目的总结

PS：很多错误是由于py的版本差异造成的。

# L6 PROBLEM 9

In [153]:animals = {'a': 'aardvark', 'b': 'baboon', 'c': 'coati'}
In [154]:animals['d'] = 'donkey'

# 下面这条命令，答案显示的是False，其实是版本造成的
In [155]: animals.has_key('b')
Traceback (most recent call last):

  File "<ipython-input-155-700826fe47e9>", line 1, in <module>
    animals.has_key('b')

AttributeError: 'dict' object has no attribute 'has_key'

# L6 PROBLEM 10

In [157]:animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}
In [167]: def howMany(aDict):
     ...:     '''
     ...:     aDict: A dictionary, where all the values are lists.
     ...: 
     ...:     returns: int, how many values are in the dictionary.
     ...:     '''
     ...:     # Your Code Here
     ...:     return len(animals.keys()) + len(animals.values())


# L6 PROBLEM 11

In [180]: animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}
     ...: 
     ...: animals['d'] = ['donkey']
     ...: animals['d'].append('dog')
     ...: animals['d'].append('dingo')
     ...: 

Example usage:

In [181]: biggest(animals)
Out[181]: 'd'

答案：
In [182]: def biggest(aDict):
     ...:     '''
     ...:     aDict: A dictionary, where all the values are lists.
     ...: 
     ...:     returns: The key with the largest number of values associated with it
     ...:     '''
     ...:     result = None
     ...:     biggestValue = 0
     ...:     for key in aDict.keys():
     ...:         if len(aDict[key]) >= biggestValue:
     ...:             result = key
     ...:             biggestValue = len(aDict[key])
     ...:     return result
     ...: 

参考链接：
Python 内置函数
Python map/reduce/filter/sorted函数以及匿名函数
6.00.1X 计算机科学和PYTHON编程导论（自主模式）