約瑟夫環的數組

最近忙著提升自身的訪談能力，美其曰：“提高自身的業務能力”，兩字呵呵。感覺在公司前途一片黑暗，連絲曙光都不見，好在我有一顆強大的?，感謝mother 。因為模擬對象中有一位學習中等，在班中揚言..... 此處略去一百字，所以我就想到自己教過的學生中就有這么一位。 然后就和他QQ聊了兩句，我怎么能這么敬業呢O__O"…。 沒想到該學生現在準備學IOS，IOS可是我一直想去學沒學的技術啊，簡直帥爆了。 今天早上他給我發了一道題：約瑟夫環的數組實現。為了打發我郁悶苦逼的心情和大把的時間，做了一下。 最后發現網上有寫好的demo比我的要好，于是乎我就重新整理，添加了注釋。題和正解如下：

約瑟夫環的數組實現

約瑟夫(Josephus)問題是由古羅馬的史學家約瑟夫提出的,他參加并記錄了公元 66-70 年猶太人反抗羅馬的起義。約瑟夫作為一個將軍,設法守住了裘達 伯特城達 47 天之久,在城市淪陷之后,他和 40 名將士在附近的一個洞穴中避難。在哪里,將士們群情激奮并表示:要投降毋寧死。于是,約瑟夫建議每個人輪流殺死他旁邊的人,而這個順序是由抽簽決定的。約瑟夫有預謀地抓到了最后一簽并且做為洞穴中兩個幸存者之一生存下來。

約瑟夫環問題的具體描述是:設有編號為 1,2,......,n 的 n(n>0)個人圍成一 個圈,從第一個人開始報數,報到 m 時停止報數,報 m 的人出圈,再從他的 下一個人起重新報數,

報到 m 時停止報數,報 m 的出圈,......,如此下去,知道只剩下一人為止。當任意給定 n 和 m 后,設計算法求 n 個人出圈的次序。

假設有n=5 ,5個人： 1 ，2 ， 3， 4， 5 ，

從第1個人開始報數字， 如果報的數字m為 2， 這個人被同伴殺死，出局被殺死人的順序是： 2, 4, 3, 1, 5

代碼如下

 1  /// <summary> 2         /// 約瑟夫環的數組實現 3         /// </summary> 4         /// <param name="n">總人數</param> 5         /// <param name="m">從編號為幾開始數數</param> 6         /// <param name="k">數到幾的人出局</param> 7         public  static void Josehp(int n, int m, int k) 8         {    9 10             //創建一個和總人數相同長度的數組11             int[] array = new int[n];12             for (int i = 0; i < n; i++)13             {14                 array[i] = i + 1; //循環給每一個數組元素賦值，編號為 1, 2, 3, 4 ,...., n 15             }16 17 18             int count = 0; //記錄數數的標號19 20             int number = n; //記錄剩余的總人數21 22             while (number > 1)23             {24                 for (int i = 0; i < n; i++) //循環遍歷數據里面的每一個元素25                 {26                     if (m != 1) //如果不是從編號1開始27                     {28                         i = m - 1;  //從 m 為的成員開始， m 為的這個人 為第1個人29                         m = 1;30                     }31                     if (array[i] == 0) //判斷array[i] 這個人是否已經出局，如果出局，繼續循環，判斷下一位32                         continue;33                     count++;34                     if (count == k) //如果要數的數字與出局數字相同35                     {36                         Console.Write(array[i] + " "); //輸出出局的編號37                         array[i] = 0; //將該位置標記為038                         count = 0; //數數標號從0開始39                         number--; //總人數 -1 40                     }41                 }42             }43 44 45             //循環判斷不為0的元素，即為最終留下的人46             for (int i = 0; i < n; i++)47             {48                 if (array[i] != 0)49                 {50                     Console.Write(array[i]);51                     break;52                 }53             }54 55             Console.WriteLine();56         }

 1   static void Main(string[] args) 2         { 3             Console.WriteLine("請輸入總人數："); 4             int m = int.Parse(Console.ReadLine()); 5              6             Console.WriteLine("請輸入報數："); 7             int n = int.Parse(Console.ReadLine()); 8  9             Console.Write("總人數是{0}, 從第{1}個人開始數數, 數到{2}時出局，出局人的順序是：",m,1,n);10             Josehp(m,1,n);11 12             Console.ReadLine();13         }