2013-03-23
圆桌问题：圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死…依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人
简化版：圆桌上坐着n个人，从第一个开始计数，偶数的人推出，最后剩下那个位置的人。
思路：数据结构，首先想到了C#提供的System.Collections.IList,思路很简单，foreach IList中每个记录，count用来计数，若count为偶数，删除之。但想到微软面试要用基元类型，想到两种类型：一个是用数组，一个自定义LinkList，而且要实现Iretator模式，下面是数据结构代码：
View Code 1 public interface IMyEnumerator2 { 3 int Length { get; } 4 T Current { get; } 5 bool MoveNext(); 6 void Reset(); 7 void Remove(T element); 8 } 9 10 //以数组结构存储数据，Length为实际记录数，Remove一个元素后，其后的记录向前移，Current为当前指向记录 11 public class SqArray1 : IMyEnumerator 12 { 13 int[] _arr; 14 int _validLength; 15 int _index; 16 public SqArray1(int[] arr) 17 { 18 _arr = new int[arr.Length]; 19 arr.CopyTo(_arr, 0); 20 _validLength = arr.Length; 21 _index = 0; 22 } 23 public int Length 24 { 25 get { return _validLength; } 26 } 27 28 public void Remove(int data) 29 { 30 for (int i = 0; i < _validLength; i++) 31 { 32 if (_arr[i] == data) 33 { 34 for (int j = i; j < _validLength - 1; j++) 35 { 36 _arr[j] = _arr[j + 1]; 37 } 38 _validLength--; 39 //删除了一个记录，index向前移一位使current指向删除记录的前一个记录 40 _index = i - 1; 41 } 42 } 43 } 44 public void Reset() 45 { 46 _index = 0; 47 } 48 public bool MoveNext() 49 { 50 if (_index < _validLength - 1) 51 { 52 _index = _index + 1; 53 return true; 54 } 55 return false; 56 57 } 58 public int Current 59 { 60 get { return _arr[_index]; } 61 } 62 } 63 64 //以数组结构存储数据，Length为实际记录数，Remove一个元素后，其记录项的值设为0，Current为当前指向记录 65 public class SqArray2 : IMyEnumerator 66 { 67 int[] _arr; 68 int _validDataNumber; 69 int _index; 70 71 public SqArray2(int[] arr) 72 { 73 _arr = new int[arr.Length]; 74 arr.CopyTo(_arr, 0); 75 _validDataNumber = _arr.Length; 76 _index = 0; 77 } 78 public int Length 79 { 80 get { return _validDataNumber; } 81 } 82 83 public void Remove(int data) 84 { 85 for (int i = 0; i < _arr.Length; i++) 86 { 87 if (_arr[i] == data) 88 { 89 _arr[i] = 0; 90 _validDataNumber--; 91 //因为当前记录被删了，这里需要设置_current，使它指向前一个有效记录 92 } 93 } 94 } 95 public bool MoveNext() 96 { 97 for (int loc = _index + 1; loc < _arr.Length; loc++) 98 { 99 if (_arr[loc] != 0)100 {101 _index = loc;102 return true;103 }104 }105 return false;106 }107 public void Reset()108 {109 for (int loc = 0; loc < _arr.Length; loc++)110 {111 if (_arr[loc] != 0)112 {113 _index = loc;114 break;115 }116 }117 }118 public int Current119 {120 get121 {122 return _arr[_index];123 }124 }125 }126 127 public class LNode128 {129 public LNode Next;130 public int Value;131 public LNode(int value) : this(value, null) { }132 public LNode(int value, LNode next)133 {134 Next = next;135 Value = value;136 }137 }138 //带有头结点的链表结构139 public class LinkList : IMyEnumerator 140 {141 142 143 private LNode _head, _tail;144 private int _length;145 private LNode _current;146 147 public int Length148 {149 get { return _length; }150 }151 152 public LinkList()153 {154 _head = _tail = new LNode(-1);155 }156 public LinkList(int[] arr)157 : this()158 {159 for (int i = 0; i < arr.Length; i++)160 {161 Add(arr[i]);162 }163 }164 public void Add(int data)165 {166 _tail.Next = new LNode(data);167 _tail = _tail.Next;168 _length++;169 }170 public LNode Current171 {172 get173 {174 return _current;175 }176 }177 public void Remove(LNode lNode)178 {179 if (_head == null)180 throw new ArgumentOutOfRangeException();181 else182 {183 LNode p = _head;184 while (p.Next != null)185 {186 if (p.Next.Value == lNode.Value)187 {188 _current = p;189 p.Next = p.Next.Next;190 _length--;191 return;192 }193 p = p.Next;194 }195 196 }197 }198 public bool MoveNext()199 {200 if (_current.Next != null)201 {202 _current = Current.Next;203 return true;204 }205 return false;206 }207 208 public void Reset()209 {210 _current = _head.Next;211 }212 }
客户端代码（包括测试数据和算法）：
View Code 1 public class Program 2 { 3 public static void Main(string[] args) 4 { 5 //Black box testing (equivalence divsion,bounary value) 6 int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 7 //arr = new int[] { 1, 2, 3, 4 }; //even number 8 //arr = new int[] { 1, 2, 3, 4, 5 }; //odd number 9 //arr = new int[] { 1, 3, 2, 4 }; //mix the ordering up10 //arr = new int[] { 1, 2, 3, 5 }; //miss a number11 12 //arr = null; //array is null13 //arr = new int[] { -1 }; //number is negative number14 //arr = new int[] { 0 }; //number is zero15 //arr = new int[] { int.MaxValue}; //bounary test16 //arr = new char[] { 'a',/0 }; //different type17 18 19 SqArray1 myArr = new SqArray1(arr);20 Suanfa(myArr);21 Console.WriteLine(myArr.Current.ToString());22 23 Suanfa(myArr);24 Console.WriteLine(myArr.Current.ToString());25 26 LinkList myList = new LinkList(arr);27 Suanfa(myList);28 Console.WriteLine(myList.Current.Value.ToString());29 Console.Read();30 }31 32 public static void Suanfa (IMyEnumerator myList)33 {34 int count = 0;35 while (myList.Length > 1)36 {37 myList.Reset();38 do39 {40 count++;41 if (count % 2 == 0)42 {43 myList.Remove(myList.Current);44 }45 }46 while (myList.MoveNext());47 }48 myList.Reset();49 }50 }