iT邦幫忙

DAY 2
0

連續30天,挑戰演算法系列 第 2

[Day02] 在PTT看到的排隊問題

這是一個載PTT的 TechJob 版上看到鄉民問的一個問題,覺得很有趣,就嘗試解了一下!

他的問題如下:
假設有一間超級好吃的麵包店,每次買東西都要排隊排很久,但是老闆又不願意大家一大早就來排隊。於是乎老闆就想出了一個方法,讓不是只有最前面的人才能買的到麵包,也不是排後面就一定買不到。

可以買到麵包的方式如下:
每個排隊的人都會有一個號碼牌,假設有 N 個人排隊,那麼號碼排就是從 1 一直到 N
接者會亂數取一個當作開始的號碼 s 和間隔的號碼 i 以及總共要可以買到麵包的人數 t
因此,就是有 N 個人在排隊,從號碼 s 開始算(含s)每隔 i 個人取一人,總共取 t 人
如果遇到最後,就再從頭算起

舉個例子來說:
有十個人在排隊 1 2 3 4 5 6 7 8 9 10
從第 2 個人開始每隔 4 個人取一人,共取 5 位。
則,選取到的幸運兒就是 [2 6 10 5 1]

那這題該怎麼解呢?乍看之下好像滿簡單的,可是卻又充滿陷阱。一不小心就很容易出錯。
因此我們先弄清我們需要什麼好了!

  1. 既然是排隊,那最簡單的當然是用一個 List 來放囉!就像真的排隊一樣。
    List<int> personList = new List<int>();

  2. 就是我們會需要一個存放結果的地方,這個就用一個text陣列吧!因為需要放多少個號碼牌是已知,陣列就是最簡單的方式了。
    int[] selectedPerson = new int[總選取人數];

  3. 也就是最重要的部份,開始選人。

把開始號碼 assign 給選取號碼
while 還沒選滿時
用 選取號碼 從排隊中選出該號碼放入 選取陣列
取得下一個選取號碼並 assign 給 選取號碼

  1. 這個步驟就是要每隔 interval 取一位了。因為,如果遇到最後一位必須從頭算起,所以就必須使用到取餘數這個方式了。

取得下一個選取號碼
將目前的位置加上間隔數字
如果超目前位置大於排隊總人數,就從頭算起 ( mod 排隊總人數 )

如果你想驗證你寫的對不對,我有寫一個 測試程式 你可以放到 Visual Studio 上去試試看就知道有沒有錯了。 ^^"

以下是我的答案 程式碼下載
(sorry, 因為還不熟悉新版的鐵人賽發文介面,所以程式碼貼起來很醜,如果看不舒服,可以點我的程式碼下載連結,上 Github 看會更清楚一些)

        public static int[] Select(int totalPerson, int startPerson, int interval, int countOfSelected)
        {
            List<int> personList = new List<int>();
            int[] selectedPerson = new int[countOfSelected];

            InitialPersonList(totalPerson, personList);

            int selectedIndex = startPerson - 1;
            for (int i = 0; i < countOfSelected; i++)
            {
                selectedPerson[i] = personList[selectedIndex];

                personList.RemoveAt(selectedIndex);
                selectedIndex--;

                selectedIndex = GetNextPersonIndex(interval, personList.Count, selectedIndex);
            }

            return selectedPerson;
        }

        private static int GetNextPersonIndex(int interval, int countOfPersonList, int selectedIndex)
        {
            selectedIndex += interval;
            selectedIndex %= countOfPersonList;
            return selectedIndex;
        }

        private static void InitialPersonList(int totalPerson, List<int> personList)
        {
            for (int i = 0; i < totalPerson; i++)
                personList.Add((i + 1));
        }

上一篇
[Day01] 30天挑戰演算法 - 開始
下一篇
[Day03] 股市中最佳買賣時機-I
系列文
連續30天,挑戰演算法30
0
海綿寶寶
iT邦超人 1 級 ‧ 2014-10-02 21:15:53

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

請教一下
為何是 2 6 10 5 1
而不是 2 6 10 4 8
疑惑

0
丁大丙
iT邦研究生 5 級 ‧ 2014-10-02 22:21:15

以前小朋友時期,有玩念一段句子,點到的要出去被罵還是先玩玩具,
要站成一個圈圈來數會比較方便喔.

0
dinochang
iT邦新手 4 級 ‧ 2014-10-03 16:32:08

重頭開始算時要先把已經選中的過濾掉,依剩下的排隊人數去挑選
所以結果會是2 6 10 5 1

1
pajace2001
iT邦研究生 1 級 ‧ 2014-10-03 20:35:14

dinochang 大大說的名錯,被選走的人就不會在原來的位置上了,所以在挑人的時候就自然挑不到被選走的人..也就是要跳過去...

0
pajace2001
iT邦研究生 1 級 ‧ 2014-10-03 20:35:46

打錯了,是說的「沒」錯! XD

0
海綿寶寶
iT邦超人 1 級 ‧ 2014-10-04 21:33:46

了解了
謝謝

0
holmes2136
iT邦新手 3 級 ‧ 2014-10-05 21:21:23

感覺有點像約瑟夫問題

我要留言

立即登入留言