劉瀚文

摘要：本文給出了史坦因豪斯18點(diǎn)問題的一個(gè)圖論求解模型，并采用Prolog語言描述了相應(yīng)的求解算法，從而構(gòu)造性地解決了史坦因豪斯問題。文章分析了該算法在最壞情況下的時(shí)間復(fù)雜性，并給出了2種形式下史坦因豪斯問題的機(jī)器運(yùn)行結(jié)果。

關(guān)鍵詞： 史坦因豪斯18點(diǎn)問題； 二部圖； 完美匹配

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：2095-2163（2017）05-0035-03

Abstract：Based on the graph theory， a solving method for Stainhauss 18 points problem is approached in this paper. The algorithm for solving the problem is given on Prolog and the Stainhauss problem is completely solved by the construction method. The complexity of the algorithm in the badest case and the running results are given too.

Keywords：Stainhaus 18 points problem； bipartite graph； perfect match

收稿日期： 2017-08-15

3問題求解程序及其性能分析

[JP2]由求解問題的圖論模型，不難設(shè)計(jì)出相應(yīng)的算法和求解程序。下面是問題求解過程的Prolog描述（文中，略去了研發(fā)程序），函數(shù)f（p， q）表示分?jǐn)?shù)p/q， t（f1， f2）表示區(qū)間[f1， f2]， f1， f2為分?jǐn)?shù)，stainhaus為求解問題的主謂詞，stainhaus0為其尾遞歸版本，其中使用了一種典型的用變量保存中間結(jié)果的技巧。謂詞stainhaus0（N，K0，S0，S）表示目前要構(gòu)造n=K0+1的解，當(dāng)n=K0時(shí)的解為S0，要求做出n=N時(shí)的解S。

當(dāng)K0

1）構(gòu)造n=K0+1=K1的二部圖；

2）從該二部圖中尋找完美匹配；

3）基于該完美匹配將原來的部分解S0擴(kuò)展為S1；

4）尾遞歸調(diào)用stainhaus0（N，K1，S1，S）。

當(dāng)K0=N時(shí)， S0即為S。

程序的性能決定于部分解擴(kuò)展過程中完美匹配的個(gè)數(shù)。為此可得：

程序運(yùn)行找到史坦因豪斯問題在n=19時(shí)的一個(gè)解：

[0/1， 1/19]， [2/3， 2/3]， [5/6， 5/6]， [2/5， 7/17]， [1/5， 4/19]， [10/11， 11/12]， [5/9， 5/9]， [1/3， 1/3]， [11/15， 14/19]， [1/10， 2/19]， [7/15， 8/17]， [18/19， 1/1]， [5/18， 2/7]， [11/18， 5/8]， [2/15， 3/19]， [7/9， 15/19]， [1/2， 10/19]， [2/9， 5/19]， [16/19， 17/19]

與Warmus的證明結(jié)果不同，其原因在于數(shù)學(xué)家們研究的18點(diǎn)問題中所有區(qū)間都定義為開區(qū)間或半開半閉區(qū)間（在前面Warmus給出的解中，其解元素均為半開半閉區(qū)間），在史坦因豪斯問題的原始表達(dá)形式中，并沒有限定[0，1]的等分區(qū)間一定為閉區(qū)間或開區(qū)間，而這里給出的解元均為閉區(qū)間，這樣就容許單點(diǎn)區(qū)間的存在，例如上述問題解中的[1/3，1/3]，而這種單點(diǎn)區(qū)間可以在解擴(kuò)展時(shí)向左右兩邊連接，因此解的范圍能夠擴(kuò)大，這也導(dǎo)致問題在n=19時(shí)存在解，研究中通過程序運(yùn)行也證明了在容許閉區(qū)間的情況下，n=20時(shí)史坦因豪斯問題無解。

除問題2中將等分區(qū)間全部理解為閉區(qū)間的形式外，史坦因豪斯問題還可以將所有等分區(qū)間表示為開區(qū)間的形式。這時(shí)，程序中構(gòu)造解的謂詞需作以下修改：

參考文獻(xiàn)

史坦因豪斯. 一百個(gè)數(shù)學(xué)問題[M]. 上海：上海教育出版社，1980.

[2] [JP2]WARMUSM. A supplementary note on the irregularities of distributions[J]. Journal of Number Theory，1976，8（3）： 260-263.

[3] Weisstein， Eric W. 18-Point Problem， From MathWorld—A Wolfram Web Resource. [EB/OL]. [2017-07-31]. http：//mathworld.wolfram.com/18-PointProblem.html.

[4] GARDNERM. The last recreations： Hydras， eggs， and other mathematical mystifications[M]. New York： Springer-Verlag， 1997.

[5] BERLEKAMP E R， GRAHAM R L. Irregularities in the distributions of finite sequences[J]. Journal of Number Theory， 1970，2（2）：152-161.

[6] CHRISTOFIDESN. Graph theory： An algorithmic approach[M]. NY， USA：Academic Press， 1975.

[7] CLOCKSIN W F， MELLISH C S. Programming in Prolog[M]. NY， USA： Springer-Verlag， 1984.

[8] BONDY J A，MURTY U S R. 圖論及其應(yīng)用[M]. 吳望名，李念祖，等譯. 北京：科學(xué)出版社，1984.

4結(jié)束語

本設(shè)計(jì)將三軸加速度傳感器與輔助作用的傾斜傳感器結(jié)合后通過GSM模塊與Lora無線模塊實(shí)現(xiàn)2種報(bào)警方式：遠(yuǎn)程報(bào)警和近距離報(bào)警。近距離報(bào)警是在Lora模塊通信距離范圍內(nèi)，實(shí)現(xiàn)接收端的報(bào)警提示，在實(shí)際應(yīng)用中可將無線接收端置于家中，作為輔助報(bào)警手段，增加了老人跌倒后救助的成功率。本文設(shè)計(jì)的算法簡(jiǎn)潔有效，準(zhǔn)確率高，具有較強(qiáng)的實(shí)用性。

參考文獻(xiàn)：

邵宇吉，吳其林，朱治鵬，等. 一種新型腰帶計(jì)步器的設(shè)計(jì)研究[J]. 電子測(cè)試，2015 （19）：111-112.

[2] 高英梅. 老年人跌倒的原因分析及護(hù)理干預(yù)[J]. 中國(guó)醫(yī)藥指南， 2013，11（27）：263-264.

[3] 王剛. 基于Arduino Uno平臺(tái)的跌倒檢測(cè)報(bào)警系統(tǒng)設(shè)計(jì)[J]. 單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2015（7）：49-52.

[4] 王剛，溫向明，路兆銘，等. 新興物聯(lián)網(wǎng)技術(shù)——LoRa[J]. 信息通信技術(shù)，2017（1）：55-59，72.

[5] 劉導(dǎo). 基于STM32單片機(jī)的動(dòng)力鋰電池管理系統(tǒng)[D]. 保定：河北大學(xué)， 2015.

[6] 劉艷，劉文文，王蓮蓮. 老年人跌倒的危險(xiǎn)因素及護(hù)理干預(yù)[J]. 現(xiàn)代醫(yī)藥衛(wèi)生，2015，31（5）：688-690.

[7] 薛源. 基于多傳感器的老人跌倒檢測(cè)系統(tǒng)的研究與應(yīng)用[D]. 武漢：武漢理工大學(xué)，2011.

[8] 李飛龍. 基于三軸加速度傳感器跌倒檢測(cè)方法的研究[D]. 成都：電子科技大學(xué)， 2015.

[9] 孫子文， 孫曉雯. 基于加速度傳感器的人體跌倒檢測(cè)方法[J]. 計(jì)算機(jī)工程與科學(xué)， 2017， 39（2）：330-335.

[10]曹玉珍， 蔡偉超， 程旸. 基于MEMS加速度傳感器的人體姿態(tài)檢測(cè)技術(shù)[J]. 納米技術(shù)與精密工程， 2010， 8（1）：37-41.endprint