一亩三分地论坛

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

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

[CS61A]Extra HW01

[复制链接] |试试Instant~ |关注本帖
sky420 发表于 2015-5-8 03:52:51 | 显示全部楼层 |阅读模式

[其他]CS61A #1 - 4@UCB

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

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

x
本帖最后由 sky420 于 2015-5-8 04:27 编辑

Extra Homework 1 about Newton's method to find the appriximate point.
http://gaotx.com/cs61a/hw/extra01/

My solution
http://gaotx.com/blogs/2015/05/07/cs61a-ehw01/

评分

1

查看全部评分

MarcoLiang 发表于 2015-5-10 16:54:46 | 显示全部楼层
def intersect(f, df, g, dg):
    """Return where f with derivative df intersects g with derivative dg.

    >>> parabola, line = lambda x: x*x - 2, lambda x: x + 10
    >>> dp, dl = lambda x: 2*x, lambda x: 1
    >>> intersect(parabola, dp, line, dl)
    4.0
    """
    def h(x):
        return f(x) - g (x)
    def dh(x):
        return df(x) -dg(x)
        
    return find_zero (h, dh)

def find_zero(f, df):
    def near_zero(x):
        return approx(f(x), 0)
    return improve (newton_update(f, df), near_zero)

def improve(update, close, x = 10):
    while not close(x):
        print x
        x = update(x)
    return x

def approx (x,y,tolerance = 1e-10):
    return abs(x-y) < tolerance
   

def newton_update(f,df):
    def update (x):
        return x- f(x)/df(x)
    return update   

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wkh279 发表于 2015-7-17 20:14:34 | 显示全部楼层
最近才开始跟啊
##################################
# Newton's method (from lecture) #
##################################

def improve(update, close, guess=1, max_updates=100):
    """Iteratively improve guess with update until close(guess) is true."""
    k = 0
    while not close(guess) and k < max_updates:
        guess = update(guess)
        k = k + 1
    return guess

def approx_eq(x, y, tolerance=1e-15):
    """Whether x is within tolerance of y."""
    return abs(x - y) < tolerance

def find_zero(f, df):
    """Return a zero of the function f with derivative df."""
    def near_zero(x):
        return approx_eq(f(x), 0)
    return improve(newton_update(f, df), near_zero)

def newton_update(f, df):
    """Return an update function for f with derivative df."""
    def update(x):
        return x - f(x) / df(x)
    return update

def nth_root_of_a(n, a):
    """Return the nth root of a.

    >>> nth_root_of_a(2, 64)
    8.0
    >>> nth_root_of_a(3, 64)
    4.0
    >>> nth_root_of_a(6, 64)
    2.0
    """
    return find_zero(lambda x: pow(x, n) - a, lambda x: n * pow(x, n-1))

def intersect(f, df, g, dg):
    """Return where f with derivative df intersects g with derivative dg.

    >>> parabola, line = lambda x: x*x - 2, lambda x: x + 10
    >>> dp, dl = lambda x: 2*x, lambda x: 1
    >>> intersect(parabola, dp, line, dl)
    4.0
    """
    def minus_fun(x):
        return f(x)-g(x)
    def minus_derivative(x):
        return df(x)-dg(x)
    return find_zero(minus_fun, minus_derivative)

X = lambda x, derive: 1 if derive else x
K = lambda k: lambda x, derive: 0 if derive else k

def quadratic(a, b, c):
    """Return a quadratic polynomial a*x*x + b*x + c.

    >>> q_and_dq = quadratic(1, 6, 8) # x*x + 6*x + 8
    >>> q_and_dq(1.0, False)  # value at 1
    15.0
    >>> q_and_dq(1.0, True)   # derivative at 1
    8.0
    >>> q_and_dq(-1.0, False) # value at -1
    3.0
    >>> q_and_dq(-1.0, True)  # derivative at -1
    4.0
    """
    A, B, C = K(a), K(b), K(c)
    AXX = mul_fns(A, mul_fns(X, X))
    BX = mul_fns(B, X)
    return add_fns(AXX, add_fns(BX, C))

def add_fns(f_and_df, g_and_dg):
    """Return the sum of two polynomials."""
    return lambda x, derive: f_and_df(x,derive)+g_and_dg(x,derive)

def mul_fns(f_and_df, g_and_dg):
    """Return the product of two polynomials."""
    return lambda x, derive: f_and_df(x, True)*g_and_dg(x, False) + f_and_df(x,False)*g_and_dg(x, True) if derive else f_and_df(x,False)*g_and_dg(x,False)

def poly_zero(f_and_df):
    """Return a zero of polynomial f_and_df, which returns:
        f(x)  for f_and_df(x, False)
        df(x) for f_and_df(x, True)

    >>> q = quadratic(1, 6, 8)
    >>> round(poly_zero(q), 5) # Round to 5 decimal places
    -2.0
    >>> round(poly_zero(quadratic(-1, -6, -9)), 5)
    -3.0
    """
    return find_zero(lambda x: f_and_df(x,False),lambda x: f_and_df(x,True))


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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