Python程序: 找出奖品可以藏在多少个房间里

假设一个游戏节目中有2n个房间排成一个圆圈。其中一个房间里有个奖品，参与者必须去找。房间被编号为1，2，3，…，n、-n，-(n-1)，…，-1，按顺时针方向进行。每个房间都有一扇门，通过门可以通向不同的房间。每个门上都有一个标记x，如果x的值为正数，则意味着从该房间顺时针方向到第x个房间。如果x的值为负数，则意味着从该房间逆时针方向到第x个房间。我们需要找出可以隐藏奖品的房间数量，使参加者难以找到奖品。

因此，如果输入形如input_array = [[4, 2]]，则输出将是[2]。

输入有两个值，第一个值是n，即房间数量的一半，第二个值是参加者开始寻找奖品的房间号。在此例中，有2 x 4 = 8个房间，参与者从顺时针方向的第2个房间开始寻找奖品。房间按顺时针方向编号1、2、3、4、-4、-3、-2、-1。参与者将按照以下方式访问这些房间：2、-4、-1、1、3、-2、-1、1、3、-2、…… 如果奖品藏在4号和-3号房间中，则参与者无法找到它们。

要解决此问题，我们需要遵循以下步骤 –

定义一个函数 prime_num_find()。这将接受 n
- p_nums：一个新的列表，值初始化为 2
- check：一份包含元素字节表示的新列表
对于从 3 到 n 的值，每次增加 2，执行以下操作：
- 如果 check[value] 不为零，则
  - 进入下一个迭代
- 在 p_nums 的末尾插入值
- 对于从 3 * value 到 n 的 i，每步更新为 2 * value，执行以下操作：
  - check[i] := 1
- 返回 p_nums
定义一个函数 factor_finder()。这将接受 p
- p_nums：prime_num_find(45000) 的一个新的映射
- f_nums：一个新的映射
对于 p_nums 中的每个值，执行以下操作：
- 如果 value * value > p 不为零，则
  - 退出循环
- while p mod value 等于 0，执行以下操作：
  - p = floor value of (p / value)
  - 如果 value 在 f_nums 中，则
  - f_nums[value] := f_nums[value] + 1
  - 否则，
  - f_nums[value] := 0
如果 p > 1，则
- f_nums[p] = 1
- 返回 f_nums
定义一个函数 euler_func()。这将接受 p
- f_nums = factor_finder(p)
- t_value = 1
对于 f_nums 中的每个值，执行以下操作：
- t_value = t_value * ((value-1) * value^(f_nums[value] – 1))
  - 返回 t_value
从主函数/方法中执行以下操作 −
输出 = 一个新的列表
对于 input_array 中的每个项，执行以下操作：
- p = item[0]
- q = item[1]
- r = 2 * p + 1
- r = floor value of (r / gcd value of (r, q mod r))
- t_value = euler_func(r)
- 对于 factor_finder(t_value) 中的每个值，执行以下操作：
  - while 当 t_value mod value 等于 0 且 (2 ^ floor value of(t_value / value) mod r) 等于 1 时：
  - t_value = floor value of (t_value / value)
- 在输出的末尾插入 2 * p – t_value
返回输出

更多Python相关文章，请阅读：Python 教程

示例

让我们看以下实现以更好地理解 −

import math
def prime_num_find(n):
    p_nums = [2]
    check = bytearray(n)
    for value in range(3, n, 2):
        if check[value]:
            continue
        p_nums.append(value)
        for i in range(3 * value, n, 2 * value):
            check[i] = 1
    return p_nums
def factor_finder(p):
    p_nums = prime_num_find(45000)
    f_nums = {}
    for value in p_nums:
        if value * value > p:
            break
        while p % value == 0:
            p //= value
            f_nums[value] = f_nums.get(value,0) + 1
    if p > 1:
        f_nums[p] = 1
    return f_nums
def euler_func(p):
    f_nums = factor_finder(p)
    t_value = 1
    for value in f_nums:
        t_value *= (value-1) * value ** (f_nums[value]-1)
    return t_value
def solve(input_array):
    output = []
    for item in input_array:
        p, q = item[0], item[1]
        r = 2 * p + 1
        r //= math.gcd(r, q % r)
        t_value = euler_func(r)
        for value in factor_finder(t_value):
            while t_value % value == 0 and pow(2, t_value // value, r) == 1:
                t_value //= value
            output.append(2 * p - t_value)
    return output
print(solve([[4, 2]]))