Topic
試題 D: 七段碼
本題總分：10 分
【問題描述】
小藍要用七段碼數碼管來表示一種特殊的文字，
上圖給出了七段碼數碼管的一個圖示
數碼管中一共有 7 段可以發光的二極管，分別標記為 a, b, c, d, e, f, g，
小藍要選擇一部分二極管（至少要有一個）發光來表達字符，
在設計字符的表達時，要求所有發光的二極管是連成一片的，
例如：b 發光，其他二極管不發光可以用來表達一種字符，
例如：c 發光，其他二極管不發光可以用來表達一種字符，
這種方案與上一行的方案可以用來表示不同的字符，盡管看上去比較相似，
例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字符，
例如：b, f 發光，其他二極管不發光則不能用來表達一種字符，因為發光的二極管沒有連成一片，
請問，小藍可以用七段碼數碼管表達多少種不同的字符？
【答案提交】
這是一道結果填空的題
你只需要算出結果后提交即可
本題的結果為一個整數
在提交答案時只填寫這個整數
填寫多余的內容將無法得分
Solution
這是一道需要判斷連通的問題
那么我們就會很自然的想到運用并查集解題
能夠運用連通分量個數判斷是否滿足條件
這里運用到了并查集串列法模板
記錄連接關系
那么首先我們需要表示出二極管和兩個二極管間的關系:
我們可以用0到6表示七個二極管
用7 * 7的矩陣記錄與其相連的管兒
先運用numpy下的zeros設定一個7 * 7的全是0的矩陣
將每一行表示為一個管兒
接著將與其相連的管兒對應的索引變為1
那么我們就記錄了二極管間的對應連接關系
排列二極管
二極管表示數字有1個管兒發光到7個管兒發光七種選擇
那么我們先將二極管（0到6）放置在num中
遇到需要拿取的管道我們再拿取
之后我們從1個管兒到7個管兒開始拿取
在取用管道時我們需要將其取用的方法進行全排列
這里用到combination隨機無放回抽樣
保證這樣點亮沒有重復
判斷是否滿足條件
在取用時我們每次實體化一個7個節點的并查集
對于每一個取用的二極管
都需要將其與臨近且點亮的二極管進行節點合并
在這里我們先取用相應個數的二極管
之后逐個二極管判斷與其臨近的二極管是否被取用（點亮）
如果被點亮則將這兩個節點進行合并
合并之前一定要保證兩個節點的索引都是整數的形式
否則并查集串列索引會報錯
每連接一次會減少一個連通分量
被取用（點亮）的二極管若能滿足條件
就會形成一個連通分量
初始有7個連通分量
減去被點亮的二極管個數加上新形成的連通分量數1
則剩下的就是滿足條件的連通分量個數
以上所有篩選條件都滿足后res的值加一
最后輸出res的值就是所求
Code
import numpy as np
import itertools as it
class UnionFind:
def __init__(self, n):
self.father = list(range(n))
self.size = [1] * n
# 當前連通分量數目
self.setCount = n
def find(self, x):
if self.father[x] == x:
return x
self.father[x] = self.find(self.father[x])
return self.father[x]
def merge(self, x, y):
x, y = self.find(x), self.find(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.father[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
res = 0
data = list(np.zeros((7, 7)))
data[0][1] = data[0][5] = 1
data[1][0] = data[1][6] = data[1][2] = 1
data[2][1] = data[2][3] = data[2][6] = 1
data[3][2] = data[3][4] = 1
data[4][3] = data[4][5] = data[4][6] = 1
data[5][0] = data[5][4] = data[5][6] = 1
num = [i for i in range(0, 7)]
for i in range(1, 8):
total = it.combinations(num, i)
for j in total:
uf = UnionFind(7)
for z in j:
for k in range(len(data[z])):
z = int(z)
b = int(data[z][k])
if b == 1 and k in j:
uf.merge(z, k)
if uf.setCount == 7 - len(j) + 1:
res += 1
print(res)
Answer
80
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257799.html
標籤：python