跟课 CS61A FALL 2015

课程开始变难了，做个笔记吧。

week4 hw03
Question 3: Count change

def count_change(amount):

    """Return the number of ways to make change for amount.

    >>> count_change(7)

    6

    >>> count_change(10)

    14

    >>> count_change(20)

    60

    >>> count_change(100)

    9828

    """

    "*** YOUR CODE HERE ***"

    def max_num(x):

        if x <= 1:

            return 0

        else:

            i = 1

            while  i < x:

                i = i * 2

            return i // 2

    def using_num(m , n):

        if m == 1:

            return 1

        elif m <= 0:

            return 0

        elif n <= 0:

            return 0

        elif n == 1:

            return 1

        else:

            with_max = using_num(m - n, n)

            without_max = using_num(m, n // 2)

            return without_max + with_max

    return using_num(amount, max_num(amount))

图解：

                                           using_num(7,4)

                         (3, 4)                      +                             (7, 2)

            (-1, 4)      +         (3, 2)                              (5, 2)        +           (7, 1)

                             (1, 2)     +   (3, 1)             (3, 2)   +          (5, 1)

                                                              (1, 2) + (3, 1)

elyn 发表于 2015-12-30 00:02
你用的cmd吗？换cmd试试？
我记得我最先也是要填邮箱，最开始的时候，然后捣鼓了半天换了cmd就可以了，
...

谢谢！                           

Week 5 discussion 3

Tree:

def tree(root, branches=[]):
        for branch in branches:
                assert is_tree(branch)
        return [root] + list(branches)

def branches(tree):
        return tree[1:]

def is_tree(tree):
        if type(tree) != list or len(tree) < 1:
                return False
        for branch in branches(tree):
                if not is_tree(branch):
                        return False
        return True

def root(tree):
        return tree[0]

def is_leaf(tree):
        return not branches(tree)

def square_tree(trees):
        return tree(root(trees)**2, [square_tree(branch) for branch in branches(trees)])

def hight(trees):
        if is_leaf(trees):
                return 0
        return max([hight(branch) for branch in branches(trees)])+1
               
def tree_size(trees):
        return sum([tree_size(branch) for branch in branches(trees)]) + 1

def tree_max(trees):
        return max([root(trees)] + [tree_max(branch) for branch in branches(trees)])

def find_path(tree, value):
        if root(tree) == value:
                return [root(tree)]
        else:
                for branch in branches(tree):
                        if find_path(branch, value):
                                return [root(tree)] + find_path(branch, value)

def hailstone_tree(n, hight):
        if hight == 0:
                return tree(n)
        else:
                branches = [hailstone_tree(2*n, hight-1)]                           //all hailstone numbers come from last number/ 2
                if (n-1) % 3 == 0 and ((n-1) // 3 )% 2 != 0 and ((n-1) // 3 ) != 1:   
                        branches += [hailstone_tree((n-1)//3, hight-1)]    // if last number comes from (a odd number * 3 +1), then there is other branch
                return tree(n, branches)

question and solution: http://cs61a.org/disc/disc03_sol.pdf

Question 4: Towers of Hanoi

def print_move(origin, destination):
    """Print instructions to move a disk."""
    print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
    """Print the moves required to move n disks on the start pole to the end
    pole without violating the rules of Towers of Hanoi.

    n -- number of disks
    start -- a pole position, either 1, 2, or 3
    end -- a pole position, either 1, 2, or 3

    There are exactly three poles, and start and end must be different. Assume
    that the start pole has at least n disks of increasing size, and the end
    pole is either empty or has a top disk larger than the top n start disks.

    >>> move_stack(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> move_stack(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> move_stack(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
    if n == 1:
        print_move(start, end)
    else:
        other = 6 - start - end
        move_stack(n-1, start, other)
        print_move(start, end)
        move_stack(n-1, other, end)

真为自己智商捉急，看了答案才明白。
一道十分典型的递归：
递归问题要点：
1，考虑最简情况。
2 , else 只考虑n 和 n-1 的关系。

这道题中，第n个盘子的最终情况是从它在的地方去end， 那么第n-1个盘子去的地方必然是除end外剩下的柱子。表示柱子的1， 2， 3的和为6，所以 other = 6 - start - end。第n-1个盘子移去other后，移第n个盘子去end，于是有接下来的print_move(start, end), 之后再把第n-1个盘子从other移到end.

Question 5: Anonymous factorial

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    """
    return (lambda f: lambda k: f(f, k))(lambda f , k: k if k == 1 else k * f(f, k-1) )

这周的题一下子就变得好难，看了答案，自己又写了一遍，笔记如下：      
这道题要点，把函数当做参数传入，构造call, 在call里用lambda构造这个函数的behavior，这样就解决了迭代时需要函数名的问题。主要分为两部分。
1，第一个括号： (lambda f: lambda k: f(f, k))
构造一个需要f函数作为参数的函数，返回值是需要k为参数的函数，返回f函数的值，并且规定了f是一个需要2个参数的函数，f自身和k
2，第二个括号：(lambda f , k: k if k == 1 else k * f(f, k-1) )
这部分作为第一个括号的第一个call，构造f函数的行为，需要2个参数：f, k. 返回值为k或else后的值，if给出最简式，else给出，k和k-1的关系
3，注意环境变量的变化，写成相同的名字便于理解，实际并不相同。

楼主加油～

另外你可以去论坛里做自我介绍，领取100大米，系统消息里有说明。

lh6210 发表于 2015-11-30 12:13
楼主加油～

另外你可以去论坛里做自我介绍，领取100大米，系统消息里有说明。

谢谢，已经报道过啦，一起加油~

请问lz，如果只学过C来学这个可以吗？这门课学完之后接下来要学些什么课程呢？

【我刚打算开始学，有点摸不着头脑，不知道从哪里入手。好多coursera上的课程都结束了，现在都点不进去。如果只跟youtube上看视频的话好多lab都没地方做的吧？
求lz推荐学习策略，哪些课程，从哪里去学？ 万分感谢啊！！

应该可以吧，我也是转专业刚开始学，我记得LAB和HW都可以做呀？用python ok -q xxx check.
我C都还没有学完。跟的中国大学的mooc上浙大的课程。现在C进阶WEEK 4。
不过之前把JAVA 的初级进阶一口气跟完了，看的之前就已经完结了课，也是浙大同一个老师的课，貌似是网易云课堂的，完结了也可以看。然后开始跟这个的。

lyr1994 发表于 2015-12-7 23:06
请问lz，如果只学过C来学这个可以吗？这门课学完之后接下来要学些什么课程呢？

【我刚打算开始学，有点 ...

应该可以吧，我也是转专业刚开始学，我记得LAB和HW都可以做呀？用python ok -q xxx check.
我C都还没有学完。跟的中国大学的mooc上浙大的课程。现在C进阶WEEK 4。
不过之前把JAVA 的初级进阶一口气跟完了，看的之前就已经完结了课，也是浙大同一个老师的课，貌似是网易云课堂的，完结了也可以看。然后开始跟这个的。

elyn 发表于 2015-12-7 23:20
应该可以吧，我也是转专业刚开始学，我记得LAB和HW都可以做呀？用python ok -q xxx check.
我C都还没 ...

谢谢lz！ 这门课是有专门一个网站来学（cs61a.org），不知道有没有类似的有这样一个网站的课程呢？

lyr1994 发表于 2015-12-8 12:04
谢谢lz！ 这门课是有专门一个网站来学（cs61a.org），不知道有没有类似的有这样一个网站的课程呢？

你是说什么有没有类似这样的网站来学？