我需要在 python3 中撰寫一個函式，該函式根據輸入用較小的正方形填充較大的正方形。
輸入是一個正整數串列。每個整數是每行的正方形數。所以串列 [3, 8, 5, 2] 意味著我有 4 行方格，其中第一個有 3 個方格，第二個有 8 個，依此類推。所有行中的所有正方形大小相同。
輸出應該是串列串列形式的行分布描述。
問題是在輸出上不能有空行。所以有效的列數不能大于行數。這些行可以分成兩行或多行。例如，對于串列 [3, 8, 5, 2]，函式應該回傳 [[3], [5, 3], [5], [2]]：
AAA
BBBBB
BBB
CCCCC
DD
對于輸入 [14,13,2,12] 它應該回傳 [[7,7], [7,6], [2], [7,5]]：
AAAAAAA
AAAAAAA
BBBBBBB
BBBBBB
CC
DDDDDDD
DDDDD
正如我們所看到的，兩個示例中的行數和列數是相等的。當然，這并不總是可能的，但列數和行數之間的差異越小，演算法的效率就越高 - 正方形填充得越好。一般來說，我們的目標是獲得盡可能多的列和盡可能少的行。
這就是問題所在——上面的例子使用了 4 個輸入行——輸入串列可以有更多的元素（例如 200 個輸入行）。問題是找到拆分行的最佳方法（例如，如果我應該將 18 拆分為 9 9 或 6 6 6 或 7 7 4 或 5 5 5 3）。因為每次我根據可用列（取決于使用的行數）拆分行時，我都會得到更多的輸出行，因此我可以使用更多額外的可用列——我陷入了一些奇怪的回圈或遞回。
如果有一些我看不到的簡單解決方案，我很抱歉，并提前感謝您的幫助<3
編輯：這里我包含示例函式，它只是忽略了行數增加的事實，只是將輸入行數視為可能的最大列數：
def getSquare(x):
output = list()
ln = len(x)
for i in x:
if i <= ln:
output.append([i])
else:
split = list()
nrows = i // ln
for j in range(nrows):
split.append(ln)
if i % ln:
split.append(i % ln)
output.append(split)
return output
print(getSquare([14, 13, 2, 12]))
# returns [[4, 4, 4, 2], [4, 4, 4, 1], [2], [4, 4, 4]]
# so 4 columns and 12 rows
# columns - maximum number in the matrix
# rows - number of all elements in the matrix (length of flattened output)
# while it should return: [[7,7], [7,6], [2], [7,5]]
# so 7 columns and 7 rows
#(nr of columns should be not larger but as close to the number of rows as possible)
EDIT2：它不必回傳完美的正方形 - 只是盡可能接近正方形 - 例如對于 [4,3,3] 它應該回傳 [[3,1],[3] ,[3]] 而對于像 [1,1,1] 這樣的極端情況，它應該只回傳 [[1],[1],[1]]
uj5u.com熱心網友回復：
list = [3, 8, 5, 2] #As close to a Square as possible
def getSquare(list):
for i in range(1, max(list) 1):
output = []
num = 0
for j in list:
output.append([i]*(j//i))
num = j//i
if j%i != 0:
output[-1].append(j%i)
num = 1
if num == i:
return output
i = int( sum(list) ** (1/2) // 1)
output = []
for j in list:
output.append([i]*(j//i))
num = j//i
if j%i != 0:
output[-1].append(j%i)
num = 1
return output
for i in getSquare(list):
for j in i:
print("*"*j)
i這里我只是重復串列的拆分程序，直到num變得相同。
uj5u.com熱心網友回復：
本質上，當你減小寬度時，你會增加行數（反之亦然：當你增加寬度時，你會減少行數），這就是為什么你想盡可能地均衡寬度和高度，因為這會讓你覆寫正方形的最小面積。從這個角度來看，您的問題看起來像三元搜索：最小化結果寬度和高度的最大值。
所以我們在寬度上執行三元搜索（修復它）并計算得到的最大正方形邊。計算功能非常明顯：
def get_max_side(l, fixed_width): # O(len(l))
height = 0
for i in l:
height = i // fixed_width
if i % fixed_width:
height = 1
return max(fixed_width, height)
然后在三元搜索演算法中使用它來找到最小值get_max_side并使用找到的值恢復答案。時間復雜度為O(len(l) * log(max_meaningful_square_width))。
uj5u.com熱心網友回復：
我改進了 KillerRebooted 的答案，添加了一些停止標志以普遍加快演算法。當沒有找到理想的解決方案時，它也會給出更有效的答案。
lst = [14, 13, 2, 12] # As close to a Square as possible
def getSquare(lst):
output = []
mx = max(lst)
for cols in range(min(len(lst), mx), mx 1):
out = []
rows = 0
for j in lst:
ln = j // cols
r = j % cols
out.append([cols] * ln)
rows = ln
if r:
out[-1].append(r)
rows = 1
if rows >= cols:
output = out
else:
break
return output
square = getSquare(lst)
print(square)
for i in square:
for j in i:
print("*" * j)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520452.html