一個(gè)翻牌算法

本周四同事分享了一個(gè)思維訓(xùn)練的PPT，里面有一個(gè)關(guān)于翻牌的題目，題目大致是：拿出從A到10的10張撲克牌，背面朝上摞在一起。首先把最上面的一張挪到下面，掀開新出現(xiàn)的一張牌是A，取出，再挪一張牌到下面，翻一張是2，依次類推，可以有順序地翻出A到10的牌來。請(qǐng)問這10張牌最初是怎么排列的？看完這個(gè)題目，我當(dāng)時(shí)說可以用一個(gè)算法實(shí)現(xiàn)。

第二天6點(diǎn)多醒來就一直在想這個(gè)問題，開始的時(shí)候想用遞歸實(shí)現(xiàn)，最后發(fā)現(xiàn)有點(diǎn)復(fù)雜，自己實(shí)現(xiàn)不了，然后想用數(shù)組實(shí)現(xiàn)，想法大致是這樣的，先將這N個(gè)數(shù)存到數(shù)組中，然后將第一張插到最后面，第二張為A，以此類推，將每張牌經(jīng)過的索引都記下來，因?yàn)槊繌埮谱詈笫菐资侵赖模缓蠓赐瞥?~N張牌是多少，但是發(fā)現(xiàn)記錄牌經(jīng)過的索引有點(diǎn)麻煩，效率也不高，記錄的數(shù)組的第一個(gè)元素即為所求。

早上到了公司一邊干活，一邊實(shí)現(xiàn)這個(gè)算法，從題目可以很容易看出奇數(shù)位一次為1~N/2,剩下的就是求偶數(shù)位的值，馬上寫了個(gè)算法，運(yùn)行是發(fā)現(xiàn)有的結(jié)果是正確的，大部分是錯(cuò)的，于是寫了個(gè)測試方法，測試方法就很簡單了，這個(gè)方法只用模擬翻牌的過程，然后輸出的結(jié)果為1~N就是正確的，否則就是錯(cuò)誤的。經(jīng)測試發(fā)現(xiàn)我的算法思路完全是錯(cuò)誤的，但是通過這個(gè)測試算法，我發(fā)現(xiàn)了能夠正確實(shí)現(xiàn)這個(gè)題目的方法。這個(gè)題目其實(shí)不是一個(gè)遞歸的過程，而是一個(gè)進(jìn)棧出棧的過程，奇數(shù)位進(jìn)棧，偶數(shù)位出棧。我們知道最后的結(jié)果，把每張牌當(dāng)做一個(gè)對(duì)象，就是進(jìn)棧出棧都是以引用的方式，翻牌完成后，按順序?qū)⑺鼈兊闹狄淮钨x值為1~N，那么我們也就知道開始的牌的順序了，就這么簡單，思路就這么簡單，實(shí)現(xiàn)起來也就很快，于是馬上實(shí)現(xiàn)了一個(gè)粗糙算法，最后用一個(gè)Window Form實(shí)現(xiàn)了，發(fā)給了同事看看，為了讓大家能看得清楚，記錄了翻牌的過程，當(dāng)然要記錄過程也是很簡單的。

代碼真的很簡單，將每張牌當(dāng)做一個(gè)對(duì)象，這樣就不用記錄牌經(jīng)過的過程，引用類型嗎！創(chuàng)建的對(duì)象的個(gè)數(shù)為N，過程也是線性的，不會(huì)有性能問題。

主要代碼如下（代碼很粗糙，但思路簡單清晰，我們知道就是對(duì)的），源碼下載

 //將牌定義成對(duì)象
        public class Card
        { 
            public int Value=0 ;
            public override string ToString()
            {
                return Value.ToString();
            } 
        }

        //測試算法，記錄了翻牌過程
        static List<string> TestResult(Card[] arr)
        {
            if (arr == null)
            { 
               throw new Exception("參數(shù)異常");
            }
            int len = arr.Length;
            Queue<Card> queue = new Queue<Card>(len);
            foreach (Card i in arr)
            {
                queue.Enqueue(i);
            }
            List<string> list = new List<string>(len);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++)
            {
                list.Add(GetItem(sb.ToString(),queue));
                Card cur = queue.Dequeue();
                queue.Enqueue(cur);
                sb.Append(queue.Dequeue().ToString().PadRight(3,' ')+"  ");
            }
            return list;
        }

        static string GetItem(string s,Queue<Card> queue)
        { 
            StringBuilder sb = new StringBuilder(s);
            foreach (var item in queue)
            {
                sb.Append(item.ToString().PadRight(3, ' ') + "  ");
            }
            return sb.ToString();
        }

        //實(shí)現(xiàn)翻牌的算法
        static Card[] TestArr(int size)
        {
            Card[] arr = new Card[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = new Card();
            }
            int len = arr.Length;
            Queue<Card> queue = new Queue<Card>(len);
            foreach (Card i in arr)
            {
                queue.Enqueue(i);
            }
            for (int i = 1; i <= len; i++)
            {
                Card cur = queue.Dequeue();
                queue.Enqueue(cur);
                cur = queue.Dequeue();
                cur.Value = i;
            }
            return arr;
        }

幾個(gè)截圖，如果題目我說得不清楚，下面幾張圖應(yīng)該可以讓大家看得更明白

posted @ 2012-09-16 12:16 古文觀芷閱讀(3834) 評(píng)論(9) 收藏舉報(bào)

刷新頁面返回頂部

一個(gè)翻牌算法

公告