约瑟夫环问题 - 详解及 Python 实现 - 常规

约瑟夫环问题是一个经典的算法问题，描述的是：有 n 个人编号为 1~n，排成一个环，从 1 号人开始从 1 到 m 报数，报到 m 的人离开该环，从下一个人开始继续从 1 到 m 报数，报到 m 的人离开该环，...，这样一直进行下去，直到最终剩余 p 个人。

从键盘输入 n、m、p，要求 n>=2、m>=2、1<=p<n，输出最终剩余的 p 个初始编号。例如：输入 n、m、p 依此为,4、3、2，则输出为 1 和 4。

约瑟夫环问题的解决思路如下：

创建一个长度为 n 的列表，用来表示 n 个人的状态，初始状态都为 1，表示这些人还在环中。
从 1 号人开始，依次报数，每报到 m 的人将其状态设置为 0，表示离开了环。
继续从下一个人开始报数，重复步骤 2，直到剩余人数等于 p。
输出状态为 1 的人的初始编号。

以下是一个 Python 的实现代码：

def josephus(n, m, p):
    people = [1] * n  # 初始状态都为 1，表示人还在环中
    count = 0  # 记录已离开环的人数
    index = 0  # 当前报数的人的索引

    while count < n - p:  # 当剩余人数等于 p 时结束循环
        num = 0  # 记录当前人已报数的次数

        while num < m:  # 报数
            if people[index] == 1:  # 如果当前人还在环中
                num += 1  # 报数次数加 1

            if num == m:  # 如果报数次数等于 m
                people[index] = 0  # 将当前人状态设置为 0，表示已离开环
                count += 1  # 已离开环的人数加 1
                break  # 跳出内层循环

            index = (index + 1) % n  # 更新当前报数的人的索引

    for i in range(n):
        if people[i] == 1:  # 输出状态为 1 的人的初始编号
            print(i + 1)

# 示例输入
n = 4
m = 3
p = 2

# 调用函数
josephus(n, m, p)

输出结果为：

1
4

括号匹配问题

对于括号匹配问题，可以使用栈来解决。算法的思路如下：

创建一个空栈，用于存储左括号。
从左到右遍历字符串中的每个字符。
如果遇到左括号 ('(', '[', '{')，将其压入栈中。
如果遇到右括号 (')', ']', '}')，判断栈是否为空。
- 如果栈为空，表示右括号没有对应的左括号，返回 False。
- 如果栈不为空，弹出栈顶元素，判断弹出的左括号与当前右括号是否匹配。
  - 如果不匹配，返回 False。
  - 如果匹配，继续遍历下一个字符。
遍历完所有字符后，判断栈是否为空。
- 如果栈为空，表示所有右括号都有对应的左括号，返回 True。
- 如果栈不为空，表示有左括号没有对应的右括号，返回 False。

以下是一个 Python 的实现代码：

def is_valid_parentheses(s):
    stack = []  # 创建一个空栈

    for char in s:
        if char in ['(', '[', '{']:  # 遇到左括号，压入栈中
            stack.append(char)
        else:  # 遇到右括号
            if not stack:  # 栈为空，表示右括号没有对应的左括号
                return False

            top = stack.pop()  # 弹出栈顶元素

            if (char == ')' and top != '(') or \
                    (char == ']' and top != '[') or \
                    (char == '}' and top != '{'):  # 左右括号不匹配
                return False

    return not stack  # 栈为空，表示所有右括号都有对应的左括号

# 示例输入
s = "([{}])"

# 调用函数
print(is_valid_parentheses(s))

输出结果为：

True