0019-约瑟夫问题

问题描述

约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n) ,从第1号开始报数, 一直数到m,数到m的猴子退出圈外, 剩下的猴子再接着从 1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入

每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m, n < 300)。最后一行是:0 0

输出

对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号

输入样列

6 2
12 4
8 3
0 0

输出样例

5
1
7

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
             while (true) {
                string input = Console.ReadLine();
                string[] data = input.Split();
                int n = int.Parse(data[0]);
                int m = int.Parse(data[1]);
                if (n == 0 && m == 0)
                    break;
                int[] num = new int[n];
                int flag = n;
                int i = 0,k=0;
                while (flag != 1) {
                    if (num[i]==0) {
                        k++;
                        if (k == m) {
                            num[i] = 1;
                            k = 0;
                            flag--;
                        }
                    }
                    i=(i+1)%n;
                }
                for (i = 0; i < n; i++)
                    if (num[i] == 0)
                        Console.WriteLine(i+1);
            }
            Console.ReadKey();
        }
    }
}