约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

例如:

n = 9, k = 1, m = 5

【解答】

出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using System;
using System.Collections.Generic;
using System.Text;
namespace Jose
{
class Program
{
public int[] Jose(int total, int start, int num)
{
int i;
int j;
int k;
int[] count; //记录出队列的顺序
int[] people; //记录玩家编号
j = 0;
k = 0;
count = new int[total];
people = new int[total + 1];
for (i = 0; i < total; i++) //给玩家编号
{
people[i] = i;
}
for (i = total; i > 1; i--)
{
start = (start + num - 1) % i;
if (start == 0)
start = i; //找到出队玩家
count[k++] = people[start]; //记录出队玩家
for (j = start + 1; j <= i; j++)
people[j - 1] = people[j]; //玩家出队,调整剩余玩家
}
count[k] = people[1];
return count;
}
static void Main(string[] args)
{
Program game = new Program();
int[] result = game.Jose(9, 0, 5);
foreach (int o in result)
{
Console.WriteLine("编号为: " + o + " 的玩家出队");
}
Console.ReadKey();
}
}
}