Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหาค่าดัชนี kth ที่ใหญ่ที่สุดของหนึ่งรายการใน Python


สมมติว่าเรามีสามค่า n, ผลรวม และ k ตอนนี้ให้พิจารณารายการของขนาด n ซึ่งมีผลรวมเท่ากับผลรวมและโดยที่ความแตกต่างที่แน่นอนระหว่างสององค์ประกอบที่ต่อเนื่องกันมากที่สุดคือ 1 เราต้องหาค่าสูงสุดที่ดัชนี k ของรายการดังกล่าว

ดังนั้น หากอินพุตเท่ากับ n =5 ทั้งหมด =15 k =3 ผลลัพธ์จะเป็น 4 เนื่องจากรายการที่เป็นไปได้อย่างใดอย่างหนึ่งคือ [3,2,3,4,3] องค์ประกอบสูงสุดที่พบในดัชนี 3 คือ 4.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • x :=0
  • ทำสิ่งต่อไปนี้ซ้ำๆ ทำ
    • a :=k + 1
    • s :=(x + x - a + 1) * floor if a/2
    • a :=n - k
    • s :=s +(x + x - a + 1) * floor of a/2
    • s :=s - x
    • ถ้า s> ทั้งหมด แล้ว
      • ออกมาจากลูป
    • x :=x + 1
  • ผลตอบแทน x - 1

ตัวอย่าง

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

def solve(n, total, k):
   x = 0
   while 1:
      a = k + 1
      s = (x + x - a + 1) * a // 2
      a = n - k
      s += (x + x - a + 1) * a // 2
      s -= x
      if s > total:
         break
      x += 1
   return x - 1

n = 5
total = 15
k = 3
print(solve(n, total, k))

อินพุต

5, 15, 3

ผลลัพธ์

4