最好的算法沒有解決

-5

2天，我與問題戰鬥。這是純粹的算法和數學。順便說一下，我需要用C編寫它。最好的算法沒有解決

這就是：

我們有一個安裝通訊窗口的時間。這個窗口可以分解成幾個子窗口並且有多次重複。

這種設置是由：

的起始時間
子窗口開始時間（陣列1至4個元素）其在從起始時間偏移的不同的子窗口的
數量在子窗口幀的
分辨率（時間順便說一句2幀）
重複數
時間順便說一句重複

讓我們做一個例子：進行配置：

的起始時間：0
子窗口開始時間： 300S 400S在
幀數子窗口：50
分辨率（時間btw 2幀）：1s
重複數：2
時間順便說一句重複：600S

例

Additionnaly，重複次數可以被設定爲規定值（65535），這意味着我們將在當時有無限的重複窗口。

的問題如下： 你有兩個聯繫窗口已編程稱爲A和B. 要編一個新的名爲C，但你必須檢查新的通信窗口Ç不重疊任何其他SUB窗口。

如何進行此項檢查？

如果您有任何意見，這將是巨大的:) 像步驟做，出發點，任何

謝謝你很多。任何幫助將不勝感激

來源

2015-10-22 Jérome Goulet

如果您有固定的解決方案和相對較小的時間間隔，您可以使用數組（位域）來存儲每個插槽。 –

問題是我必須在具有非常少的空間和內存的微控制器上實現這一點。我還要管理無限次重複的最壞情況。但我會調查你的想法。 Thk –

提示：https：//en.wikipedia.org/wiki/Least_common_multiple –

我將談論如何找到碰撞時的所有序列重複無限，當所有的起始時間爲0。這是很容易給這個適應有限的情況：只是檢查是否有任何你發現這種方式發生的碰撞發生得足夠早成爲一個問題。適應非0開始時間也很容易：只要將非0開始時間週期性地向後循環到0，並檢查您是否發現這種方式的任何碰撞發生的時間足以造成問題。

讓我們有一個表示通信窗口的數據結構。它將保存窗口的長度（以秒爲單位）以及該窗口正在使用的一系列時間範圍。因此：

type Block = (Int, Int) 
data Window = Window 
    { len :: Int 
    , blocks :: [Block] 
    }

（記號[Block]說來存儲其元素爲Block類型的列表，我們會解釋對Int小號組成一個Block爲開始時間和結束時間，併爲）。我們將保持不變，即如果w是一個窗口並且t是w中的一個塊的開始或結束時間，則0 <= t < len w。現在

，很容易使Window時間越長，所提供的新的長度是舊的倍數：剛剛撞了len，使現有blocks的多個副本，由len移，上升到新長度。因此：

unsafeExpand :: Int -> Window -> Window 
unsafeExpand newLen (Window { len = oldLen, blocks = oldBlocks }) = Window 
    { len = newLen 
    , blocks = [ (start + shift, end + shift) 
       | (start, end) <- oldBlocks 
       , shift <- [0, oldLen .. newLen-1] 
       ] 
    }

（我稱這個unsafeExpand因爲它假定newLen是oldLen多 - 我們將確保這下面，但unsafe是一個提醒，有一個前提條件檢查我會用這。整個命名約定）

另一件事，很容易是要檢查特定塊是否重疊另一個特定塊：

blockCollides :: Block -> Block -> Bool 
blockCollides (start, end) (start', end') = end >= start' && end' >= start

鑑於原始，很容易檢查WH以太兩個相同長度的窗口碰撞：只是檢查一個塊是否與另一個塊碰撞。實際上，因爲我們希望能夠稍後做一個有限版本的算法，所以不僅返回是否存在碰撞，而且還包括所有碰撞的列表將很方便。當然，一個空的列表表明沒有碰撞。

unsafeWindowCollisions :: Window -> Window -> [(Block, Block)] 
unsafeWindowCollisions w w' = 
    [ (b, b') 
    | b <- blocks w 
    , b' <- blocks w' 
    , blockCollides b b' 
    ]

爲確保兩個窗口具有相同的長度，我們可以將它們擴展到它們的最小公倍數。因此，我們可以把上面的不安全功能到一個安全的一個如下：

windowCollisions :: Window -> Window -> [(Block, Block)] 
windowCollisions wShort wShort' = unsafeWindowCollisions wLong wLong' where 
    newLen = lcm (len wShort) (len wShort') 
    wLong = unsafeExpand newLen wShort 
    wLong' = unsafeExpand newLen wShort'

我們可以肯定它的好打電話unsafeExpand因爲lcm a b總是返回a和b的倍數;我們可以確定可以致電unsafeWindowCollisions，因爲wLong和wLong'的長度相同（即newLen）。

現在我們完成了：我們有一個算法來查找兩個窗口之間的碰撞。如果你有兩個以上的窗口，你可以兩兩檢查它們是否有碰撞。下面是ghci中的一些快速示例運行，以查看它的工作。以>開頭的行表示我的輸入;其他行是解釋器的輸出。

> let testWindow1 = Window 600 [(300, 350), (400, 450)] 
> let testWindow2 = Window 300 [(100, 150)] 
> let testWindow3 = Window 200 [(151, 199)] 
> let testWindow4 = Window 3 [(1, 1)] 
> let testWindow5 = Window 4 [(2, 3)] 
> windowCollisions testWindow1 testWindow2 
[((400,450),(400,450))] 
> windowCollisions testWindow1 testWindow3 
[] 
> windowCollisions testWindow4 testWindow5 
[((7,7),(6,7)),((10,10),(10,11))]

來源

2015-10-22 20:43:02

謝謝丹尼爾。你的解決方案是建設性的。但我無法使用它，因爲我們處在微控制器上。如果你有一個窗口長度太大的原始數字，它會使我的微觀崩潰。我必須考慮其他解決方案。順便說一句，我用Python編寫你的例子，它幾乎適用於所有情況。 –

最好的算法沒有解決

回答

相關問題