Python程序找出可以隐藏奖品的房间数量

假设，在一个游戏节目中，有2n个房间，这些房间呈圆形排列。其中一个房间里藏着一个奖品，参与者必须收集它。房间从1、2、3、…、n、-n、-(n-1)、…、-1按顺时针方向编号。每个房间都有一扇门，通过这扇门可以访问另一个房间。每扇门上都有一个标记x，表示另一个房间距离当前房间x个单位。如果x的值为正，则门打开到从该房间顺时针方向的第x个房间。如果x的值为负，则表示门打开到从该房间逆时针方向的第x个房间。我们必须找出可以放置奖品的房间数量，以及参与者难以找到奖品的情况。

因此，如果输入类似于input_array = [[4, 2]]，则输出将为[2]

输入有两个值，第一个值是n，它是房间总数的一半，第二个值是参与者开始寻找奖品的房间号。这里有2x4 = 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]不为零，则
      • 跳过本次迭代
    • 将value插入到p_nums的末尾
    • 对于从3 * value到n的每个值，步长为2 * value，执行以下操作：
      • check[i] := 1
    • 返回p_nums
  • 定义一个函数factor_finder()。这将接收p作为参数
    • p_nums := prime_num_find(45000)
    • f_nums := 一个新的映射
  • 对于p_nums中的每个值，执行以下操作：
    • 如果value * value > p不为零，则
      • 退出循环
    • 当p模value等于0时，执行以下操作：
      • p := (p / value)的下取整
      • 如果f_nums中存在value，则
        • 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
  • 从主函数/方法中执行以下操作：
  • output := 一个新的列表
  • 对于input_array中的每个项目，执行以下操作：
    • p := item[0]
    • q := item[1]
    • r := 2 * p + 1
    • r := (r / (r, q模r)的最大公约数)的下取整
    • t_value := euler_func(r)
    • 对于factor_finder(t_value)中的每个值，执行以下操作：
      • 当t_value模value等于0且(2 ^ (t_value / value)的下取整模r)等于1时，执行以下操作：
        • t_value := (t_value / value)的下取整
    • 将2 * p - t_value插入到output的末尾
  • 返回output

示例

让我们看看以下实现，以获得更好的理解：

 在线演示

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]]))

输入

[[4, 2]]

输出

[2]

更新于： 2021年5月18日

428次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告