一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3003|回复: 33
收起左侧

跟课 CS61A FALL 2015

[复制链接] |试试Instant~ |关注本帖
elyn 发表于 2015-11-28 23:06:14 | 显示全部楼层 |阅读模式

[其他]CS61A FALL 2015 #4 - 2015-08-26@UCBerkekly

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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)

评分

2

查看全部评分

小菜 发表于 2015-12-30 09:39:41 | 显示全部楼层
elyn 发表于 2015-12-30 00:02
你用的cmd吗?换cmd试试?
我记得我最先也是要填邮箱,最开始的时候,然后捣鼓了半天换了cmd就可以了,
...

谢谢!                           
回复 支持 1 反对 0

使用道具 举报

 楼主| elyn 发表于 2015-11-29 00:53:30 | 显示全部楼层
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.
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-11-29 11:50:38 | 显示全部楼层
本帖最后由 elyn 于 2015-11-29 11:53 编辑

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,注意环境变量的变化,写成相同的名字便于理解,实际并不相同。
回复 支持 反对

使用道具 举报

lh6210 发表于 2015-11-30 12:13:33 | 显示全部楼层
楼主加油~

另外你可以去论坛里做自我介绍,领取100大米,系统消息里有说明。
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-11-30 13:35:10 | 显示全部楼层
lh6210 发表于 2015-11-30 12:13
楼主加油~

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

谢谢,已经报道过啦,一起加油~
回复 支持 反对

使用道具 举报

lyr1994 发表于 2015-12-7 23:06:18 | 显示全部楼层
请问lz,如果只学过C来学这个可以吗?这门课学完之后接下来要学些什么课程呢?

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

使用道具 举报

 楼主| elyn 发表于 2015-12-7 23:20:32 | 显示全部楼层
应该可以吧,我也是转专业刚开始学,我记得LAB和HW都可以做呀?用python ok -q xxx check.
我C都还没有学完。跟的中国大学的mooc上浙大的课程。现在C进阶WEEK 4。
不过之前把JAVA 的初级进阶一口气跟完了,看的之前就已经完结了课,也是浙大同一个老师的课,貌似是网易云课堂的,完结了也可以看。然后开始跟这个的。
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-7 23:20:48 | 显示全部楼层
lyr1994 发表于 2015-12-7 23:06
请问lz,如果只学过C来学这个可以吗?这门课学完之后接下来要学些什么课程呢?

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


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

使用道具 举报

lyr1994 发表于 2015-12-8 12:04:04 | 显示全部楼层
elyn 发表于 2015-12-7 23:20
应该可以吧,我也是转专业刚开始学,我记得LAB和HW都可以做呀?用python ok -q xxx check.
我C都还没 ...

谢谢lz! 这门课是有专门一个网站来学(cs61a.org),不知道有没有类似的有这样一个网站的课程呢?
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-8 12:33:44 | 显示全部楼层
lyr1994 发表于 2015-12-8 12:04
谢谢lz! 这门课是有专门一个网站来学(cs61a.org),不知道有没有类似的有这样一个网站的课程呢?

你是说什么有没有类似这样的网站来学?
回复 支持 反对

使用道具 举报

lyr1994 发表于 2015-12-8 13:40:15 | 显示全部楼层
elyn 发表于 2015-12-8 12:33
你是说什么有没有类似这样的网站来学?

那个cs61a的课程网站不是berkely自己弄的吗,有lecture、lab、HW什么的,就想类似的课程网站~
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-8 14:18:06 | 显示全部楼层
lyr1994 发表于 2015-12-8 13:40
那个cs61a的课程网站不是berkely自己弄的吗,有lecture、lab、HW什么的,就想类似的课程网站~

http://ocw.mit.edu/courses/
回复 支持 反对

使用道具 举报

calbears 发表于 2015-12-12 12:49:59 | 显示全部楼层
cs61a.org是官方的网站
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-16 23:12:38 | 显示全部楼层
Week 5 lab04
Question 12: Flatten
Write a function flatten that takes a (possibly deep) list and "flattens" it. For example:
>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]
Hint: you can check if something is a list by using the built-in type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

    new_lst= []
    for x in lst:
        if type(x) == list:
            new_lst += flatten(x)
        else:
            new_lst += [x]
    return new_lst


回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-16 23:17:50 | 显示全部楼层
本帖最后由 elyn 于 2015-12-16 23:19 编辑

Week 5 lab04
Question 13: Merge
Write a function merge that takes 2 sorted lists lst1 and lst2, and returns a new list that contains all the elements in the two lists in sorted order.

def merge(lst1, lst2):
    """Merges two sorted lists.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
iterative:
    new_lst = []
    while lst1 and lst2:
        if lst1[0] < lst2[0]:
            new_lst += [lst1[0]]
            lst1 = lst1[1:]
        else:
            new_lst += [lst2[0]]
            lst2 = lst2[1:]
    if lst1:
        return new_lst + lst1
    else:
        return new_lst + lst2


recursive:
  if not lst1 or not lst2:
        return lst1 + lst2
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-16 23:36:23 | 显示全部楼层
本帖最后由 elyn 于 2015-12-17 00:14 编辑

Week 5 Tips:

1. join
print('  '.join(i for i in [1, 2, 3, 4, 5])
>>> 1 2 3 4 5
print(' + '.join(i for i in [1, 2, 3, 4, 5])
>>> 1 + 2 + 3 + 4 + 5

2.list()
不能list(int object)

3.list comprehension
video: https://www.youtube.com/watch?v= ... VLYJsBamd9hSOOSrYgB
example: [x for x in [1,2,3,4] if x > 2]
>>>[3, 4]
4.slicing
list_obj[start:end:step]
start 缺省 从0开始
end 缺省 直到最后
step缺省 默认为1
step为负 从后往前
index 为负从后往前计数

list_num[ 0, 1, 2, 3, 4, 5, 6, 7]
list_num[-1]
>>>7
list_num[2:-2]
>>>[2,3,4,5]
list_num[4:2]
>>>[]
list_num[6::-2]
>>>[6,4,2,0]

回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-17 17:49:05 | 显示全部楼层
本帖最后由 elyn 于 2015-12-17 17:57 编辑

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
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-17 23:46:12 | 显示全部楼层
Week 5 hw04
Q8:
Write a function polynomial that takes an interval x and a list of coefficients c, and returns the interval containing all values of f(t) for t in interval x, where:

f(t) = c[k-1] * pow(t, k-1) + c[k-2] * pow(t, k-2) + ... + c[0] * 1
Like quadratic, your polynomial function should return the smallest such interval, one that does not suffer from the multiple references problem.

Hint: You can approximate this result. Try using Newton's method.

貌似涉及很多数学知识,已忘光。。先留着以后做吧。。
回复 支持 反对

使用道具 举报

想念英雄 发表于 2015-12-28 20:36:11 | 显示全部楼层
赞一下楼主,这个和15 Spring的是类似的课程内容吗?http://cs61b.ug/sp15/
回复 支持 反对

使用道具 举报

 楼主| elyn 发表于 2015-12-29 12:57:39 | 显示全部楼层
想念英雄 发表于 2015-12-28 20:36
赞一下楼主,这个和15 Spring的是类似的课程内容吗?http://cs61b.ug/sp15/

有的视频是15spring有的是15fall新录的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 18:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表