# 北軟107 problemB

###### tags: `北軟107`

### 題目敘述：
大家或許都玩過一個大地遊戲，N 個人圍成一個圓圈，從第一個
人開始報數，照順序從 1 開始報數，當報到一個特定的數 M，例如 M=3，報數的那個人就被淘汰，淘汰的人就要離開圓圈，不能報數了。然後從下一個人開始從頭（1）報數，報到 3 的就淘汰。例如假設有 N=9 人（編號為 1~9）圍成一個圓圈圈，從 1 開始報數，報到 3 的就淘汰，如下圖，淘汰的順序是 3、6、9、4、8、5、2、7，最後勝利者是 1 號。

### 想法：
這題我們可以設計一個主控介面的程式，會比較簡便。
由於N,M的值都不超過100，所以我們可以暴力解這一題。
開一個bool陣列visited，存取哪些人已經被淘汰了。
接下來開一個迴圈，迴圈i=0,運行條件為淘汰人數不等於n-1，每次程式運行完i就+1，然後i同餘n(循環到i=0的概念)。

接下來迴圈內的程式，假設visited[i]是true，就跳過，意味著這個人已經被淘汰了。
如果沒有，報數就+1，假設報數+1後的數字等於M，就將visited[i]設為true，且報數歸零，淘汰人數+1，意味著編號為(i+1)的人從這場遊戲被淘汰了。

做完之後，我們再巡一次visited[i]，假設尋找到一個visited[i]=false，就代表編號為(i+1)的人沒被淘汰。

因此，我們就可以找到淘汰順序以及最後贏家。

這是一個很有名的問題，名為約瑟夫問題。
如果限制程式運行時間，本題將會變得更加困難。

### 程式碼(C#)：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace problemB
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m;
            Console.Write("請輸入N人數：");
            string split = Console.ReadLine();
            n = Convert.ToInt16(split);
            Console.Write("請輸入M報數：");
            split = Console.ReadLine();
            m = Convert.ToInt16(split);
            run(n, m);
        }
        static void run(int n,int k)
        {
            bool[] visited = new bool[n];
            for (int i = 0; i < n; visited[i] = false, i++) ;
            int count = 0;
            int kick = 0;
            int a = 0;
            Console.Write("淘汰順序：");
            for(int i = 0; kick != n-1; i++,i%=n)
            {
                a++;
                if (visited[i] == true) continue;
                count++;
                if(count == k)
                {
                    kick++;
                    count = 0;
                    visited[i] = true;
                    Console.Write(i+1 + " ");
                }
            }
            Console.WriteLine();
            Console.Write("最後贏家：");
            for(int i = 0; i < n; i++)
            {
                if(visited[i] == false)
                {
                    Console.WriteLine(i+1);
                    break;
                }
            }
            Console.WriteLine();
        }
    }
}