##### 检查一个整数是否完全平方
##
def check_square(n):
    m = 0
    while m * m < n:
        m += 1
    if m * m == n:
        return True
    return False


##### 生成并输出 1 到 200 中的完全平方数
##
##for k in range(1, 201):
##    if check_square(k):
##        print(k)


### squares in [1, 200], method 2
##k = 1
##while k * k <= 200:
##    print(k * k)
##    k += 1


### squares in [1, 200], method 3
##n = 1
##s = 1  # 这是 1 的平方
##while s <= 200:
##    s += 2 * n + 1
##    n += 1


#### 检查素数的函数（谓词）
##
##def is_prime(n):
##    if n < 2:
##        return False
##    k = 2
##    while k * k <= n:
##        if n % k == 0:
##            return False
##        k += 1
##    return True
##
##
##for n in range(10, 30):
##    if is_prime(n):
##        print(n, "is prime.")


#### 两个求幂的递归函数
##def power(x, n):
##    if n == 0:
##        return 1
##    else:
##        return x * power(x, n - 1)


#### 另一个求幂函数
##def power(x, n):
##    if n == 0:
##        return 1
##    elif n % 2 == 0:
##        return power(x * x, n // 2)
##    else:
##        return x * power(x, n - 1)


#### 斐波那契数列的计算

##### 直接根据数学定义写的递归函数
##def fib(n):
##    if n < 1:
##        return 0
##    if n == 1:
##        return 1
##    return fib(n - 1) + fib(n - 2)



###### 计算斐波那契数，并计时
from time import time
def test_fib(n):
    t = time()
    f = fib(n)
    print("Fib[" + str(n) + "] =", f)
    print("Timing:", str(time() - t) + "s\n")

    
##test_fib(28)
##test_fib(29)
##test_fib(30)


from time import time
def test_fibs(m, n):
    for k in range(m, n):
        t = time()
        f = fib(k)
        print("Fib[" + str(k) + "] =", f,
              "Timing:", str(time() - t) + "s")


#### 按递推方式写出的循环程序
        
##def fib(n):
##    if n <= 0:
##        return 0
##    f1, f2 = 0, 1 # F_0, F_1
##    k = 0
##    while k < n:
##        f1, f2 = f2, f2 + f1
##        k += 1
##    return f1   


#### 简化的循环程序
#### 实际上，n 是 0 的情况已经蕴含在下面循环中
#### 由于可以确定循环次数，用 for 循环更简单
##
##def fib(n):
##    f1, f2 = 0, 1
##    for k in range(0, n):
##        f1, f2 = f2, f2 + f1
##    return f1


###### 递归定义的函数，采用高效的递推计算方法
##def fib0(f1, f2, k, n):
##    return f1 if k > n else fib0(f2, f1 + f2, k + 1, n)
##
##def fib(n):
##    return fib0(0, 1, 1, n)


#### 求最大公约数问题

#### 采用顺序枚举与检查方法的函数
#### 这里假定 m >= 0, n > 0
##def gcd (m, n):
##    if m == 0:
##        return n
##    i = 1
##    d = 1
##    k = min(m, n)
##    while i <= k:
##        if m % i == 0 and n % i == 0:
##            d = i
##        i += 1
##    return d


#### 从大到小顺序枚举与检查方法的函数
#### 这里假定 m >= 0, n > 0
##def gcd(m, n):
##    if m == 0:
##        return n
##    k = min(m, n)
##    while k > 1:
##        if m % k == 0 and n % k == 0:
##            break
##        k -= 1
##    return k


#### 求最大公约数，按辗转相除法递归定义的函数
#### 假定 m >= 0, n > 0
def gcd(m, n):
    if m % n == 0:
        return n
    return gcd(n, m % n)


#### 处理所有整数的不同情况，包括负值、0
#### 如果两个数都为 0，本函数简单返回 0 指明特殊情况
def gcd1(m, n):
    assert type(m) == int, type(n) == int
    if m < 0:
        m = -m
    if n < 0:
        n = -n
    if n == 0:
        return m
    return gcd(m, n)


#### 求兑换硬币的不同方式，递归定义的函数
#### 用 k 种硬币兑换 n 的不同方式等于
#### 用硬币 a 一次后兑换 n-a 的不同方式加不同 a 兑换 n 的方式
####
#### 函数 amount 将硬币类 1 到 6 对应到具体币值
def amount(k):
    if k == 1:
        return 1
    if k == 2:
        return 2
    if k == 3:
        return 5
    if k == 4:
        return 10
    if k == 5:
        return 50
    if k == 6:
        return 100
    assert False

#### 核心函数 ccoins 用递归地计算不同兑换方式
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)

#### 主函数 get_coins 对具体的 n 值启动计算
def get_coins(n):
    return ccoins(6, n)

##for m in range(11, 21):
##    print(get_coins(m), "different ways for amount", m)


#### 相互递归定义的函数示例

##def even(n):
##    if n == 0:
##        return True
##    else:
##        return odd(n-1)
##
###even(4) # will be an error
##
##def odd(n):
##    if n == 0:
##        return False
##    else:
##        return even(n-1)