约瑟夫环是一个数学的应用问题:已知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(); } } }
|