2010-07-16 67 views
4

問題看起來像這樣, 您必須將N px寬度線繪製爲M個統一的破折號。統一整數除法器

如果例如N = 13和M = 5,我們的短劃線將有2 px寬度,我們將有3 px錯誤。

我們可以做得更好,我們可以繪製以下寬度的破折號:3,3,3,2,2。 但我們可以做得更好破折號可以有以下寬度:3,2,3,2,3。

如果我有一個列表a =(3,3,3,2,2)我怎麼能找到這樣的列表,列表中所有對之間的距離'D'將是最大的? D(b)= 1 + 1 + 1 + 1 = 1 = 4.

什麼是最快/最簡單的方法?

+0

這是[家庭作業]?你到目前爲止有什麼?因爲我不完全理解爲什麼3-2-3-2-3比3-3-3-2-2更好,您還可以添加更多信息。爲什麼我們想要最大化D()? – Edd 2010-07-16 12:29:16

+0

我們想要最大化D(),因爲我們想繪製看起來像相等的元素,並且所有元素都會選擇大小。例如想象繪製任意大小的棋盤。 – bartek 2010-07-16 12:34:14

+0

破折號之間沒有空格嗎? – Svante 2010-07-16 15:40:37

回答

2

我知道最簡單的方法嗎?使用浮點數...

在Python:

def pace(D,M): return [round(float(D)/M * i) for i in range(1,M+1)] 

我已經在這裏看到這個地方我想。

+0

美麗,這是很好,簡單的答案。唯一的想法是,這不會給我們答案如何找到解決更普遍的問題 - 給定一組整數,找到這樣的排列,最大化D,但正如我所說,這是我的問題的很好的解決方案,謝謝。 – bartek 2010-07-16 18:24:10

0

Bresenham's algorithm啓發的東西應該可以做到。相信我,你不希望在你的設置的所有排列中使D最大化。這個問題太複雜了(複雜度是O(n!),所以除非n很小,否則這將不起作用)

+0

也許這是一個好方向。當我尋找答案時,我沒有想過。 當然,我不想最大化目標的功能!我只是想以正式的方式表達這個問題。 – bartek 2010-07-16 13:14:14