資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
- 如果check[value]不為零，則
- 定義一個函式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
- 如果value * value > p不為零，則
- 如果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
- t_value := t_value * ((value-1) * value^(f_nums[value] - 1))
- 從主函式/方法中執行以下操作：
- 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)的下取整
- 當t_value模value等於0且(2 ^ (t_value / value)的下取整模r)等於1時，執行以下操作：
- 將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次瀏覽
廣告