使用Python计算带彩色顶点的正多边形中等腰三角形的数量
假设我们有一个具有n个侧面的正多边形,它被表示为大小为n的二进制字符串。顶点可以涂成蓝色(0)或红色(1)。它们按顺时针方向着色。我们必须计算等腰三角形的数量,其顶点是正多边形的顶点,且它们的颜色相同。
因此,如果输入是多边形=“111010”,则输出将是2,因为
有两个三角形ACE和AFE。
为了解决这个问题,我们将按照以下步骤进行 –
- 定义一个函数“all()”,它将获取n
- 如果n mod 2与1相同,则no := n*(n-1) /2
- 否则,no := n*(n/2-1)
- 如果n mod 3与0相同,则no := no – n/3*2
- 返回no
- 定义一个函数“non()”,它将获取a和n
- 如果n mod 2与1相同,则
- s0 := 0,s1 := 0
- i := 0
- while i < n,do
- 如果a[i]与’0’相同,则s0 := s0 + 1
- 否则,s1 := s1 + 1
- i := i + 1
- s := s0s16
- 如果n mod 3与0相同,则
- n1 := n/3
- n2 := n1*2
- i := 0
- while i < n,do
- 如果a[i]与a[(i+n1)mod n]不相同,则
- s := s – 2
- 如果a[i]与a[(i+n2)mod n]不相同,则
- s := s – 2
- i := i + 1
- 否则,
- s00 := 0,s01 := 0,s10 := 0,s11 := 0,s := 0
- i := 0
- while i < n,do
- 如果a[i]与’0’相同,则s00 := s00 + 1
- 否则,s01 := s01 + 1
- i := i + 2
- i := 1
- while i < n,do
- 如果a[i]与’0’相同,则s10 := s10 + 1
- 否则,s11 := s11 + 1
- i := i + 2
- s := s + s00 * s01 * 8
- s := s + s10 * s11 * 8
- s := s + s00 * s11 * 4
- s := s + s10 * s01 * 4
- n1 := n/2
- i := 0
- while i < n,do
- 如果a[i]与a[(i + n1)mod n]不相同,则
- s := s – 2
- i := i + 1
- 如果n mod 3与0相同,则
- n1 := n/3
- n2 := n1*2
- i := 0
- while i < n,do
- 如果a[i]与a[(i+n1)mod n]不相同,则
- s := s – 2
- 如果a[i]与a[(i+n2)mod n]不相同,则
- s := s – 2
- i := i + 1
- 返回s/2
- 从主方法中,执行以下操作-
- n := polygon的大小
- no := all(n) – non(polygon,n) /2
- 返回no
例子
让我们看下面的实现以获得更好的理解 –
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