20分送上 减治法解决8枚硬币问题 !!!
减治法:题目:在8枚外观相同的硬币中,有一枚是假币,并且已知假币真币的重量不同,假设假币比真币的重量轻,可以通过一架天平来比较检测,设计一个高效的算法来检测这枚假币!!!!
求用c#写的这 8枚硬币的算法!!!
//获取假币索引 private int GetMinIndex(int[] array) { if (array.Length != 8) { return -1; } List<int> list = new List<int>(); for (int i = 0; i < array.Length; i++) { list.Add(i); } //天平算法,3次结束 while (list.Count > 1) { int a = 0; int b = 0; for (int i = 0; i < list.Count / 2; i++) { a += array[list[i]]; } for (int i = list.Count / 2; i < list.Count; i++) { b += array[list[i]]; } if (a > b) { list.RemoveRange(0, list.Count / 2); } else { list.RemoveRange(list.Count / 2, list.Count / 2); } } return list[0]; } //测试 private int Test() { int[] array = new int[8] { 2, 2, 2, 1, 2, 2, 2, 2 }; return GetMinIndex(array); }
class Program { /// <summary> /// 判断真币假币,假币轻,则两数相比为较小的 /// </summary> /// <param name="a">第一个数</param> /// <param name="b">第二个数</param> /// <returns>第一个数是假币返回1,第二个数是假币返回2,都是真币返回-1</returns> public int CheckMin(int a, int b) { if (a < b) { return 1; } else if (a > b) { return 2; } else { return -1; } } static void Main(string[] args) { //真币为1,假币为0,顺序任意 int[] arr = new int[] { 1, 1, 1, 1, 1, 0, 1, 1 }; Program pro = new Program(); //将8个硬币找假币,减少为2个硬币找假币,从头到尾循环一下就找出假币了,当然算法不是最高效 for (int i = 0; i < arr.Length - 1; i++) { int min = pro.CheckMin(arr[i], arr[i + 1]); if (min != -1) { Console.WriteLine("第" + (i + min) + "个是假币"); break; } else { i++; } } Console.Read(); } }