Lane
cs61a

cs61a

introduction

cs61a-one of the best choices for cs biginners

:tent:invigationhttps://inst.eecs.berkeley.edu/~cs61a/su22/

week1

lectrue 1-functions

lesson 1-Names, Assignment, and User-Defined Functions

1
2
3
4
5
6
7
>>> pi
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'pi' is not defined
>>> from math import pi
>>> pi
3.141592653589793

这同样适用于函数

1
2
3
4
5
>>> from math import sin
>>> sin
<built-in function sin>
>>> sin(pi/2)
1.0

自定义

1
2
3
>>> httt=99
>>> httt
99

将两者相结合进行多元定义与计算

1
2
3
4
5
>> area,cnt=299*pi,sin(pi/4)
>>> area
939.3362034233481
>>> cnt
0.7071067811865476

函数的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
>>> max(1,2,3)
3
>>> f=max
>>> f
<built-in function max>
>>> max
<built-in function max>
>>> f(2,3,6)
6
>>> from operator import add,mul
>>> add
<built-in function add>
>>> mul
<built-in function mul>
>>> def square(x):
... return mul(x,x)
...
>>> def ttt(x):
... return add(x,x)
...
>>> square(11)
121
>>> ttt(11)
22
>>>

函数与定义名的区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> tt = 12
>>> ttt =2*tt
>>> ttt
24
>>> tt=11
>>> ttt
24 \\自定义名
>>> def ttt():
... return 2*tt
...
>>> ttt
<function ttt at 0x0000023B0E7A3910>
>>> ttt
<function ttt at 0x0000023B0E7A3910>
>>> ttt()
22
>>> tt=12
>>> ttt()
24
>>> \\定义函数

discussion question1

what is the value of the final expression

1
2
3
4
5
>>> f=min
>>> f=max
>>> g,h=min,max
>>> max=g
>>> max(f(2,g(h(1,5),3)),4)
answer 3

lession 2-Environment Diagrams

learn to use python online tutor

这个网站好用咧https://pythontutor.com/python-compiler.html#mode=edit

同样地该网站也方便c的调试

:tent:插入一条广告 功能强大的python shell——ipython

1
2

pip install ipython

使用时(这对windows用户)windows+r 输入ipython即可

lession 3-Defining Functions

lectrue 2-Control and Iteration

lession 1-Print and None

打印

1
2
3
4
5
6
>>> print(print(1),print(2))
1
2
None None
>>> print(None,None)
None None

expression:
None represents nothing in python.a function that does not explicitly return a value will return None in python

careful:None is not displayed by the interpreter as the value of an expression

lession 2-Miscellaneous Python Features

division

1
2
3
4
5
6
7
8
9
10
>>> 213/10
21.3
>>> 213//10
21
>>> from operator import truediv,floordiv
>>> truediv(213,10)
21.3
>>> floordiv(213,10)
21
>>>

function can return multiple values

1
2
3
4
5
6
7
8
9
10
11
12
>>> def haveatry(n,d):
... return n/d,n//d,n%d
...
>>> haveatry(7,3)
(2.3333333333333335, 2, 1)
>>> t,tt,ttt=haveatry(7,3)
>>> t
2.3333333333333335
>>> tt
2
>>> ttt
1

some python featrues

  • kill process

    1
    2
    import sys
    sys.exit()
  • in control of terminal

    1
    2
    3
    4
    5
    python  ex.py  """execute the code"""
    python -i ex.py """execute the code and enter the python process More important you can use functions in python process which are defined in this code"""
    python -m doctest ex.py
    python -m doctext -v ex.py
    """very important in code by python.it is a way to debug in case of the next situation"""

for example

1
2
3
4
5
6
7
8
9
10
def haveatry(n,d):
"""
>>> a
289.1285714285717
>>> b
289
>>> c
1
"""
return n/d,n//d,n%d

lession 3-Conditional statements

  • if statement
1
2
3
4
5
6
7
>>> def fabex(x):
... if(x<0):
... return -x
... elif(x==0):
... return 0
... else:
... return x
  • boolean context

‘True’ ‘False’ belong to boolean context,which are like ‘1’ ‘0’ in language C

  • boolean operator
    ‘and’ ‘or’ ‘not’ ,which are like ‘&&’ ‘||’ ‘!’ in language C

lession 4-Iteration

to beign with let us show a basic statement

for example

1
2
3
4
5
6
7
8
9
>>> i,total=0,0
>>> while(i<3):
... i+=1
... total+=i
...
>>> i
3
>>> total
6

then we will give an iteration example

:smile: dang dang dang

the fibonacci sequence

1
2
3
4
5
6
7
def feb(n):
...: pred,curr=0,1
...: k=1
...: while(k<=n):
...: pred,curr=curr,pred+curr
...: k+=1
...: return curr

note: :smile: previous code is written by ipython which is much better than python.Strong recommend

lession 5-return and lambda expression

  • a return statement completes the evaluation of a call expression and provides its value
  • only one return statement is ever executed while executing the body of the function

next i will introduce a function—lambda

  • lambda 在Python编程中使用的频率非常高,我们通常提及的lambda表达式其实是python中的一类特殊的定义函数的形式,使用它可以定义一个匿名函数。即当你需要一个函数,但又不想费神去命名一个函数,这时候,就可以使用 lambda了。

  • the role of function lambda

    1
    lambda [arg1 [,arg2,.....argn]]:expression

here is some typical examples:

  • Anonymous functions without parameters:

    1
    2
    3
    4
    5
    6
    7
    8
    >>> t = lambda : True 
    >>> t()
    True
    """which is equal to the next code """
    >>> def func():
    return True
    >>> func()
    True
  • Anonymous functions with parameters:

    1
    2
    3
    4
    5
    >>> lambda x: x**3  # 带有一个参数

    >>> lambda x, y, z: x+y+z # 带有多个参数

    >>> lambda x, y=3: x*y # 存在默认值的参数
    • Enter any number of parameters:
    1
    >>> lambda *z: z  # *z传入的是任意个数的参数

    here are some useful examples by using lambda functions:

    for example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    >>> f = lambda x, y, z: x*y*z
    >>> f(2,3,4)
    24

    >>> (lambda x, y: x if x>y else y)(1, 2)
    2
    # 判断字符串是否以某个字母开头
    >>> print((lambda x:x.startswith('B'))('Bob'))
    True
    # 将lambda嵌套到普通函数中,lambda函数本身做为return的值
    >>> def add(n):
    ... return lambda x: x+n
    ...
    >>> f = add(1)
    >>> f(2)
    3

lab1

  • example 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def how_big(x):
    ...: ... if x > 10:
    ...: ... print('huge')
    ...: ... elif x > 5:
    ...: ... return 'big'
    ...: ... elif x > 0:
    ...: ... print('small')
    ...: ... else:
    ...: ... print("nothin'")
    ...:

question: how_big(12)

answer huge analyse: in python print can be used as a return statement in language C
  • example 2
1
2
3
4
   >>> positive = 28
>>> while positive: # If this loops forever, just type Infinite Loop
... print("positive?")
... positive -= 3
answer infinite loop
analyse: this is a typical example to distinguish python and C.That's because in C '1' and '0' are used as 'True' and 'False' in python

but what should be noted that if ‘0’ in python is treated as False only ‘0’

lectrue3-higher-older functions

lession1-description

  • generalizing patterns with arguments

to bigin with,let us introduce assert statement

for example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    In [1]: def square(r):
...: return r*r
In [2]: square(11)
Out[2]: 121
In [3]: square(-11)
Out[3]: 121
# let us introduce assert statement
In [4]: def square(r):
...: assert(r>0),'r should be positive'
...: return r*r
Cell In[4], line 2, in square(r)
1 def square(r):
----> 2 assert(r>0),'r should be positive'
3 return r*r

AssertionError: r should be positive
  • the common structrue among functions may be a computational process,rather than a number

  • we can use a high-older function to describe some funtcions which have similarities(just like swich-case statement in language C)

    for example

    1
    2
    3
    4
    5
    6
    7
    In [6]: def cobe(k):
    ...: return pow(k,3)
    def summin(k,term):
    ...: total,n=0,1
    ...: while(n<=k):
    ...: total,n=total+term(n),n+1
    ...: return total
  • return a function

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
        In [12]: def makeaddr(n):
    ...: def adder(k):
    ...: return k+n
    ...: return adder
    ...:

    In [13]: tt=makeaddr(3)

    In [14]: tt(2)
    Out[14]: 5

lession2-Function Example: Sound

the code is saved in cs61a courses

lession3-array

在python中我们用列表实现其他语言的数组结构

  • append
1
2
3
4
5
6
7
8
9
10
11
12
13
 fruits = ["apple", "banana", "cherry"]
fruits.append("orange") # Adds "orange" to the end of the list
print(fruits) # Outputs: ['apple', 'banana', 'cherry', 'orange']
```
* extend

``` python

fruits = ["apple", "banana", "cherry"]
more_fruits = ["orange", "mango", "grapes"]
fruits.extend(more_fruits)
print(fruits) # Outputs: ['apple', 'banana', 'cherry', 'orange', 'mango', 'grapes']
### homework
  • sum

sum can calculate all members in list

  • len
    len can calculate the lenth in list

  • to sum two arrays

    1
    2
    3
    4
    5
    6
     In [2]: haveatry=[1,2,3,4]

    In [3]: haveatry1=[5,6]

    In [4]: haveatry1*2+haveatry
    Out[4]: [5, 6, 5, 6, 1, 2, 3, 4]
  • getitem

    1
     

homework

Q3: Make Repeater

Implement the function make_repeater so that make_repeater(func, n)(x) returns func(func(…func(x)…)), where func is applied n times. That is, make_repeater(func, n) returns another function that can then be applied to another argument. For example, make_repeater(square, 3)(42) evaluates to square(square(square(42))).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def compose1(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
def make_repeater(func, n):
"""Return the function that computes the nth application of func.

>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
"*** YOUR CODE HERE ***"
f = func
if n == 0:
return identity
for i in range(n-1):
f = compose1(func, f)
return f

analyse:
在 Python 中,当我们谈论 “return identity” 的时候,我们通常是在谈论这样一个函数:它的输出(返回值)与输入完全相同。也就是说,对于任何输入值 x,这个函数都返回 x 自身。这样的函数在函数式编程中也被称为 “恒等函数” 或 “identity function

week2

lectrue1-environment diagrammes

lession1-multiple environment

example

1
2
3
4
5
6
In [1]: def square(square):
...: return square*square
...:

In [2]: square(11)
Out[2]: 121

lession2-Environments for Higher-Order Functions

1
2
3
4
5
6
7
8
9
10
In [1]: def haveatry(f,x):
...: return f(f(x))
...:

In [2]: def square(x):
...: return x*x
...:

In [3]: haveatry(square,3)
Out[3]: 81

lession3-environment for nested definitions

1
2
3
4
5
6
7
8
9
10
In [4]: def make_adder(k):
...: def adder(x):
...: return x+k
...: return adder
...:

In [5]: tt=make_adder(3)

In [6]: tt(2)
Out[6]: 5
  • local name causes error
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [7]: def g(a):
...: return y+a
...:

In [8]: def f(x,y):
...: return g(x)
...:

In [9]: f(1,2)
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[9], line 1
----> 1 f(1,2)

Cell In[8], line 2, in f(x, y)
1 def f(x,y):
----> 2 return g(x)

Cell In[7], line 2, in g(a)
1 def g(a):
----> 2 return y+a

NameError: name 'y' is not defined

lession4-self refrence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
In [19]: def printall(x):
...: print(x)
...: return printall
...:

In [20]: printall(2)
2
Out[20]: <function __main__.printall(x)>

In [21]: printall(2)(3)
2
3
Out[21]: <function __main__.printall(x)>
In [22]: printall(2)(3)(4)
2
3
4
Out[22]: <function __main__.printall(x)>
1
2
3
4
5
6
7
8
9
In [23]: def sum_print(x):
...: print(x)
...: def next_sum(y):
...: return sum_print(x+y)
...: return next_sum
...: sum_print(1)(2)(3)
1
3
6

lession5-decorator

usually used to trace process

1
2
3
4
5
6
7
8
9
10
11
12
>>> def trace1(fn):
... def traced(x):
... print('nihao',fn,x)
... return fn(x)
... return traced
>>> @trace1
... def square(x):
... return x*x
...
>>> square(11)
nihao <function square at 0x00000218E20539A0> 11
121

lectrue2-Recursion

lession1-recursive functions

for example to calculate sum without a while statement

1
2
3
4
5
6
7
8
9
In [32]: def sum_digits(x):
...: if(x<10):
...: return x
...: else:
...: return sum_digits(x//10)+x%10
...:

In [33]: sum_digits(2023)
Out[33]: 7

lession2-mutual recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  In [34]: def luhn_sum(x):
...: if(x<10):
...: return x
...: else:
...: return doubleluhn(x//10)+x%10
...:

In [35]: def doubleluhn(x):
...: if(x<10):
...: return x
...: else:
...: return luhn_sum(x//10)+sum_digits(2*(x%10))
...:

In [36]: luhn_sum(4)
Out[36]: 4

In [37]: luhn_sum(94)
Out[37]: 13

lession3-recursion and iteration

we can convert iteration statement to recursion statement

next we will introduce a example of recrusive calls

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 In [1]: def haveatry(x):
...: if(x<10):
...: print(x)
...: else:
...: print(x)
...: haveatry(x//10)
...: print(x)
#which is equal to the next code
In [4]: def haveatry(x):
...: print(x)
...: if(x>=10):
...: haveatry(x//10)
...: print(x)In [6]: haveatry(12345)
12345
1234
123
12
1
12
123
1234
12345

lectrue3-tree recrusion

fb array is a typical example

1
2
3
4
5
6
7
In [10]: def feb(n):
...: if(n==0):
...: return 0
...: elif(n==1):
...: return 1
...: else:
...: return feb(n-1)+feb(n-2)
  • Counting Partitions

    a typical example:count_partition(6,4):2+4=6;1+1+4=6;
    3+3=6;1+2+3=6;1+1+1+3=6;2+2+2=6;1+1+2+2=6;1+1+1+1+2=6;
    1+1+1+1+1+1=6

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
          def count_part(n,m):
    if(n==0)
    ..: return 1
    ...: elif(n<0):
    ...: return 0
    ...: elif(m==0):
    ...: return 0
    ...: else:
    ...: with_m=count_part(n-m,m)
    ...: without_m=count_part(n,m-1)
    ...: return with_m+without_m
    ...:

    In [16]: count_part(6,4)
    Out[16]: 9

lectrue4-containers and sequences

  • containers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In [7]: kkk=[1,2,3,4]

In [8]: 1 in kkk
Out[8]: True

In [9]: '1' in kkk
Out[9]: False

In [10]: 1=='1'
Out[10]: False

In [11]: [1,2] in kkk
Out[11]: False

In [12]: [1,2] in [1,[1,2]]
Out[12]: True
  • for statement

for ‘name’ in ‘expression’:

‘suite’

for example

1
2
3
4
5
6
7
8
9
10
In [15]: def count_same(s,value):
...: result=0
...: for k in tryfor:
...: if k==value:
...: result=result+1
...: return result
...:

In [16]: count_same(tryfor,4)
Out[16]: 3
  • ranges

a range is a sequence of consequtive integers

here are range statement characteristics

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [17]: list(range(-2,6))
Out[17]: [-2, -1, 0, 1, 2, 3, 4, 5]

In [18]: range(5)
Out[18]: range(0, 5)

In [21]: for k in range(5):
...: print('lakerswillwin')
...:
lakerswillwin
lakerswillwin
lakerswillwin
lakerswillwin
lakerswillwin

  • list comprehensions

powerful way to use array in language python

1
2
3
4
5
6
In [22]: odds=[1,3,5,7,9]

In [23]: [x+1 for x in odds]
Out[23]: [2, 4, 6, 8, 10]
In [26]: [x for x in odds if 25%x==0]
Out[26]: [1, 5]
  • strings
1
2
3
4
5
6
7
8
9
10
11
12
13
In [28]: 'hello'
Out[28]: 'hello'

In [29]: sth='lakerswillwin'

In [30]: len(sth)
Out[30]: 13

In [31]: sth[0]
Out[31]: 'l'

In [35]: 'laker' in sth
Out[35]: True #here is a diffrence between number array and string array

week3

lectrue1-mutability

  • objects

in python every value is a object

date

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In [36]: from datetime import date

In [37]: date
Out[37]: datetime.date

In [38]: today=date(2024,2,1)

In [39]: today.year
Out[39]: 2024

In [40]: today.month
Out[40]: 2

In [41]: today.day
Out[41]: 1
In [43]: today.strftime('%A %B %d')
Out[43]: 'Thursday February 01'
In [47]: freedom=date(2027,3,12)

In [48]: str(freedom-today)
Out[48]: '1135 days, 0:00:00'

strings are objects so they have attributes

here are another characteristics

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In [49]: haveatry='lakerswiillwin'

In [50]: haveatry.upper
Out[50]: <function str.upper()>

In [51]: haveatry.upper()
Out[51]: 'LAKERSWIILLWIN'

In [52]: haveatry.lower()
Out[52]: 'lakerswiillwin'

In [53]: haveatry.swapcase()
Out[53]: 'LAKERSWIILLWIN'

In [54]: haveatry
Out[54]: 'lakerswiillwin'

next introduce ascii code

1
2
3
4
5
6
7
8
In [55]: ord('a')
Out[55]: 97

In [56]: ord('A')
Out[56]: 65

In [57]: hex(ord('a'))
Out[57]: '0x61' #convert tenth into sixth

and ascii expand into the unicode standard

1
2
3
4
5
6
7
8
9
10
11
12
13
In [62]: from unicodedata import name,lookup

In [63]: name('a')
Out[63]: 'LATIN SMALL LETTER A'

In [64]: name('L')
Out[64]: 'LATIN CAPITAL LETTER L'

In [65]: lookup('snowman')
Out[65]: '☃'

In [70]: lookup('soccer ball').encode()
Out[70]: b'\xe2\x9a\xbd'
  • mutation operation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
In [71]: suits=['lakers','heat','wirrors']

In [72]: original_suits=suits

In [73]: suits.pop()
Out[73]: 'wirrors'

In [74]: suits
Out[74]: ['lakers', 'heat']

In [75]: suits.remove('lakers')

In [76]: suits
Out[76]: ['heat']

In [77]: suits.append('bears')

In [78]: suits.extend(['tigers','suns'])

In [79]: suits
Out[79]: ['heat', 'bears', 'tigers', 'suns']

In [80]: suits[0:2]
Out[80]: ['heat', 'bears']

In [81]: original_suits
Out[81]: ['heat', 'bears', 'tigers', 'suns']
#we can see not only change different name but also change numbers in list which is different from language C

here introduce a special dictionary in python

1
2
3
4
5
6
7
8
9
10
11
12
In [1]: haveatry={'t':1,'pp':98,'fuck':69}

In [2]: haveatry['fuck']
Out[2]: 69

In [3]: haveatry['cao']=96

In [4]: haveatry.pop('pp')
Out[4]: 98

In [5]: haveatry
Out[5]: {'t': 1, 'fuck': 69, 'cao': 96}
  • tuples

it means it can’t be changed in python language

but two tuples can add to creat a new tuple

  • mutation

distinguish idetity and equality:

identity:#exp0# is #exp1#

if result is true both two expression evaluate to the same object

equality:#exp0# == #exp1#

if result is true both two expression evaluate to equal value

lecture2-objects

  • Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class ClassName:
# 类的属性和方法定义在这里
# example
class Employee:
# 类的属性
company = "ABC Corp"

# 类的方法
def greet(self):
return "Hello, Employee"
# 创建类的实例
emp = Employee()

# 访问类的属性
print(emp.company) # 输出:"ABC Corp"

# 调用类的方法
print(emp.greet()) # 输出:"Hello, Employee"
#moreover
class Employee:
def __init__(self, name, department):# 双下划线
self.name = name
self.department = department

def info(self):
return f'Employee Name: {self.name}, Department: {self.department}'

# 创建类的实例
emp = Employee('John Doe', 'HR')

# 调用类的方法
print(emp.info()) # 输出:"Employee Name: John Doe, Department: HR"

lectrue3-inheritance and string representation

  • attributes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
In [14]: class account:
...: intrest=0.02
...: def __init__(self,holder):
...: self.holder=holder
...: self.balance=0
...:

In [15]: my_account=account('LAKERs')

In [16]: my_account.intrest=0.08 #instance attribute assignment

In [17]: print(my_account.intrest)
0.08

In [18]: print(my_account.balance)
0

In [19]: account.intrest=0.04 # class attribute assignment but don't change the result which has completed instance attribute assignment
In [20]: print(my_account.intrest)
0.08

In [21]: her_account=account('jj')

In [22]: her_account.intrest
Out[22]: 0.04
In [23]: account.intrest=0.05

In [24]: her_account.intrest
Out[24]: 0.05

analyse:all these result from ‘intrest’ in class structrue which is diffrent from ‘folder’ and ‘balance’ in class structrue

  • inheritance

inheritance is a method for relating classes together

most behavior next is shared with the base calss account which means inheritance

1
2
3
4
5
class checkingaccount(account):
withdraw_fee=1
intrest=0.01
def withdraw(self,account):
return account.withdraw(self,account+self.withdraw_fee)
  • object-oriented design

designing for inheritance

  • attribute look-up practice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class A:
z=-1
def f(self,x):
return B(x-1)
class B(A):
n=4
def __init__(self,y):
if y:
self.z=self.f(y)
else:
self.z=C(y+1)
class C(B):
def f(self,x):
return x
>>> a=A()
>>> b=B(1)
>>> b.n=5
>>> C(2).n
4
>>> a.z==C.z #because of inheitance
True
>>> a.z==b.z
False
  • multiple inheritance
1
2
3
4
class exampleaccount(checkingaccount,savingaccount):
def __init__(self,account_holder):
self.holder=account.holder
self.balance=1

analyse:both checkingaccount and savingaccoujnt base on account

week4

lecture1-iterators and generators

  • iterator

iter(iterable) :return an iterator over the elements of an iterable value

next(iterator):return the next element in an iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
In [1]: s=[[1,2],3,4,5]

In [2]: next(s)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[2], line 1
----> 1 next(s)

TypeError: 'list' object is not an iterator

In [3]: t=iter(s)

In [4]: next(t)
Out[4]: [1, 2]

In [5]: list(t)
Out[5]: [3, 4, 5]

In [6]: next(t)
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
Cell In[6], line 1
----> 1 next(t)

StopIteration:
  • dictionary iteration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
In [13]: p={'one':1,'two':2}
n [15]: k=iter(p.values())

In [16]: next(k)
Out[16]: 1
In [18]: p['zero']=0

In [19]: k1=iter(p.keys())

In [20]: next(k1)
Out[20]: 'one'

In [21]: next(k1)
Out[21]: 'two'

In [22]: p
Out[22]: {'one': 1, 'two': 2, 'zero': 0}

In [23]: next(k1)
Out[23]: 'zero'
In [24]: k2=iter(p)

In [25]: next(k2)
Out[25]: 'one'
  • for statement
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
In [27]: r=range(3,6)

In [28]: r
Out[28]: range(3, 6)

In [29]: ri=iter(r)

In [30]: for k in ri:
...: print(k)
...:
3
4
5

In [31]: next(ri)
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
Cell In[31], line 1
----> 1 next(ri)

StopIteration:
In [34]: ri=iter(r)

In [35]: next(ri)
Out[35]: 3

In [36]: for k in ri:
...: print(k)
...:
4
5

analyse:when we take some tips to treat iterator as list or dictionary,they will convert to which and we should reaptedly do iter.

  • built-in fuctions for iteration
1
2
3
4
5
6
7
map(fuc,iterable): iterate over func(x) for x in iterator
filter(func,iterable): iterate over x in iterable if func(x)
zip(first_iter,second_iter):iterate over co-indexed (x,y)pairs
reversed(sequence):iterate over x in a sequence in reversed_order
list(iterable):craet a list containing all x in iterable
tuple(iterable:):craet a tuple containing all x in iterable
sorted(iterable):craet a sorted list containing x in iterable

for example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# map
In [37]: bcd=['b','c','d']

In [38]: m=map(lambda x:x.upper(),bcd)

In [39]: next(m)
Out[39]: 'B'
In [52]: c=range(5)
# filter
In [53]: f=lambda x:x>2

In [54]: t=filter(f,c)

In [55]: next(t)
Out[55]: 3

In [56]: next(t)
Out[56]: 4
# reversed
In [57]: t=reversed(range(5))

In [58]: next(t)
Out[58]: 4
# zip
list(zip(range(5),range(1,8))
...:
...: )
Out[59]: [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
  • generators

a generator function is a function that yields values intead of returning them

1
2
3
4
5
6
7
8
9
10
In [60]: def haveatry(x):
...: yield x
...: yield -x
...:
>>> c=haveatry(4)
In [64]: next(c)
Out[64]: 4

In [65]: next(c)
Out[65]: -4
  • generator and iterator
1
a yield from statement yield all values from an iterator or iterable
  • generator function with return statemennt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# upon executing a return statement,a generator function exits and cannot yield any values
In [9]: def f(x):
...: yield x
...: yield x+1
...: return
...: yield x+2
...:

In [10]: list(f(4))
Out[10]: [4, 5]
# providing a value to be returned is allowed,but this value is not yielded
In [11]: def f(x):
...: yield x
...: yield x+1
...: return x+2
...: yield x+3
...:

In [12]: list(f(4))
Out[12]: [4, 5]
# it is possible to access the returned value

In [13]: def g(x):
...: y=yield from f(x)
...: yield y
...:

In [14]: list(g(4))
Out[14]: [4, 5, 6]

lectrue2-efficiency

  • measuring efficiency

  • exponentiation

fast exp

1
2
3
4
5
6
7
In [36]: def fast_exp(b,n):
...: if(n==0):
...: return 1
...: elif(n%2==0):
...: return square(fast_exp(b,n//2))
...: else:
...: return fast_exp(b,n-1)*b
  • orders of growth

  • memo(a way to imporve efficiency)

for example of fib

1
2
3
4
5
6
7
8
def fibonacci(n, memo = {}):
...: if n <= 0:
...: return 0
...: elif n == 1:
...: return 1
...: elif n not in memo:
...: memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
...: return memo[n]

week5

lecture1-tree

  • tree class

recursive description:

1
2
3
4
a tree has a root label and a list of branches
each branch is a tree
a tree with zero branches is called a leaf
a tree starts at the root

tree class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class TreeNode:
def __init__(self, value):
self.value = value # 当前节点的值
self.children = [] # 列表,包含子节点

def add_child(self, child_node):
self.children.append(child_node) # 添加子节点

def remove_child(self, child_node):
self.children.remove(child_node) # 移除子节点

def traverse(self):
nodes_to_visit = [self]
while len(nodes_to_visit) > 0:
current_node = nodes_to_visit.pop()
print(current_node.value)
nodes_to_visit += current_node.children
  • tree mutation

example:pruning tree

1
2
3
4
def prune(t,n):
t.branches=[b for b in t.branches if b.label!=b]
for b in t.branches:
prune(b,n)

观众老爷能赏口饭吃吗

图片的替代文字

本文总阅读量
本文作者:Lane
本文链接:https://lakerswillwin.github.io/2024/05/03/cs61a/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可