python | Python practice

素数（质数）问题

获得指定范围内的所有素数（埃拉托斯特尼筛法）

使用 filte() + 生成器


class Myclass():
    def __init__(self):
        self.res = []

    @staticmethod
    def _odd_iter():
        '''
            生成一个从3开始的奇数序列(因为偶数除了2以外不可能是素数，所以只考虑奇数)
        '''
        n = 1
        while n < 1050:
            n = n + 2
            yield n

    @staticmethod
    def _not_divisible(n):
        '''
            检查 X 是否能被 n 整除
        '''
        return lambda x: x % n > 0  


    def primes(self):
        '''
            生成器函数，用于生成素数序列
        '''
        yield 2
        it = self._odd_iter() # 初始序列，获取生成器对象
        while True:
            n = next(it) # 返回序列的第一个数
            yield n
            it = filter(self._not_divisible(n), it) # 构造新序列

    def get_nums(self, n):
        # 打印1000以内的素数:
        for f in self.primes():
            if f < n:
                self.res.append(f)
            else:
                break

temp = Myclass()
temp.get_nums(1000)
print(temp.res)

厄拉多塞筛法

判断指定的数是否是素数

线程同步输出

创建两个线程，其中一个输出1-52，另外一个输出A-Z。


#	输出格式要求：
#	12A
#	34B
#	56C
#	...
#	5152Z

# 使用互斥锁


# 使用事件管理

斐波那契数列

计算斐波那契数列的第 n 项

普通递归版本：


def fib(n):
    match n:
        case x if x <= 1:
            return x
        case _:    
            return fib(n-1)+fib(n-2)


def fib(n):
    return n if n <= 1 else fib(n-1)+fib(n-2)

斐波那契数列的动态规划版本：


def fibonacci(n):
    dp = [0, 1] + [0] * (n - 1)# 初始化数组，存储斐波那契数列的值
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]# 状态转移方程
    return dp[n]

# 调用函数计算斐波那契数列的第 n 项
result = fibonacci(10)
print(result)# 输出: 55

状态压缩版本：


def fibonacci_compressed(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b# 只保存必要的两个状态，而不是整个序列return b

# 调用函数计算斐波那契数列的第 n 项
compressed_result = fibonacci_compressed(10)
print(compressed_result)# 输出: 55

输出斐波那契数列的前 n 项

汉诺塔问题

杨辉三角


杨辉三角定义如下：

          1
         / \
        1   1
       / \ / \
      1   2   1
     / \ / \ / \
    1   3   3   1
   / \ / \ / \ / \
  1   4   6   4   1
 / \ / \ / \ / \ / \
1   5   10  10  5   1

把每一行看做一个list

输出杨辉三角第 n 行的元素组成的列表

普通递归：


def triangles(n):
    if n == 1:
        return [1]
    L = [0] + triangles(n-1) + [0]
    L = [L[f]+L[f+1] for f in range(len(L)-1)]
    return L

动态规划：


def triangles(n):
    if n == 1:
        return [1]
    res = [[1]]
    for _ in range(1, n):
        L = [0] + res[_-1] + [0]
        L = [L[f]+L[f+1] for f in range(len(L)-1)]
        res.append(L)
    return res[n-1]

状态压缩


def triangles3(n):
    if n == 1:
        return [1]
    row = [1]
    for _ in range(1, n):
        row = [x + y for x, y in zip([0]+row, row+[0])]
    return row

输出杨辉三角的第一行到第 n 行


import time

from functools import reduce

def calculate_runtime(func, n, res=False):
    '''
        计算函数的运行时间（/s）
    '''
    start = time.perf_counter()
    result = func(n)
    end = time.perf_counter()
    if not res:
        print(f'{func.__name__}\t运行时间（/s）：{end-start}')
    else:
        print(f'{func.__name__}\n运行结果:{result}\n运行时间（/s）：{end-start}')


class Calculate_fib_specified_location_element():
    @staticmethod
    def fib_ordinary_func(n):
        '''
            使用迭代的方式计算斐波那契数列指定位置的元素
        '''
        if n <= 1:
            return n
        a, b = 1, 1
        for _ in range(2, n):
            a, b = b, a+b
        return b

    @staticmethod
    def fib_recursion_ordinary(n):
        '''
            使用普通递归计算斐波那契数列指定位置的元素
        '''
        return n if n<=1 else Calculate_fib_specified_location_element.fib_recursion_ordinary(n-1)+Calculate_fib_specified_location_element.fib_recursion_ordinary(n-2)


    @staticmethod
    def fib_recursion_dynamic_programming(n):
        '''
            使用动态规划计算斐波那契数量指定位置的元素
        '''
        dp = [0, 1] + [0] * (n - 1)# 初始化数组，存储斐波那契数列的值
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]# 状态转移方程
        return dp[n]

class Calculate_fib_specified_length_list():
    '''
        计算指定长度的斐波那契数列
    '''
    @staticmethod
    def fib_func1(n):
        if n == 1:
            return [0]
        res = [0, 1]
        a, b = res
        for _ in range(2, n):
            a, b = b, a+b
            res.append(b)
        return res

    @staticmethod
    def fib_func2(n):
        if n == 1:
            return [0]
        res = [0]+[1]*(n-1)
        for i in range(2, n):
            res[i] = res[i-1]+res[i-2]
        return res


class Calculate_YangHui_triangle():
    def get_triangles1(n):
        '''
            计算杨辉三角的前n行
        '''
        if n == 1:
            return [1]
        res = [[1]]
        row = [1]
        for _ in range(1, n):
            row = [x + y for x, y in zip([0]+row, row+[0])]
            res.append(row)
        return res
            
    def get_triangles2(n):
        '''
            计算杨辉三角的前n行
        '''
        if n == 1:
            return [1]
        res = [[1]]
        for _ in range(1, n):
            L = [0] + res[_-1] + [0]
            L = [L[f]+L[f+1] for f in range(len(L)-1)]
            res.append(L)
        return res


def str2int(s):
    '''
        将字符串转化整数
    '''
    d = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
    def char2num(n):
        return d[n]

    def get_int(x, y):
        return x*10 + y

    return reduce(lambda x,y:x*10+y, map(lambda n:d[n], s))

def str2float(s):
    '''
        将字符串转化为浮点数
    '''
    d = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
    integer_part, decimal_part = s.split('.')
    integer = reduce(lambda x,y:10*x+y, map(lambda n:d[n], integer_part))
    decimal = reduce(lambda x,y:10*x+y, map(lambda n:d[n], decimal_part))/10**len(decimal_part)
    return integer+decimal


def filter_list_of_even_numbers(sequence):
    '''
        筛选得到序列对象中的偶数列表和奇数列表
    '''
    even_nums = list(filter(lambda x:x%2==0, sequence))
    odd_nums = list(filter(lambda x:x%2!=0, sequence))
    return even_nums, odd_nums

def get_prime_number(n):
    '''
        获得指定范围内的素数列表
    '''
    if n < 2:
        return []
    res = [True] * (n+1)
    res[0], res[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if res[i]:
            res[i*i:n+1:i] = [False] * len(res[i*i:n+1:i])
    return [i for i,value in enumerate(res) if value]

class Myclass():
    def __init__(self):
        self.res = []

    @staticmethod
    def _odd_iter():
        '''
            生成一个从3开始的奇数序列(因为偶数除了2以外不可能是素数，所以只考虑奇数)
        '''
        n = 1
        while n < 1050:
            n = n + 2
            yield n

    @staticmethod
    def _not_divisible(n):
        '''
            检查 X 是否能被 n 整除
        '''
        return lambda x: x % n > 0  


    def primes(self):
        '''
            生成器函数，用于生成素数序列
        '''
        yield 2
        it = self._odd_iter() # 初始序列，获取生成器对象
        while True:
            n = next(it) # 返回序列的第一个数
            yield n
            it = filter(self._not_divisible(n), it) # 构造新序列

    def get_nums(self, n):
        # 打印1000以内的素数:
        for f in self.primes():
            if f < n:
                self.res.append(f)
            else:
                break