โปรแกรมนับจำนวนสามเหลี่ยมหน้าจั่วจากจุดยอดสีปกติรูปหลายเหลี่ยมใน Python

สมมติว่าเรามีรูปหลายเหลี่ยมปกติหนึ่งรูปที่มีด้าน n แทนเป็นสตริงไบนารีขนาด n จุดยอดสามารถเป็นสีน้ำเงิน (0) หรือสีแดง (1) พวกมันถูกระบายสีตามเข็มนาฬิกา เราต้องนับจำนวนสามเหลี่ยมหน้าจั่วที่มีจุดยอดเป็นจุดยอดของรูปหลายเหลี่ยมปกติและมีสีเท่ากัน

ดังนั้น หากอินพุตเป็นเหมือนรูปหลายเหลี่ยม ="111010" ผลลัพธ์จะเป็น 2 เพราะ

มีสามเหลี่ยมสองรูปคือ ACE และ AFE

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

• กำหนดฟังก์ชัน all() นี่จะใช้เวลา n
• ถ้า n mod 2 เหมือนกับ 1 แล้ว ไม่ใช่ :=n*(n-1) /2
• มิฉะนั้น ไม่ :=n*(n/2-1)
• ถ้า n mod 3 เหมือนกับ 0 แล้ว no :=no - n/3*2
• ไม่รับคืน
• กำหนดฟังก์ชัน non() นี่จะใช้เวลา a,n
• ถ้า n mod 2 เหมือนกับ 1 แล้ว
  • s0 :=0, s1 :=0
  • ผม :=0
  • ในขณะที่ฉัน
  • ถ้า a[i] เหมือนกับ '0' ดังนั้น s0 :=s0 + 1
  • มิฉะนั้น s1 :=s1 + 1
  • ผม :=ผม + 1
• s :=s0*s1*6
• ถ้า n mod 3 เหมือนกับ 0 แล้ว
  • n1 :=n/3
  • n2 :=n1*2
  • ผม :=0
  • ในขณะที่ฉัน
  • ถ้า a[i] ไม่เหมือนกับ a[(i+n1)mod n] แล้ว
    • s :=s - 2
  • ถ้า a[i] ไม่เหมือนกับ a[(i+n2)mod n] แล้ว
    • s :=s - 2
  • ผม :=ผม + 1

ตัวอย่าง

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

def all(n):
   if n % 2 == 1:
      no = n*(n-1)/2
   else:
      no = n*(n/2-1)
   if n % 3 == 0:
      no -= n/3*2
   return no

def non(a,n):
   if n % 2 == 1:
      s0 = s1 = 0
      i = 0
      while i < n:
         if a[i] == '0':
            s0 += 1
         else:
            s1 += 1
         i += 1
      s = s0*s1*6
      if n % 3 == 0:
         n1 = n/3
         n2 = n1*2
         i = 0
         while i<n:
            if a[i] != a[int((i+n1)%n)]:
               s -= 2
            if a[i] != a[int((i+n2)%n)]:
               s -= 2
            i += 1
   else:
      s00 = s01 = s10 = s11 = s = 0
      i = 0
      while i <n:
         if a[i] == '0':
            s00 += 1
         else:
            s01 += 1
         i += 2
      i = 1
      while i < n:
         if a[i] == '0':
            s10 += 1
         else:
            s11 += 1
         i += 2
      s += s00 * s01 * 8
      s += s10 * s11 * 8
      s += s00 * s11 * 4
      s += s10 * s01 * 4
      n1 = n/2
      i = 0
      while i < n:
         if a[i] != a[int((i + n1)%n)]:
            s -= 2
         i += 1
      if n % 3 == 0:
         n1 = n/3
         n2 = n1*2
         i = 0
         while i < n:
            if a[i] != a[int((i+n1)%n)]:
               s -= 2
            if a[i] != a[int((i+n2)%n)]:
               s -= 2
            i += 1
   return s/2

def solve(polygon):
   n = len(polygon)
   no = all(n) - non(polygon,n)/2
   return int(no)

polygon = "111010"
print(solve(polygon))

อินพุต

1, 1000

ผลลัพธ์

2