#### 第9次课的示例程序, 4月9日

#### 求不同换零钱方式的函数，将辅助函数局部化
#### 核心函数 ccoins 用递归地计算不同兑换方式
#### 主函数 get_coins 对具体的 n 值启动计算
def get_coins(n):
    def ccoins(k, n):
        if n == 0:
            return 1
        if k == 0 or n < 0:
            return 0
        return ccoins(k, n - amount(k)) + ccoins(k - 1, n)

    return ccoins(6, n)

from math import sin, cos, fabs

#### 求立方根的函数

def improve(x, x1):
    return(2.0 * x1 + x / x1 / x1) / 3
    
def accept(x1, x2):
    return fabs((x2 - x1)/x1) < 1E-6

def cbrt(x):
    if x == 0.0:
        return 0.0
    x1 = x
    x2 = improve(x, x1)
    while not accept(x1, x2):
        x1 = x2
        x2 = improve(x, x1)
    return x2


#### 从求立方根函数抽象出一个计算框架

def appr_method(x, improve, accept):
    if x == 0.0:
        return 0.0
    x1 = x
    x2 = improve(x, x1)
    while not accept(x1, x2):
        x1 = x2
        x2 = improve(x, x1)
    return x2

def cb_improve(x, x1):
    return(2.0 * x1 + x / x1 / x1) / 3
    
def accept(x1, x2):
    return fabs((x2 - x1)/x1) < 1E-6

def cbrt(x):
    return appr_method(x, cb_improve, accept)

def sq_improve(x, x1):
    return (x1 + x/x1)/2

def sqrt(x):
    return appr_method(x, sq_improve, accept)


#### 求一个可积函数的数值积分，积分函数需要一个函数参数和一个积分区间
#### 设参数 f 被积函数, [a, b] 是积分区间

##division = 100  # 划分数
##
def integrate(f, a, b):
    if a > b:
        a, b = b, a
    d = (b - a)/division
    s = 0
    for i in range(division):
        s += f(a + i*d)
    return s*d

##from math import sin, cos, log, pi
##print(integrate(sin, 0, pi))
##print(integrate(cos, 0, pi/2))



#### lambda 表达式的直接使用
##print((lambda x, y: x**2 + y**2)(3, 4))


#### 采用 lambda 表达式定义的求立方、求平方函数
##
def appr_method(x, improve, accept):
    if x == 0.0:
        return 0.0
    x1 = x
    x2 = improve(x, x1)
    while not accept(x1, x2):
        x1 = x2
        x2 = improve(x, x1)
    return x2

##def cbrt(x):
##    return appr_method(x,
##                       lambda x, x1:(2.0 * x1 + x / x1 / x1) / 3,
##                       lambda x1, x2: fabs((x2 - x1)/x1) < 1E-6)
##
##def sqrt(x):
##    return appr_method(x,
##                       lambda x, x1:(x1 + x/x1)/2,
##                       lambda x1, x2: fabs((x2 - x1)/x1) < 1E-6)


###### 牛顿法求函数的根
##def newton(f, df, init):
##    def improve(x1):
##        return x1 - f(x1)/df(x1)
##    
##    x1 = init
##    x2 = improve(x1)
##    while fabs(f(x2)) >= 1e-6:
##        x1 = x2
##        x2 = improve(x1)
##
##    return x2
##
##print("newton(sin, cos, 1.9)")
##print("We have:", newton(sin, cos, 1.9))


#### 数值微分函数和应用实例
####
##epsilon = 0.001
##def diff(f):
##    return lambda x: (f(x + epsilon) - f(x))/epsilon
##
##from math import sin
##print("diff(sin)(0.0)")
##print(diff(sin)(0.0), "\n")
##print("diff(sin)(1.57)")
##print(diff(sin)(1.57), "\n")
##print("diff(sin)(3.14)")
##print(diff(sin)(3.14), "\n")
##
##def cube(x):
##    return x*x*x
##
##print("diff(cube)(1.0)")
##print(diff(cube)(1.0), "\n")
##print("diff(cube)(10.0)")
##print(diff(cube)(10.0), "\n")


#### 牛顿逼近法求函数的根，被求根的函数是参数
##
epsilon = 0.001

def diff(f):
    return lambda x: (f(x + epsilon) - f(x))/epsilon

def newton(f, init):
    def improve(x1):
        return x1 - f(x1)/df(x1)

    df = diff(f)
    x1 = init
    x2 = improve(x1)
    while fabs(f(x2)) >= 1e-6:
        x1 = x2
        x2 = improve(x1)

    return x2







#### 蒙特卡罗模拟程序（通用模拟框架）和实例
####
### Suppose m >= 0, n > 0
##def gcd(m, n):
##    if m%n == 0:
##        return n
##    return gcd(n, m%n)
##
##from random import randrange
##def pi_test():
##    a = randrange(1, 2**31)
##    b = randrange(1, 2**31)
##    return gcd(a, b) == 1    
##
##def monteCarlo(test, num):
##    passed = 0
##    for i in range(num):
##        if test():
##            passed += 1
##    return passed/num
##
##from math import sqrt
##x = sqrt(6 / monteCarlo(pi_test, 500))
##print("Montecarlo pi:", x)
##x = sqrt(6 / monteCarlo(pi_test, 500000))
##print("Montecarlo pi:", x)



##def print_fibs(n) :
##    f1 = f2 = 1
##    print(1, 1, end="")
##    for k in range(1, n) :
##        f1, f2 = f2, f2 + f1
##        print("", f2, end="")
##    print("\n")
##
##print_fibs(20)


##def print_fibs1(n) :
##    f1 = f2 = 1
##    print(1, 1, sep=", ", end="")
##    for k in range(1, n) :
##        f1, f2 = f2, f2 + f1
##        print(",", f2, end="")
##    print("\n")
##
##print_fibs1(20)


for i in range(100):
    print(i, end=", " if i%10 != 9 else ",\n")





##s = "Peking University"
##t = "Beijing, 100871"
##
##addr = s + "\n" + t
##print(addr + "\n")
##
##
##i = 0
##while i < len(s) :
##    print(s[i])
##    i += 1
##
##for c in s :
##    print(c)
##
##
##ss = s = "Thank"
##s += " you! "
##s *= 2


##def gen_fibs(n) :
##    f1 = f2 = 1
##    fibs = "1, 1"
##    for k in range(1, n) :
##        f1, f2 = f2, f2 + f1
##        fibs += ", " + str(f2)
##    return fibs
##
##fibs = gen_fibs(10)
##print(fibs)