红魔咖啡馆


头发越掉越多，头发越掉越少

【CS61A】CS61A——Lab6

  • ~10.58K 字
  1. 1. Lab 6
    1. 1.1. Q1: Bank Account
    2. 1.2. Q2: Email
    3. 1.3. Q3: Make Change
    4. 1.4. Q4: Change Machine

Lab 6

Q1: Bank Account

扩充Account类，添加属性transaction，即一个transaction列表实例，每一次调用都会创建一个该实例，记录每次调用deposit和withdraw前后的余额。另外，每个transaction有一个id属性，记录之前账户对deposit或withdraw的调用次数。id对于每个账户内是唯一的，而不是在所有transaction中的全局标识符

transaction有两个方法：

  • changed：若在调用前后balance发生变化则返回True，否则返回False
  • report：返回一个字符串用来描述该次transaction，以id开始，之后返回消息
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Transaction:
    def __init__(self, id, before, after):
        self.id = id
        self.before = before
        self.after = after

    def changed(self):
        """Return whether the transaction resulted in a changed balance."""
        if self.before == self.after:
            return False
        else :
            return True

    def report(self):
        """Return a string describing the transaction.

        >>> Transaction(3, 20, 10).report()
        '3: decreased 20->10'
        >>> Transaction(4, 20, 50).report()
        '4: increased 20->50'
        >>> Transaction(5, 50, 50).report()
        '5: no change'
        """
        msg = 'no change'
        if self.changed():
            if self.before > self.after:
                msg = 'decreased ' + str(self.before)+'->'+str(self.after)
            else :
                msg = 'increased ' + str(self.before) + '->' + str(self.after)
        return str(self.id) + ': ' + msg

class Account:
    """A bank account that tracks its transaction history.

    >>> a = Account('Eric')
    >>> a.deposit(100)    # Transaction 0 for a
    100
    >>> b = Account('Erica')
    >>> a.withdraw(30)    # Transaction 1 for a
    70
    >>> a.deposit(10)     # Transaction 2 for a
    80
    >>> b.deposit(50)     # Transaction 0 for b
    50
    >>> b.withdraw(10)    # Transaction 1 for b
    40
    >>> a.withdraw(100)   # Transaction 3 for a
    'Insufficient funds'
    >>> len(a.transactions)
    4
    >>> len([t for t in a.transactions if t.changed()])
    3
    >>> for t in a.transactions:
    ...     print(t.report())
    0: increased 0->100
    1: decreased 100->70
    2: increased 70->80
    3: no change
    >>> b.withdraw(100)   # Transaction 2 for b
    'Insufficient funds'
    >>> b.withdraw(30)    # Transaction 3 for b
    10
    >>> for t in b.transactions:
    ...     print(t.report())
    0: increased 0->50
    1: decreased 50->40
    2: no change
    3: decreased 40->10
    """

    # *** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        self.counter = -1
        self.transactions = []

    def id_gene(self):
        self.counter+=1
        yield self.counter

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """
        pre = self.balance
        self.balance = self.balance + amount
        self.transactions.append(Transaction(next(self.id_gene()),pre, self.balance))
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount, add the withdraw
        to the transaction history, and return the new balance.
        """
        if amount > self.balance:
            self.transactions.append(Transaction(next(self.id_gene()), self.balance, self.balance))
            return 'Insufficient funds'
        pre = self.balance
        self.balance = self.balance - amount
        self.transactions.append(Transaction(next(self.id_gene()), pre, self.balance))
        return self.balance

Q2: Email

一个邮箱系统包括三个类：Email, Server, Client

Client类可以compose邮件，该邮件会被send到Server类中

Server类会把该邮件运到对应Client的inbox中，为了实现这个，一个Server类拥有一个字典clients，将Email中的recipient_name与拥有该名称的Client对象绑定

注意：client永远不会更改其使用的server

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Email:
    """An email has the following instance attributes:

        msg (str): the contents of the message
        sender (Client): the client that sent the email
        recipient_name (str): the name of the recipient (another client)
    """
    def __init__(self, msg, sender, recipient_name):
        self.msg = msg
        self.sender = sender
        self.recipient_name = recipient_name

class Server:
    """Each Server has one instance attribute called clients that is a
    dictionary from client names to client objects.
    """
    def __init__(self):
        self.clients = {}

    def send(self, email):
        """Append the email to the inbox of the client it is addressed to."""
        self.clients[email.recipient_name].inbox.append(email)

    def register_client(self, client):
        """Add a client to the dictionary of clients."""
        self.clients[client.name] = client

class Client:
    """A client has a server, a name (str), and an inbox (list).

    >>> s = Server()
    >>> a = Client(s, 'Alice')
    >>> b = Client(s, 'Bob')
    >>> a.compose('Hello, World!', 'Bob')
    >>> b.inbox[0].msg
    'Hello, World!'
    >>> a.compose('CS 61A Rocks!', 'Bob')
    >>> len(b.inbox)
    2
    >>> b.inbox[1].msg
    'CS 61A Rocks!'
    >>> b.inbox[1].sender.name
    'Alice'
    """
    def __init__(self, server, name):
        self.inbox = []
        self.server = server
        self.name = name
        server.register_client(self)

    def compose(self, message, recipient_name):
        """Send an email with the given message to the recipient."""
        email = Email(message, self, recipient_name)
        self.server.send(email)

这里的inbox存储的是每一个email实例，故传参时应传入self

Q3: Make Change

实现make_change函数，输入amount和coins字典

coins字典的键是一个正整数，表示面额；值也是一个正整数，表示硬币数量，如{1:4, 5:2}表示四个便士和两个五分

函数返回列表，其中元素是求和能达到amount数量的硬币列表，其中每种面额k最多使用coins[k]次

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
33
34
35
36
37
38
39
40
41
def make_change(amount, coins):
    """Return a list of coins that sum to amount, preferring the smallest coins
    available and placing the smallest coins first in the returned list.

    The coins argument is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> make_change(2, {2: 1})
    [2]
    >>> make_change(2, {1: 2, 2: 1})
    [1, 1]
    >>> make_change(4, {1: 2, 2: 1})
    [1, 1, 2]
    >>> make_change(4, {2: 1}) == None
    True

    >>> coins = {2: 2, 3: 2, 4: 3, 5: 1}
    >>> make_change(4, coins)
    [2, 2]
    >>> make_change(8, coins)
    [2, 2, 4]
    >>> make_change(25, coins)
    [2, 3, 3, 4, 4, 4, 5]
    >>> coins[8] = 1
    >>> make_change(25, coins)
    [2, 2, 4, 4, 5, 8]
    """
    if not coins:
        return None
    smallest = min(coins)
    rest = remove_one(coins, smallest)
    if amount < smallest:
        return None
    elif amount == smallest:
        return [smallest]
    else:
        temp = make_change(amount-smallest, rest)
        if not temp:
            return make_change(amount, rest)
        else :
            return [smallest]+temp

首先尝试使用最小面额的coin，但若无法实现则尝试使用更大面额

具体步骤：

  • 进入函数默认使用一个最小面额硬币

  • 若amount==samllest：最小面额硬币即可满足需求，返回包含该值的列表

  • 否则，递归调用make_change(amount-smallest, rest)，减去一次最小面额

  • 若返回一个列表，则将该最小面额放入列表，并继续递归调用，将其返回的列表接在后面

  • 若返回None，则表明使用最小面额无法实现，故递归调用make_change(amount, rest)，让函数把最小面额硬币去除后使用更大面额尝试

Q4: Change Machine

完成ChangeMachine类中的change方法，每个该类的实例包含了一些coins，一开始都是便士。change方法传入正整数coin，把他添加到coins中，并返回列表，其中的硬币面额之和要达到cin

该类倾向于使用尽可能多的最小面额硬币

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class ChangeMachine:
    """A change machine holds a certain number of coins, initially all pennies.
    The change method adds a single coin of some denomination X and returns a
    list of coins that sums to X. The machine prefers to return the smallest
    coins available. The total value in the machine never changes, and it can
    always make change for any coin (perhaps by returning the coin passed in).

    The coins attribute is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> m = ChangeMachine(2)
    >>> m.coins == {1: 2}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.coins == {2: 1}
    True
    >>> m.change(2)
    [2]
    >>> m.coins == {2: 1}
    True
    >>> m.change(3)
    [3]
    >>> m.coins == {2: 1}
    True

    >>> m = ChangeMachine(10) # 10 pennies
    >>> m.coins == {1: 10}
    True
    >>> m.change(5) # takes a nickel & returns 5 pennies
    [1, 1, 1, 1, 1]
    >>> m.coins == {1: 5, 5: 1} # 5 pennies & a nickel remain
    True
    >>> m.change(3)
    [1, 1, 1]
    >>> m.coins == {1: 2, 3: 1, 5: 1}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.change(2) # not enough 1's remaining; return a 2
    [2]
    >>> m.coins == {2: 1, 3: 1, 5: 1}
    True
    >>> m.change(8) # cannot use the 2 to make 8, so use 3 & 5
    [3, 5]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(1) # return the penny passed in (it's the smallest)
    [1]
    >>> m.change(9) # return the 9 passed in (no change possible)
    [9]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(10)
    [2, 8]
    >>> m.coins == {10: 1}
    True

    >>> m = ChangeMachine(9)
    >>> [m.change(k) for k in [2, 2, 3]]
    [[1, 1], [1, 1], [1, 1, 1]]
    >>> m.coins == {1: 2, 2: 2, 3: 1}
    True
    >>> m.change(5) # Prefers [1, 1, 3] to [1, 2, 2] (more pennies)
    [1, 1, 3]
    >>> m.change(7)
    [2, 5]
    >>> m.coins == {2: 1, 7: 1}
    True
    """
    def __init__(self, pennies):
        self.coins = {1: pennies}

    def change(self, coin):
        """Return change for coin, removing the result from self.coins."""
        self.coins[coin] = self.coins.get(coin, 0)+1
        result = make_change(coin, self.coins)
        for c in result:
            self.coins = remove_one(self.coins, c)
        return result
  • 将加入的coin放入coins字典，注意，这里的键为面额对应数量，而值为面额，故我们用get方法获取传入coin的键，并在此基础上+1（我们可以在第二个参数设置默认值，当没有对应面额时，get会返回设定值而非None）
  • 之后调用make_change方法，获得最小面额能实现达到coin数的硬币列表
  • 使用remove_one将类中已经用过的硬币移除
  • 返回列表
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵