[發明專利]基于空間搜索的唯一隨機數序列的求取算法

在審

• 申請號: 201710252961.5
• 申請日: 2017-04-12
• 公開（公告）號: CN107092463A
• 公開（公告）日: 2017-08-25
• 發明（設計）人: 吳旭軍;劉旭東
• 申請（專利權）人: 煙臺職業學院
• 主分類號: G06F7/58
• 分類號: G06F7/58
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及求取算法領域，尤其涉及一種基于空間搜索的唯一隨機數序列的求取算法。

背景技術

唯一隨機數序列在計算機游戲、軟件測試用例、計算機考試等場景中經常用到，一種最平常的算法是：將每次產生的隨機數進行比較，以前如果出現過就再發生一次，這樣如果序列很長的話，越到后面的運算，所花的時間越長，并且其時間復雜度是無法估計的(因為不知道什么時候才能產生與前面不一樣的隨機數)。通常情況下，由于所使用的隨機序列不長或者對時間要求不高，并且出現極端情況的幾率很小，所以遇上麻煩的情況很少，并且即使遇到問題也可以通過其他手段處理(比如：中止進程)，因此，該問題通常情況被忽視。

基于空間搜索的唯一隨機數序列的求取算法擬解決的問題是：在已知隨機序列的數的上界和下界、隨機序列的長度的情況下，能否找到一種算法，其空間復雜度為O(Max-Min)，(Max：隨機序列的上界，Min：隨機序列的下界)，時間復雜度盡可能小，并且不會出現理論上的無限循環。這樣的算法應該盡可能簡單(能為一般軟件人員接受)，但非常巧妙，因此可以為千千萬萬的軟件所使用，因而變得十分有意義。

絕大多數的軟件人員，或多或少都碰到過這個問題，但都忽視了該問題的極端情況。因此，大多數程序員容易忽略巧妙方法的存在；或者說難以提出問題，也就更不會深入思考了。

因此，有必要提供一種基于空間搜索的唯一隨機數序列的求取算法解決以上技術問題。

發明內容

本發明的目的為了減少獲取唯一隨機序列的計算量，本算法通過構造一個一維的連續整數數組，通過隨機檢索該數組的元素，獲得一個隨機數序列。由于檢索是隨機的，所以確定該序列是隨機的；由于是隨機檢索，當兩次檢索到同一個數時，需要考慮一個輪轉機制，或者使用其他方法處理。

本發明提供一種基于空間搜索的唯一隨機數序列的求取算法，將直接求取隨機序列的過程轉變為求取一個已知序列的隨機地址指針的過程，主要包括下面步驟：

步驟1，變量賦值，定義隨機序列的最大值Max，最小值Min，一個長度為Data[Max-Min]的數組和一個長度為Length的空數組Data1，其中Length為待求隨機序列的長度；

步驟2，如果Max-Min＜Length，轉到步驟9；

步驟3，按照從小(Min)到大(Max)，循環給Data賦值；

步驟4，定義一個循環變量i＝0，如果i＞＝Length，轉到步驟9；

步驟5，產生一個0＜n＜Max-Min的隨機數，取Data[n]；

步驟6，如果Data[n]＝Invalid，n＝(n+1)mod(Length)，回到步驟6；

步驟7，Data1[i]＝Data[n]，Data[n]＝Invalid，i＝i+1轉4；

步驟8，輸出Data1；

步驟9，結束。

與相關技術相比，本發明提供的基于空間搜索的唯一隨機數序列的求取算法對于需要頻繁使用隨機數序列的場合，如：計算機游戲、在線考試系統等應用場景，可以大幅縮減計算時間，提高軟件的運行效率，并排除極端情況下出現的死循環。

附圖說明

圖1為本發明提供的基于空間搜索的唯一隨機數序列的求取算法的流程圖。圖2為求取一個[0，10)以內的5個唯一隨機正整數序列情況下，采用該算法運算的部分空間變化圖。該圖表示通過兩次運算之后的搜索空間的變化情況，第一行為原始空間狀態，左邊10個圓表示Data數組，右邊5個圓表示Data1，第二行、第三行是經過一輪搜索之后，空間變化情況，第四、五行表示第二次隨機搜索之后的空間變化。

具體實施方式

以下將參考附圖并結合實施例來詳細說明本發明。需要說明的是，在不沖突的情況下，本發明中的實施例及實施例中的特征可以相互組合。為敘述方便，下文中如出現“上”、“下”、“左”、“右”字樣，僅表示與附圖本身的上、下、左、右方向一致，并不對結構起限定作用。

閱讀本例請參閱圖1和圖2(本發明提供的基于空間搜索的唯一隨機數序列的求取算法的流程圖和空間變化示意圖)。

假設需要求取一個[0，10)以內的5個唯一隨機正整數序列(實際情況可能比這個序列大得多)，按照本發明提供的算法，這里Max＝10，Min＝0，Length＝5，由于是正整數，取Invalid＝-1；采用最簡單的循環賦值方式為長度為10的一維連續整數數組賦值；采用向后順序流轉作為沖突消解策略。