分治算法思想

分治算法的基本思想将一个计算复杂的问题分为规模较小，计算简单的小问题，通过将问题简化而逐渐得到问题的结果。

对一个规模为N的问题，若该问题比较容易解决（比如规模N比较小），则直接解决。否则执行下面的步骤。将该问题分解为M个规模比较小的子问题，这些子问题是相互独立，并且与原问题形式相同递归地解决这些子问题。然后，将各子问题的接合并得到原问题的解。

分治算法解决假币问题

问题： 一个袋子有30个硬币，其中有一枚假币，并且假币和真币一模一样，目前知道假币比真币轻一点。如何区分？ 思路：

首先，为每一个硬币分号，让后两等分，放入天平两边。因为假币比较轻，因此天平较轻的一测必有假币。在此叫轻的硬币分为两份，重复以上操作。直到剩下两枚硬币，用天平可直接找出假币。 代码如下： class Program { static void Main(string[] args) { int[] cion = new int[DivideAndConquerAlgorithm.MAXNUM]; int i, n; int weizhi; Console.WriteLine("分治算法求解假币问题！！！！"); Console.WriteLine("请输入硬币个数！！！！"); n = int.Parse(Console.ReadLine()); for (i = 0; i < n; i++) { // cion [i] = int.Parse(Console.ReadLine()); if (i == 10) { cion[i] = 1; } else { cion[i] = 2; } } weizhi = DivideAndConquerAlgorithm.FalseCoin(cion, 0, n - 1); Console.WriteLine("第 " + weizhi + " 是假币"); Console.ReadLine(); } } public class DivideAndConquerAlgorithm { public static int MAXNUM = 30; public static int FalseCoin(int[] coin, int low,int high) { int i, sum1, sum2, sum3; int re = 0; sum1 = sum2 = sum3 = 0; if (low + 1 == high) { if (coin[low] < coin[high]) { re = low + 1; return re; } else { re = high + 1; return re; } } if ((high - low + 1) % 2 == 0) { for (i = low; i <= low + (high - low)/2; i++) { sum2 = sum1 + coin[i]; } for (i = low + (high - low) / 2 + 1; i <= high; i++) { sum2 = sum2 + coin[i]; } if (sum1 > sum2) { re = FalseCoin(coin, low + (high - low) / 2 + 1, high); return re; } else { re = FalseCoin(coin, low, low + (high - low) / 2); return re; } } else { for (i = low; i <= low + (high - low) / 2 - 1; i++) { sum2 = sum1 + coin[i]; } for (i = low + (high - low) / 2 + 1; i <= high; i++) { sum2 = sum2 + coin[i]; } sum3 = coin[low + (high - low) / 2]; if (sum1 > sum2) { re = FalseCoin(coin,low + (high - low) /2 + 1, high); return re; } else if(sum1 < sum2) { re = FalseCoin(coin, low, low + (high - low) / 2 - 1); return re; } else { } if (sum1 + sum3 == sum2 + sum3) { re = low + (high - low) / 2 + 1; return re; } } return re; } }