c#约瑟夫环

2012-03-13 约 442 字预计阅读 1 分钟

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

目录

c#约瑟夫环