CS入门学习笔记6-MIT 6.00.1x

Lecture 6 对象

截止目前,已学习过的算法:

  • Exhaustive enumeration
  • Guess and check
  • Bisection
  • Divide and conquer

学习过的simple data types:

  • Numbers
  • Strings

马上要接触到的Compound data types

  • Tuples
  • Lists
  • Dictionaries

1. Tuples

  • Ordered sequence of elements
  • elements can be more than just characters, even tuple can be another tuple’s element

2. Operations on Tuples

  • 连接
  • 索引
  • 切割
  • 单项–若要创建一个只有一个元素的tuple,切记要在定义时元素后加一个逗号。
    CS入门学习笔记6-MIT 6.00.1xCS入门学习笔记6-MIT 6.00.1x上例中涉及到了:
  • 创建一个空的tuple
  • 使用for循环,不断往tuple中添加新元素。
>>>divisors = findDivisors(20, 100)
>>>divisors
(1,2,4,5,10,20)
>>>total = 0
>>>for d in divisors:
    total += d
>>>print(total)
42

此处total会返回42的原因,当用for循环遍历tuple时,会从位置0开始,将每个位置对应的value取出赋给d,而非代表位置的数值。所以total相当于是把tuple divisors里面所有元素进行数值求和。

>>> x = (1, 2, (3, 'John', 4), 'Hi')
>>> x[-1][-1]
'i'
# 不要忘记string也可以分离出元素
>>> x[0:1]
(1,)
# 在slicing时一定要注意结尾到哪儿
>>> x[0] = 8
TypeError: 'tuple' object does not support item assignment 
# tuple不支持修改其中的元素

作业二
Write a procedure called oddTuples, which takes a tuple as input, and returns a new tuple as output, where every other element of the input tuple is copied, starting with the first one. So if test is the tuple (‘I’, ‘am’, ‘a’, ‘test’, ‘tuple’), then evaluating oddTuples on this input would return the tuple (‘I’, ‘a’, ‘tuple’).

def oddTuples(aTup):
    '''
    aTup: a tuple
    
    returns: tuple, every other element of aTup. 
    '''
    rTup = ()
    for i in range(0,len(aTup)):
        if i % 2 == 0:
            rTup += (aTup[i],)
            # 一开始没加"( ,)",程序报错,提示TypeError: can only concatenate tuple (not "int") to tuple,
            # 然后才意识到aTup[i]取出来的数据格式不对,进行了修改。
    return rTup

3. lists
定义方式&运算方式&与tuple的巨大区别

CS入门学习笔记6-MIT 6.00.1x
4. mutable structure与 fixed structure的对比与运用

CS入门学习笔记6-MIT 6.00.1x

Techs = ['MIT', 'Cal Tech']
Ivys = ['Harvard', 'Yale', 'Brown']

Univs = [Techs, Ivys]
Univs1 = [['MIT', 'Cal Tech'], ['Harvard', 'Yale', 'Brown']]

Techs.append('RPI')

print('Univs = ')
print(Univs)
print('')
print('Univs1 =')
print(Univs1)
# 执行过append操作后,会发现univs与univs1显示的结果不同,因为univs指向的是pointers;
# 而univs1指向的是pointers原本指向的具体内容,所以无法随着pointers所指内容更改。
# 此种现象成为aliasing(别名混用/混淆现象)
# 因此,在使用aliasing这种方法时要格外小心

CS入门学习笔记6-MIT 6.00.1x此外,lists支持直接指定元素进行修改,如:

CS入门学习笔记6-MIT 6.00.1x5. 内置函数sum
sum在调用时需要填入的是一个list,而不能直接写数字:

The function sum is a built-in function that takes one list as an argument and returns the sum of that list. The items in the list must be numeric types. Some examples:

>>> sum([1, 9, 10])
20
>>> sum([4.5, 7, 0.331])
11.831
>>> sum(['a', 'b', 'c'])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'

作业四

>>>range(10, 3)
>[]
>>>range(10,3,-1)
>[10, 9, 8, 7, 6, 5, 4]
>>>range(3, 10.5, 0.5)
>TypeError: range() integer end argument expected, got float. 
# range中的参数必须是int,不接受float形式

6. lists的相关运算

  • 使用for循环遍历lists,举例如下:
## universities
Techs = ['MIT', 'Cal Tech']
Ivys = ['Harvard', 'Yale', 'Brown']
Univs = [Techs, Ivys]

Techs.append('RPI')

for e in Univs:
    print('Univs contains ')
    print(e)
    print('   which contains')
    for u in e:
        print('      ' + u)
## 输出结果显示如下:
Univs contains 
['MIT', 'Cal Tech', 'RPI']
   which contains
      MIT
      Cal Tech
      RPI
Univs contains 
['Harvard', 'Yale', 'Brown']
   which contains
      Harvard
      Yale
      Brown
  • append 与 ‘+’的区别:
    CS入门学习笔记6-MIT 6.00.1x在此例中,attend是在mutating formal list, 而concatenation 是在creating a new list。

  • 关于使用clone的一个例子:
    CS入门学习笔记6-MIT 6.00.1x原意是想在L1中删除所有与L2重复的数值,但却因为在删除掉第一个数字“1”后,L1的指针指向发生改变,只能从当前的LI[1]即“3”开始判断,于是“2”被跳过,造成结果不对,此时便可以使用clone的方法,确保删除时有一个正确的指针参考。

CS入门学习笔记6-MIT 6.00.1x
作业五

aList = range(1, 6)
bList = aList
aList[2] = 'hello'

>>> aList is bList
>True

>>> cList = range(6, 1, -1)
>>> dList = []
>>> for num in cList:
        dList.append(num)
>>> cList is dList
>False
# 注意此处,虽然cList与dList的数值相同,但因为不是直接指向的关系,
# 所以做is判断时,结果会是False。

作业六

listA = [1, 4, 3, 0]
listB = ['x', 'z', 't', 'q']

>>>listA.sort
><function sort>
##自己老是忘记未加()的会返回function
>>>listA.sort()
#此处只是对listA进行了一个操作,并不会有返回值!!
>>>listA
>[0,1,3,4]
>>>listA.insert(0, 100)
>#此处只是对listA进行了一个操作,并不会有返回值!!
>>>listA.remove(3)
>>>listA.append(7)

7. functions as objects

  • first class objects的几大特点:
    CS入门学习笔记6-MIT 6.00.1x
  • string, numbers, list, tuple,以及functions都属于此类object。
  • function也可以作为另一个function的参数被带入。

8. higher order functions/ higher order procedures

CS入门学习笔记6-MIT 6.00.1x9. dictionaries

  • 定义
    CS入门学习笔记6-MIT 6.00.1x

  • dictionary里的项目都是无序排列的,并且不能按照number顺序号进行查找,只能用key。

  • key可以是复杂的结构,但必须是不可变的,如tuple可以做key,而list不行

  • 使用dict[‘key’]的方法时,只能用key查找value,反之不行。

10. operations on dicts
1. insertion
2. iteration
可以将dict里面元素的key用循环的方式导入至list中
CS入门学习笔记6-MIT 6.00.1x3. 查找dict里是否存在某key ‘xxx’:
dictname.has_key(‘xxx’)

  1. 判断dict里是否存在某value‘xxxx’:
    ‘xxxx’ in dictname.values()

  2. 删除特定key对应的元素:
    del dictname[‘xxx’]

  3. dict里的value也可以是一个list,如下代码所示:

animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}

animals['d'] = ['donkey']
animals['d'].append('dog')
animals['d'].append('dingo')

print animals
> {'a': ['aardvark'],
 'b': ['baboon'],
 'c': ['coati'],
 'd': ['donkey', 'dog', 'dingo']}

【作业十】

Consider the following sequence of expressions:

animals = { ‘a’: [‘aardvark’], ‘b’: [‘baboon’], ‘c’: [‘coati’]}

animals[‘d’] = [‘donkey’]
animals[‘d’].append(‘dog’)
animals[‘d’].append(‘dingo’)

We want to write some simple procedures that work on dictionaries to return information.

First, write a procedure, called howMany, which returns the sum of the number of values associated with a dictionary. For example:

print howMany(animals)
6

def howMany(aDict):
    '''
    aDict: A dictionary, where all the values are lists.

    returns: int, how many values are in the dictionary.
    '''
    n = 0
    for i in aDict.keys():
        n += len(aDict[i])
    return n

【作业十一】

Consider the following sequence of expressions:

animals = { ‘a’: [‘aardvark’], ‘b’: [‘baboon’], ‘c’: [‘coati’]}

animals[‘d’] = [‘donkey’]
animals[‘d’].append(‘dog’)
animals[‘d’].append(‘dingo’)

We want to write some simple procedures that work on dictionaries to return information.

This time, write a procedure, called biggest, which returns the key corresponding to the entry with the largest number of values associated with it. If there is more than one such entry, return any one of the matching keys.

Example usage:

biggest(animals)
‘d’

If there are no values in the dictionary, biggest should return None.

def biggest(aDict):
    '''
    aDict: A dictionary, where all the values are lists.

    returns: The key with the largest number of values associated with it
    '''
    # n为key列表中第一个key,ans为第一个key对应的value长度
    n = aDict.keys()[0]
    ans = len(aDict[n])
    # 判断dict是否有value
    if len(aDict) == 0:
        return None
    for i in aDict.keys():
        count = len(aDict[i])
        if count > ans:
            ans = count
            n = i
    return n

别人的答案:

def biggest(aDict):
    result = None
    biggestValue = 0
    for key in aDict.keys():
        if len(aDict[key]) >= biggestValue:
            result = key
            biggestValue = len(aDict[key])
    return result

作业十一对比他人,需改进之处:

  • 直接用result = none 省去了关于dict是否为空的判断;
  • biggestValue、key等的命名比我的更好理解与辨认。
上一篇:CF923E Perpetual Subtraction 题解


下一篇:二元一次不定方程的解