圆桌问题 明

2013-03-23

圆桌问题：圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死…依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人

简化版：圆桌上坐着n个人，从第一个开始计数，偶数的人推出，最后剩下那个位置的人。

思路：数据结构，首先想到了C#提供的System.Collections.IList,思路很简单，foreach IList中每个记录，count用来计数，若count为偶数，删除之。但想到微软面试要用基元类型，想到两种类型：一个是用数组，一个自定义LinkList，而且要实现Iretator模式，下面是数据结构代码：

public interface IMyEnumerator<T>
{
    int Length { get; }
    T Current { get; }
    bool MoveNext();
    void Reset();
    void Remove(T element);
}

//以数组结构存储数据，Length为实际记录数，Remove一个元素后，其后的记录向前移，Current为当前指向记录
public class SqArray1 : IMyEnumerator<int>
{
    int[] _arr;
    int _validLength;
    int _index;
    public SqArray1(int[] arr)
    {
        _arr = new int[arr.Length];
        arr.CopyTo(_arr, 0);
        _validLength = arr.Length;
        _index = 0;
    }
    public int Length
    {
        get { return _validLength; }
    }

    public void Remove(int data)
    {
        for (int i = 0; i < _validLength; i++)
        {
            if (_arr[i] == data)
            {
                for (int j = i; j < _validLength - 1; j++)
                {
                    _arr[j] = _arr[j + 1];
                }
                _validLength--;
                //删除了一个记录，index向前移一位使current指向删除记录的前一个记录
                _index = i - 1;
            }
        }
    }
    public void Reset()
    {
        _index = 0;
    }
    public bool MoveNext()
    {
        if (_index < _validLength - 1)
        {
            _index = _index + 1;
            return true;
        }
        return false;

    }
    public int Current
    {
        get { return _arr[_index]; }
    }
}

//以数组结构存储数据，Length为实际记录数，Remove一个元素后，其记录项的值设为0，Current为当前指向记录
public class SqArray2 : IMyEnumerator<int>
{
    int[] _arr;
    int _validDataNumber;
    int _index;

    public SqArray2(int[] arr)
    {
        _arr = new int[arr.Length];
        arr.CopyTo(_arr, 0);
        _validDataNumber = _arr.Length;
        _index = 0;
    }
    public int Length
    {
        get { return _validDataNumber; }
    }

    public void Remove(int data)
    {
        for (int i = 0; i < _arr.Length; i++)
        {
            if (_arr[i] == data)
            {
                _arr[i] = 0;
                _validDataNumber--;
                //因为当前记录被删了，这里需要设置_current，使它指向前一个有效记录
            }
        }
    }
    public bool MoveNext()
    {
        for (int loc = _index + 1; loc < _arr.Length; loc++)
        {
            if (_arr[loc] != 0)
            {
                _index = loc;
                return true;
            }
        }
        return false;
    }
    public void Reset()
    {
        for (int loc = 0; loc < _arr.Length; loc++)
        {
            if (_arr[loc] != 0)
            {
                _index = loc;
                break;
            }
        }
    }
    public int Current
    {
        get
        {
            return _arr[_index];
        }
    }
}

public class LNode
{
    public LNode Next;
    public int Value;
    public LNode(int value) : this(value, null) { }
    public LNode(int value, LNode next)
    {
        Next = next;
        Value = value;
    }
}
//带有头结点的链表结构
public class LinkList : IMyEnumerator<LNode>
{


    private LNode _head, _tail;
    private int _length;
    private LNode _current;

    public int Length
    {
        get { return _length; }
    }

    public LinkList()
    {
        _head = _tail = new LNode(-1);
    }
    public LinkList(int[] arr)
        : this()
    {
        for (int i = 0; i < arr.Length; i++)
        {
            Add(arr[i]);
        }
    }
    public void Add(int data)
    {
        _tail.Next = new LNode(data);
        _tail = _tail.Next;
        _length++;
    }
    public LNode Current
    {
        get
        {
            return _current;
        }
    }
    public void Remove(LNode lNode)
    {
        if (_head == null)
            throw new ArgumentOutOfRangeException();
        else
        {
            LNode p = _head;
            while (p.Next != null)
            {
                if (p.Next.Value == lNode.Value)
                {
                    _current = p;
                    p.Next = p.Next.Next;
                    _length--;
                    return;
                }
                p = p.Next;
            }

        }
    }
    public bool MoveNext()
    {
        if (_current.Next != null)
        {
            _current = Current.Next;
            return true;
        }
        return false;
    }

    public void Reset()
    {
        _current = _head.Next;
    }
}

客户端代码（包括测试数据和算法）：

public class Program
{
    public static void Main(string[] args)
    {
        //Black box testing (equivalence divsion,bounary value)
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
        //arr = new int[] { 1, 2, 3, 4 };    //even number
        //arr = new int[] { 1, 2, 3, 4, 5 }; //odd number
        //arr = new int[] { 1, 3, 2, 4 };    //mix the ordering up
        //arr = new int[] { 1, 2, 3, 5 };    //miss a number

        //arr = null;              //array is null
        //arr = new int[] { -1 };  //number is negative number
        //arr = new int[] { 0 };   //number is zero
        //arr = new int[] { int.MaxValue};  //bounary test
        //arr = new char[] { 'a',/0 };  //different type


        SqArray1 myArr = new SqArray1(arr);
        Suanfa(myArr);
        Console.WriteLine(myArr.Current.ToString());

        Suanfa(myArr);
        Console.WriteLine(myArr.Current.ToString());

        LinkList myList = new LinkList(arr);
        Suanfa(myList);
        Console.WriteLine(myList.Current.Value.ToString());
        Console.Read();
    }

    public static void Suanfa<T>(IMyEnumerator<T> myList)
    {
        int count = 0;
        while (myList.Length > 1)
        {
            myList.Reset();
            do
            {
                count++;
                if (count % 2 == 0)
                {
                    myList.Remove(myList.Current);
                }
            }
            while (myList.MoveNext());
        }
        myList.Reset();
    }
}