【问题描述】 编写程序，以字符串的形式输入前缀表达式，然后计算其值。输入格式为：计算符 对象1 对象2 *(乘法)或/(除法)，计算对象为不超过10的整数，用空间隔开。要求:设计相应的函数来实现加、减、乘、除四种操作。 输入格式：输入只有一行，即前缀表达字符串。 输出格式:输出相应的计算结果(如果是除法，直接使用C语言的/运算符，结果为整数)。 样例输入 5 2 【样例输出】 7

一开始我以为前缀表达式字符串很长，要算值，后来发现输入三个对象就行了。 注意，使用‘/’号时，结果应返回到整数

S = list(input().split()) print(int(eval(S[1]   S[0]   S[2]))) 

【问题描述】 任何正整数都可以用2进制表示，比如137的2进制表示10001001。 将这种2进制表示写成2次幂和的形式，使次幂高排在前面，可以得到以下表达式:137=2^{7 2}3 2^0 现在约定用括号表示权力次用，即a^b表示为a（b） 此时，137可以表示为:2(7) 2（3） 2（0） 进一步：7=2^{2 2 2}0 （2^1用2表示） 3=2 2^0 所以最后137可以说是:2(2(2) 2 2（0）） 2（2 2（0）） 2（0） 又如：1315=2^{10 2}8 2^5 2 1 因此，1315最终可以表示为： 2（2（2 2（0）） 2） 2（2（2 2（0））） 2（2（2） 2（0）） 2 2（0） 输入格式 正整数（1<=n<=20000） 输出格式 n符合约定的0，2表示(表示中不能有空格) 样例输入 137 样例输出 2(2(2) 2 2(0)) 2(2 2(0)) 2(0) 样例输入 1315 样例输出 2(2(2 2(0)) 2) 2(2(2 2(0))) 2(2(2) 2(0)) 2 2(0)

def show(num):     if num == 1:         print('2', end='')     else:         print(f'2({ 
          num})', end='')


def fun(arr, m):
    # 先给出m的二进制（在这里我没用python自带函数）
    bin_arr = []
    while m:
        bin_arr.insert(0, m % 2)
        m //= 2
    bin_arr.reverse()

    # 根据二进制数组获得次幂数数组
    for i in range(len(bin_arr)):
        if bin_arr[i] == 1:
            arr.append(i)
    arr.reverse()

    # 遍历次幂数数组
    for i in range(len(arr)):
        if i != 0:
            print('+', end='')
        if arr[i] <= 2:
            # 如果小于等于2，则输出
            show(arr[i])
        else:
            # 否则递归，外面需要套上2()
            print('2(', end='')
            fun([], arr[i])
            print(')', end='')

if __name__ == '__main__':
    n = int(input())
    fun([], n)

【问题描述】 　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。 　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法） 【输入格式】 　　两个整数，表示m和n 【输出格式】 　　一个整数，表示队伍的排法的方案数。 【样例输入】 　　3 2 【样例输出】 　　5

之前一直没懂这题说的什么，后来是看了大佬的博客才了解这道题的解法，采用递归的思想 传送门：算法训练 未名湖边的烦恼_@Star的博客 python版代码如下：

def fun(m, n):
    # 如果还鞋的人 < 租鞋的人，说明无鞋可租，不能这样排
    if m < n:
        return 0
    # 当没人租鞋的时候，也可以算是一种方法
    if n == 0:
        return 1
    # '还鞋的人在后面，租鞋的人在前面' 或 '租鞋的人在后面，还鞋的人在前面' 都可以接着排序
    return fun(m - 1, n) + fun(m, n - 1)


if __name__ == '__main__':
    # m:还鞋 n:租鞋
    m, n = list(map(int, input().split()))
    print(fun(m, n))

【问题描述】 【样例输入】 　　3 10 【样例输出】 　　120

def fun(k, n):
    if k == 0 or k == n:
        return 1
    return fun(k, n - 1) + fun(k - 1, n - 1)


if __name__ == '__main__':
    k, n = list(map(int, input().split()))
    print(fun(k, n))

【问题描述】 　　输出一个n行的与样例类似的数字三角形,必须使用递归来实现 【输入格式】 　　一个正整数数n，表示三角形的行数 【输出格式】 　　输出一个与样例类似的n行的数字三角形，同一行每两个数之间用一个空格隔开即可(图中只是为防止题面格式化而用’_'代替空格） 【样例输入】 　　4 【样例输出】 　　___1 　　__2_3 　　_4_5_6 　　7_8_9_10

def show(arr):
    # 判断前面打印多少个空格
    print(' ' * abs(len(arr) - n), end='')
    for i in arr:
        print(i,end=' ')
    print('')
 
 
def fun(start, step):
    # 如果步数为n+1，则返回，步数为n时，还得继续递归
    if step == n + 1:
        return
    # 输出这段数组的内容
    show(arr[start:start + step])
    # 起点为start + step，步数为step + 1
    fun(start + step, step + 1)
 
 
if __name__ == '__main__':
    n = int(input())
    # 初始化数组，从1开始
    arr = [i + 1 for i in range(int((1 + n) * n / 2))]
    # 起点为0，步数为1
    fun(0, 1)

【问题描述】 　　编写一个程序，输入一个4位的正整数，将组成该数的各位数字重新排列，形成一个最大数和一个最小数，之后用最大数减去最小数，得到一个新的正整数（该数一定大于1000）。然后对于这个新的正整数，重复上述步骤，直到该正整数的值不再发生变化。 　　例如，假设用户输入的正整数为1001，那么由它所形成的最大数为1100，最小数为11，因此新的正整数为1089。对于1089，由它形成的最大数为9810，最小数为189，因此新的正整数为9621。9621的最大数为9621，最小数为1269，结果为8352,。8352的最大数为8532，最小数为2358，结果为6174。6174的最大数为7641，最小数为1467，结果仍为6174，因此程序结束。（注：出自课本第六章第22题） 【样例输入】 　　1001 【样例输出】 　　6174

n = input()
temp = int(n)
# 如果n不等于temp，则循环一直继续
while n != temp:
    temp = n  # 用来判断n的值是否改变
    # 先将数组转为字符串，再转换成数组，再升序排列，再转换成字符串
    max_num = ''.join(sorted(list(str(n)), reverse=True))
    # 先将数组转为字符串，再转换成数组，再降序排列，再转换成字符串
    min_num = ''.join(sorted(list(str(n)), reverse=False))
    # 相减时需要转换成int类型
    n = int(max_num) - int(min_num)
print(n)

【问题描述】 　　我们要求找出具有下列性质数的个数(包含输入的自然数n): 　　先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理: 　　1. 不作任何处理; 　　2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 　　3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 【输入格式】 　　一个数n 【输出格式】 　　一个数表示答案 【样例输入】 　　6 【样例输出】 　　6 【样例说明】 　　满足条件的数为6,16,26,126,36,136

刚开始还每个都打印输出，后来发现只要计数就行了

def fun(m):
    global count
    if m == 1:
        return
    count += int(m / 2)  # 数的一半有多少个 就有多少种
    # 遍历数的一半，递归执行函数
    for i in range(1, int(m / 2) + 1):
        fun(i)


if __name__ == '__main__':
    n = int(input())
    count = 1  # 数本身也是一种
    fun(n)
    print(count)

【问题描述】 　　接收用户输入的自然数m，n，计算它们的最小公倍数。 【样例输入】 　　4 6 【样例输出】 　　12

这里记录一下最大公约数和最小公倍数的求法，做十次，十次都不记得过程。。

# 最大公约数greatest common divisor
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a % b)


# 最小公倍数least common multiple
def lcm(a, b):
    remainder = gcd(a, b)
    print(int(a * b / remainder))


if __name__ == '__main__':
    m, n = input().split()
    lcm(int(m), int(n))

【问题描述】 　　求出区间[a,b]中所有整数的质因数分解。 【输入格式】 　　输入两个整数a，b。 【输出格式】 　　每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例) 【样例输入】 　　3 10 【样例输出】 　　3=3 　　4=22 　　5=5 　　6=23 　　7=7 　　8=222 　　9=33 　　10=25

还有一题也是质因数的，可以一起做

# 获取一个数的质因数
def get_list(n):
    i = 2
    arr = []
    while i <= n:
        if n % i == 0:
            arr.append(f'{ 
          i}')  # 因为想用join()函数，所以数组里面存放的是字符串类型
            n /= i
        else:
            i += 1
    return arr


if __name__ == '__main__':
    a, b = input().split()
    for i in range(int(a), int(b) + 1):
        print(f'{ 
          i}=', end='')
        print('*'.join(get_list(i)))

【问题描述】 　　已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。 　　现给出一个整数 K，要求计算出一个最小的n；使得Sn＞K。 【输入格式】 　　一个整数，表示整数 k 【输出格式】 　　一个整数，表示最小的n 【样例输入】 　　1 【样例输出】 　　2

k = int(input())
Sn = 0
n = 1
while True:
    Sn += (1 / n)
    if Sn > k:
        break
    n += 1
print(n)

【问题描述】 　　给一个正整数n，输出它所有的正整数加法的分解方法。 　　注意： 　　1． 根据输入的要求决定交换加数的位置是否视为不同的分解方案。 　　2． 不分解也视为一种分解方案。 　　3． 按字典序输出所有分解方案，格式见样例。 【输入格式】 　　输入共1行，包含2个正整数n和m，之间用一个空格隔开。n表示待分解正整数，m是1或者2： 　　1表示交换加数的位置是否视为不同的分解方案； 　　2表示交换加数的位置是否视为相同的分解方案。 【输出格式】 　　输出若干行，每行表示一种分解方案。对于一种方案，先输出n，再输出一个“=”。然后输出分解的各数，不同的数之间用一个“+”连接。 【样例输入】 　　5 2 【样例输出】 　　5=1+1+1+1+1 　　5=1+1+1+2 　　5=1+1+3 　　5=1+2+2 　　5=1+4 　　5=2+3 　　5=5 【样例输入】 　　5 1 【样例输出】 　　5=1+1+1+1+1 　　5=1+1+1+2 　　5=1+1+2+1 　　5=1+1+3 　　5=1+2+1+1 　　5=1+2+2 　　5=1+3+1 　　5=1+4 　　5=2+1+1+1 　　5=2+1+2 　　5=2+2+1 　　5=2+3 　　5=3+1+1 　　5=3+2 　　5=4+1 　　5=5

def show(arr):
    # 输出第一个值
    print(f'{ 
          n}={ 
          arr[0]}', end='')
    # 之后每个值输出前都加上'+'号
    for i in arr[1:]:
        print(f'+{ 
          i}', end='')
    print('')


def dfs(first_num, end, count):
    ''' :param first_num: 第一个数从多少开始 :param end: 数组最后一个索引 :param count: 累计和 :return: '''
    # 和大于输入的n，则返回
    if count > n:
        return
    # 和等于输入的n，则输出
    if count == n:
        show(arr[:end])
        return
    # 和小于输入的n，则继续下面的步骤
    # 判断m为1还是2，差别在于从几开始循环，一个从1开始，一个从first_num开始
    if m == 1:
        for i in range(1, n + 1):
            arr[end] = i  # 数组索引的最后一个数为i
            # 递归，从i开始，end往后移一位，累计和加上当前i
            dfs(i, end + 1, count + i)
    elif m == 2:
        for i in range(first_num, n + 1):
            arr[end] = i
            dfs(i, end + 1, count + i)

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    arr = [0 for _ in range(n)]
    dfs(1, 0, 0)

【问题描述】 　　给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。 【输入格式】 　　两行，每行一个字符串，分别表示中序和后序排列 【输出格式】 　　一个字符串，表示所求先序排列 【样例输入】 　　BADC 　　BDCA 【样例输出】 　　ABCD

解析见 ALGO-705-根据前、中序遍历求后序遍历

def fun(LDR, LRD):
    if LDR == LRD and len(LDR) < 1:
        print(LDR, end='')
        return
    D = LRD[-1]
    print(D, end='')

    L = LDR.split(D)[0]
    fun(L, LRD[:len(L)])

    R = LDR.split(D)[1]
    fun(R, LRD[len(L):-1])


if __name__ == '__main__':
    LDR = input()  # 中序遍历序列
    LRD = input()  # 后序遍历序列
    fun(LDR, LRD)

【问题描述】 　　给定一棵二叉树的前序遍历和中序遍历序列，用你所熟悉的程序设计语言生成该二叉树，并将其后序遍历打印出来。为便于编程，二叉树的结点用单个大写英文字母表示，且结点互不重复。比如，输入前序遍历序列为DBACPMZX，中序遍历序列为ABCDMPXA，应生成的二叉树结构如下图所示： 　　应输出的后序遍历序列为ACBMXZPD 【输入格式】 　　两行两个大写字母字符串，分别代表前序和中序遍历 【输入格式】 　　一行表示后序遍历 【样例输入】 　　DBACPMZX 　　ABCDMPXZ 【样例输出】 　　ACBMXZPD

前提知识： 先序遍历序列：根左右 中序遍历序列：左根右 后序遍历序列：左右根

题目： 先序遍历序列：D BACPMZX 中序遍历序列：ABC D MPXZ 这题想到用递归，递归出口就是先序遍历序列等于中序遍历序列的时候，说明只有一个字符 我们根据先序遍历序列获取根结点：D 根据 ‘中序遍历序列：左根右’ 的知识，我们可以知道用根结点分割中序遍历序列时，分割成两个部分，第一个部分是左子树，第二部分是右子树 [‘ABC’, ‘D’, ‘MPXZ’] ==> 左子树：‘ABC’ 右子树：‘MPXZ’ 然后开始递归，这里递归的顺序是，先递归左子树，再递归右子树

1、先递归左子树 获取左子树的先序遍历序列和中序遍历序列，递归fun函数 - 先序遍历序列：DLR[1:len(L) + 1] （第一个是根结点，因此从1开始，直到左子树的长度+1，作为左子树的先序遍历序列） - 中序遍历序列：L （左子树是从中序遍历序列中获得的，作为左子树的中序遍历序列）

2、再递归右子树 获取右子树的先序遍历序列和中序遍历序列，递归fun函数 - 先序遍历序列：DLR[len(L) + 1:] （从左子树的长度+1开始直到结尾，作为右子树的先序遍历序列） - 中序遍历序列：R （右子树是从中序遍历序列中获得的，作为右子树的中序遍历序列）

3、最后输出根结点 根结点就是先序遍历序列的第一个值，即DLR[0]

def fun(DLR, LDR):
    # 如果先序遍历序列 == 中序遍历序列，且只有一个字符，可以直接输出
    if DLR == LDR and len(LDR) < 1:
        print(DLR, end='')
        return
    D = DLR[0]  # 获取根结点

    # 1、先递归左子树
    # 根据根结点进行分割中序遍历序列，第0个是左子树
    L = LDR.split(D)[0]
    # 递归：先序遍历序列为DLR[1:len(L) + 1]，后序遍历序列为L
    fun(DLR[1:len(L) + 1], L)

    # 2、再递归右子树
    # 根据根结点进行分割中序遍历序列，第1个是右子树
    R = LDR.split(D)[1]
    # 递归：先序遍历序列为DLR[len(L) + 1:]，后序遍历序列为R
    fun(DLR[len(L) + 1:], R)

    # 3、最后输出根结点
    print(D, end='')  # 输出根结点，因为后序遍历序列是左右根，根结点在最后


if __name__ == '__main__':
    DLR = input()  # 先序遍历序列
    LDR = input()  # 中序遍历序列
    fun(DLR, LDR)

【问题描述】 　　王神想要知道n的所有排列的逆序对数和，但是他觉得太水了，于是让你算。 【输入格式】 　　一行一个整数n 【输出格式】 　　一行即答案，对1007取模 【样例输入】 　　2 【样例输出】 　　1

刚开始看这道题又没看懂（我理解能力是真的差），后来搜了一下看到了这篇博客下的博主评论，才知道要先求全排列，再求逆序数 传送门：试题 算法训练 序列_@醉尘归的博客 这道题就转变成如下两步： 1、求一个数的全排列 2、求全排列的逆序数 全排列b站讲解：【python】递归与回溯-全排列（第二讲）_@八月里的小太阳 逆序数b站讲解：【XDOJ】1052:经典逆序对问题【Python基础系列习题学习教程】_@散装未央 python代码如下：