递归和信用卡的Luhn算法

这里用python做一个mutual recursion

 

def split(n):
    return n//10, n%10

def luhn_sum(n):
    if n<10:
        return n
    else:
        rest, last = split(n)
        return luhn_double_sum(rest) + last

def luhn_double_sum(n):
    rest, last = split(n)
    luhn_digit = split(2*last)[0] + split(2*last)[1]
    if n<10:
        return luhn_digit
    else:
        rest, last = split(n)
        return luhn_sum(rest) + luhn_digit

 

Newton's Method

寻找函数零点:Quickly finds accurate approximations to zeros of differenciable functions.

只要问题是可微的,则问题是可解的。

Wikipedia上操作演示

https://en.wikipedia.org/wiki/Newton's_method#/media/File:NewtonIteration_Ani.gif

 

实现指南:

高阶函数为的是抽象出功能,不要被参数混乱思路

python中整数相除会返回整数,所以注意传入浮点数做参数

 

def square_root(a):
    def f(x):
        return x * x - a

    def df(x):
        return 2 * x

    return find_zero(f, df)

def find_zero(f, df):
    def near_zero(x):
        return appro_equal(f(x), 0)
    return improve(update(f, df), near_zero, guess=1.0, max_update=100)

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

def improve(update, close, guess, max_update):
    k = 0
    while not close(guess) and k < max_update:
        print guess, k
        guess = update(guess)
        k += 1
    return guess  # the guess improved

def appro_equal(x, y, tolerance=1e-15):
    print abs(x-y) < tolerance
    return abs(x-y) < tolerance

 

推广至求n次根

>>> def power(x, n):
        """Return x * x * x * ... * x for x repeated n times."""
        product, k = 1, 0
        while k < n:
            product, k = product * x, k + 1
        return product
>>> def nth_root_of_a(n, a):
        def f(x):
            return power(x, n) - a
        def df(x):
            return n * power(x, n-1)
        return find_zero(f, df)

 

实际应用 Function Decorator

 

def trace(fn):
    def t(x):
        print "Calling", fn, "on argument", x
        return fn(x)
    return t

@trace
def square(x):
    return x * x

Higher-Order Functions in Python

学习资料:

http://composingprograms.com/pages/16-higher-order-functions.html

定义:

Higher-Order functions can accept other functions as arguments or return functions as values.

例一:计算黄金比例

 

def improve(update, close, guess=1):
    while not close(guess):
        guess = update(guess)
    return guess

def golden_update(guess):
    return 1/guess + 1

def square_close_to_successor(guess):
    return approx_eq(guess * guess,
                     guess + 1)

def approx_eq(x, y, tolerance=1e-3):
    return abs(x - y) < tolerance

phi = improve(golden_update,
              square_close_to_successor)

 

Two key advantages of lexical scoping in Python.

  • 函数命名只与定义环境有关,与执行环境无关
    The names of a local function do not interfere with names external to the function in which it is defined, because the local function name will be bound in the current local environment in which it was defined, rather than the global environment.

     
  • 执行函数由内向外延展
    A local function can access the environment of the enclosing function, because the body of the local function is evaluated in an environment that extends the evaluation environment in which it was defined. 

例二:

def average(x, y):
    return (x + y)/2

def improve(update, close, guess=1):
    while not close(guess):
        guess = update(guess)
    return guess

def approx_eq(x, y, tolerance=1e-3):
    return abs(x - y) < tolerance

def sqrt(a):
    def sqrt_update(x):
        return average(x, a/x)
    def sqrt_close(x):
        return approx_eq(x * x, a)
    return improve(sqrt_update, sqrt_close)

result = sqrt(256)

 

函数计算时层层隔离,名字重复无影响。但是对于大工程来说,明明冲突可能给自己带来麻烦,比如需要重命名的时候。

 

def square(x):
    return x * x

def successor(x):
    return x + 1

def compose1(f, g):
    def h(x):
        return f(g(x))
    return h

def f(x):
    """Never called."""
    return -x

square_successor = compose1(square, successor)
result = square_successor(12)

 

use Processing to run a program on android device

S1 make Arch 64 compatible with lib32: install lib32-* from [multilib]

# vim /etc/pacman.conf

    => [multilib]

    SigLevel = PackageRequired

    Include = /etc/pacman.d/mirrorlist

# pacman -Syu ---- update multilib to local database

 

S2 install android_sdk

# pacman -S android-sdk android-sdk-platform-tools android-sdk-build-tools

[Alt + F2] android ---- run Android SDK Manager

    => makesure the following:

     Underneath “Tools”, check the box for “Android SDK Platform-tools”. (The “Android SDK Tools” item will already be installed.)
     Beneath “Android 2.3.3 (API 10)”, select “SDK Platform”. (As of Processing 2.0b7, you no longer need to include the “Google APIs” item.)


S3 lauch Processing and add ''Android Mode'' to Processing

    If there is a warning about missing ANDROID_SDK variable,
   choose 'yes' (installed sdk) and choose the directory '' / → opt → android_sdk ''

 

S4 write the simple program and run it on ur phone

        void setup(){}
        
void draw(){  background(0);  rect(mouseX, mouseY, 100, 100);  }