โปรแกรม 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

  • ตรวจสอบ :=รายการใหม่ที่มีการแทนค่าไบต์ขององค์ประกอบ

• สำหรับค่าในช่วง 3 ถึง n เพิ่มขึ้น 2 ทำ

  • ถ้า check[value] ไม่ใช่ศูนย์ แล้ว
    • ติดตามตอนต่อไป
  • ใส่ค่าที่ส่วนท้ายของ p_nums
  • สำหรับ i ในช่วง 3 * ค่าเป็น n ให้อัปเดตในแต่ละขั้นตอนด้วยค่า 2 * ทำ
    • check[i] :=1
  • ส่งคืน p_nums
• กำหนดฟังก์ชัน factor_finder() นี่จะใช้เวลา p
  • p_nums :=prime_num_find(45000)
  • f_nums :=แผนที่ใหม่
• สำหรับแต่ละค่าใน p_nums ให้ทำ
  • ถ้าค่า * ค่า> p ไม่ใช่ศูนย์ ดังนั้น
    • ออกมาจากวงจร
  • ในขณะที่ค่า p mod เหมือนกับ 0, do
    • p :=ค่าพื้นของ (p / ค่า)
    • ถ้าค่าเป็น 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 :=ค่าพื้นของ (ค่า r / gcd ของ (r, q mod r))
  • t_value :=euler_func(r)
  • สำหรับแต่ละค่าใน factor_finder(t_value) ทำ
    • ในขณะที่ค่า mod t_value เหมือนกับ 0 และ (2 ^ ค่าพื้นของ (t_value / ค่า) mod r) เหมือนกับ 1 ทำ
      • t_value :=ค่าพื้นของ (t_value / ค่า)
  • แทรก 2 * p - t_value ที่ส่วนท้ายของเอาต์พุต
• ผลตอบแทนที่ได้

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]