圓圈中最後剩下的數字

題目：0，1，...，n-1這n個數字排成一個圓圈，從數字0開始每次從這個圓圈裡删除第m個數字。求出這個圓圈裡剩下的最後一個數字。

這就是有名的約瑟夫（Josephuse）環問題。可以用環形連結清單模拟圓圈的經典解法。

分析：用模闆庫中的std::list來模拟一個環形連結清單。由于std::list本身不是一個環形結構，是以每當疊代器掃描到連結清單末尾的時候，要記得把疊代器移到連結清單的頭部，這樣就相當于按照順序在一個圓圈裡周遊了。

這種思路的代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

<code>int</code> <code>LastRemaining(unsigned </code><code>int</code> <code>n, unsigned </code><code>int</code> <code>m)</code>

<code>{</code>

<code>    </code><code>if</code><code>(n &lt; 1 || m &lt; 1)</code>

<code>        </code><code>return</code> <code>-1;</code>

<code>    </code> 

<code>    </code><code>unsigned </code><code>int</code> <code>i = 0;</code>

<code>    </code><code>list&lt;</code><code>int</code><code>&gt; numbers;</code>

<code>    </code><code>for</code><code>(i = 0; i &lt; n; ++i)</code>

<code>        </code><code>numbers.push_back(i);</code>

<code>    </code><code>list&lt;</code><code>int</code><code>&gt;::iterator current = numbers.begin();</code>

<code>    </code><code>while</code><code>(numbers.size() &gt; 1)</code>

<code>    </code><code>{</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 1; i &lt; m; ++i)</code>

<code>        </code><code>{</code>

<code>            </code><code>current++;</code>

<code>            </code><code>if</code><code>(current == numbers.end())</code>

<code>                </code><code>current = numbers.begin();</code>

<code>        </code><code>}</code>

<code>        </code> 

<code>        </code><code>list&lt;</code><code>int</code><code>&gt;::iterator next = ++current;</code>

<code>        </code><code>if</code><code>(next == numbers.end())</code>

<code>            </code><code>next = numbers.begin();</code>

<code>        </code><code>--current;</code>

<code>        </code><code>numbers.erase(current);</code>

<code>        </code><code>current = next;</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code> <code>*(current);</code>

<code>}</code>

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3645558.html，如需轉載請自行聯系原作者