分治法-找假币问题

亦凉 2022-11-18 13:49 8阅读 0赞

#### 一、分治法 ####

将一个复杂的问题分为规模较小的问题，计算简单的小问题求解，然后综合小问题，得到最终的答案。

##### 基本思路 #####

*  对于一个规模为N的问题，若该问题可以很容易的解决，则直接解决，否则执行下面操纵
 *  将该问题分解成M个规模较小的问题，这些子问题互相独立，并且与原问题形式相同
 *  地柜的求解子问题
 *  然后将各个问题的解合并到原问题的解

#### 二、假币问题 ####

假币问题：有n枚硬币，其中有一枚是假币，己知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。

##### 分析 #####

*  首先为每个币编号，然后将所有的币等分为两份，放在天平的两边。这样就将区分假币的问题变为区别两堆币的问题。
 *  因为假币分量较轻，因此天平较轻的一侧中一定包含假币。
 *  再将较轻的一侧中币等分为两份，重复上述做法。
 *  直到剩下两枚银币，便可用天平直接找出假币。

##### java程序算法 #####

public class CheckMoney { 
        public static void main(String[] args) { 
            int[] arr = { 2,2,2,2,2,1};
            int pos = checkMoney(arr, 0, arr.length - 1);
            System.out.println("位置:"+pos);
        }
        //检查
        public static int checkMoney(int arr[],int left,int right) { 
            int sum1 = 0, sum2 = 0, sum3 = 0;
            if ((right - left + 1) % 2 == 0) { //数组为偶数
                if (left + 1 == right) { 
                    if (arr[left] < arr[right]) { //当前剩下两个数,进行比较
                        return left;
                    } else { 
                        return right;
                    }
                } else { //数组里面多于2个数
                    int mid = (right - left + 1) / 2 + left;//找出中间位置
                    for (int i = left; i < mid; i++) { 
                        sum1 += arr[i];//中间靠左的数组集合总和
                        sum2 += arr[right - (i - left)];//中间靠右的数组集合总和
                    }
                    if(sum1<sum2){ 
                        return checkMoney(arr,left,mid-1);
                    }else { 
                        return checkMoney(arr,mid,right);
                    }
                }
            } else { //数组为奇数
                int mid = (right - left) / 2 + left;//找出中间位置
                for (int i = left; i < mid; i++) { 
                    sum1 += arr[i];//中间靠左的数组集合总和
                    sum2 += arr[right - (i - left)];//中间靠右的数组集合总和
                }
                if(sum1<sum2){ 
                    return checkMoney(arr,left,mid-1);
                }else if(sum1>sum2) { 
                    return checkMoney(arr,mid+1,right);
                }else { 
                    return mid;
                }
            }
        }
    }