Python3函数之例子

1.分别使用递归、循环和生成器求菲波那切数列 递归： def fib_rec(n): if n == 0: return 1 if n == 1: retur

1.分别使用递归、循环和生成器求菲波那切数列

  递归：

def fib_rec(n):    if n == 0:        return 1    if n == 1:        return 1    return fib_rec(n-1) + fib_rec(n-2)fib_rec(5)

  循环：

def fib_loop(n):    lst = []    for i in range(n+1):        if i == 0 or i == 1:            lst.append(1)        else:            lst.append(lst[-1] + lst[-2])    return lst.pop()fib_loop(5)

def fib_loop2(n):    a, b = 1, 1    for i in range(n+1):        if i == 0 or i == 1:            a, b = 1, 1        else:            a, b = b, a+b    return bfib_loop2(5)

  生成器：

def fib_gen():    i = 0    a, b = 1, 1    while True:        if i == 0 or i == 1:            yield 1        else:            a, b = b, a+b            yield b        i += 1def fib(n):    gen = fib_gen()    for _ in range(n):        next(gen)    return next(gen)fib(5)

2.写一个函数，实现对整数的排序，默认升序排序，不能使用任何内置函数和第三方库

  fun1：

def sort_int(lst, asc=True):    sort_lst = []    while lst:        i = None        min_int = None        for i in lst:            if min_int is None:                min_int = i            else:                if min_int > i:                    min_int = i        lst.remove(min_int)        if asc:            sort_lst.append(min_int)        else:            sort_lst.insert(0, min_int)    return sort_lst

  fun2：

def sort(lst, reverse=False):    dst = []    for n in lst:        for i, e in enumerate(dst):            if not reverse:                if n < e:                    dst.insert(i, n)                    break            else:                if n > e:                    dst.insert(i, n)                    break        else:            dst.append(n)    return dst

3.写一个函数，把整数转化为罗马数字，输入为1到3999之间的任意数字

def int2rom(n):    if n < 1 or n > 3999:        print('input error.')        return 0    rom_lst = [' ',               'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX',                'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC',               'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM',               'M', 'MM', 'MMM']    rom = ''    bit = n % 10    ten = (n % 100) // 10    hun = (n % 1000) // 100    tho = n // 1000    if tho != 0:        rom += rom_lst[27 + tho]    if hun != 0:        rom += rom_lst[18 + hun]    if ten > 0:        rom += rom_lst[9 + ten]    if bit > 0:        rom += rom_lst[bit]    return rom

3.2写一个函数，把整数转化为罗马数字，输出为1到3999之间的任意数字

def roman2int(src):    convert_map = {        'I':1,        'V':5,        'X':10,        'L':50,        'C':100,        'D':500,        'M':1000    }    # MDCCCXCIX    # XICXCCCDM    # +10 -1 +100 -10 +100 +100 +100 +500 +1000    # 1899    roman = src.upper()[::-1]    prev = 0    lst = []    for x in roman:        i = convert_map[x]        if i < prev:            lst.append(-1 * i)        else:            lst.append(i)        prev = i    return sum(lst)roman2int('MDCCCXCIX')

4.写一个函数，求两个字符串的最长公共子串

  例如输入：I love Python 和 Python is a simple language，输出为Python

def psubstring_long(x, y):    f = []    max_len = 0    idx = 0    for i, a in enumerate(x):        f.append([])        for j, b in enumerate(y):            if a != b:                f[i].append(0)            else:                if i == 0 or j == 0:                    f[i].append(1)                else:                    f[i].append(f[i-1][j-1] + 1)                if max_len < f[i][j]:                    max_len = f[i][j]                    # idx = max_len - (i+1)                    idx = i + 1 - max_len    return x[idx: idx + max_len]psubstring_long('babcdf', 'xxaabcaac')

5.动态规划

  总长n，step表示一次可选步数，总共多少种走法

ret = 0tmp = []solution = []def recursion(n, tmp, step=3):    global ret    if n == 0:        solution.append('===')        solution.extend(tmp)        ret += 1        return 0    for i in range(1, step+1):        if n > i-1:            tmp.append(i)            recursion(n-i, tmp, step)            tmp.pop(-1)    return retprint(recursion(3, [], 3), solution)4 ['===', 1, 1, 1, '===', 1, 2, '===', 2, 1, '===', 3]