电脑和手机都能浏览的网站开发,设计学类包括哪些专业,长沙网站建设+个人,个人网站备案能几个八枚硬币问题 在八枚外观相同的硬币中#xff0c;有一枚是假币#xff0c;并且已知假币与真币的重量不同#xff0c;但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币#xff0c;设计一个高效的算法来检测出这枚假币。 我们先假设一个条件#xf… 八枚硬币问题 在八枚外观相同的硬币中有一枚是假币并且已知假币与真币的重量不同但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币设计一个高效的算法来检测出这枚假币。 我们先假设一个条件已知假币比真币轻 二分查找算法实现时间复杂度(O(log(以2为底n的对数))) 思路把n枚硬币分成两堆每堆有枚硬币如果n为奇数的话就留下一枚额外的硬币然后把两堆硬币放在天平上。如果两堆硬币重量相同那么放在旁边的硬币就是假币否则我们可以用同样的方式对较轻的一堆硬币进行处理这堆硬币中一定包含那枚假币。注意即使我们把硬币分成了两个子集但在每次称重之后我们只需要解决一个规模为原来一半的问题。所以这是一个减治算法而不是一个分治算法。 public class Main {static int[] a {2, 2, 2, 2, 2, 2, 1, 2};public static void main(String[] args) {int l 0;int r a.length-1;System.out.println(f2(l, r));}private static int f2(int l, int r) {int n r - l 1;int mid (lr) / 2;if(n 1) {return l;}/*** n为总个数mid为中值* n为偶数则将n枚硬币分成两堆数量相等的硬币对轻的一堆迭代称重* n为奇数留下一枚硬币对n-1枚硬币按偶数继续操作* */if (n % 2 0) {if (sum(l, mid) sum(mid1, r)) {return l - 1;} else if (sum(l, mid) sum(mid1, r)){return f2(l, mid);} else {return f2(mid1, r);}} else {return f2(l1, r);}}/*** 获取指定区域内硬币的重量* */private static int sum(int l, int r) {int sum 0;for (int i l; i r; i) {sum a[i];}return sum;}
} 三分查找算法实现时间复杂度(O(log(以3为底n的对数))) 思路将n枚硬币分成三组前两组有组硬币其余的硬币作为第三组将前两组硬币放到天平上如果它们的重量相同则假币一定在第三组中用同样的方法对第三组进行处理如果前两组的重量不同则假币一定在较轻的那一组中用同样的方法对较轻的那组硬币进行处理。这也是一个减治算法。 public class Main {static int[] a {2, 2, 2, 2, 2, 2, 1, 2};public static void main(String[] args) {int l 0;int r a.length-1;System.out.println(f3(l, r));}private static int f3(int l, int r) {int n r - l 1;int x;if(n 1) {return l;}/*** n为总个数* 将n分成n/3, n/3, n-2(n/3)三堆硬币* 对前两堆称重相等则对第三堆继续操作不相等则对轻的一堆继续操作* */if (n % 3 0) {x n / 3;} else {x n / 3 1;return f3(l1, r);}int mid1 l x - 1;int mid2 mid1 x;if (sum(l, mid1) sum(mid11, mid2)) {return f3(mid21, r);} else if (sum(l, mid1) sum(mid11, mid2)){return f3(l, mid1);} else {return f3(mid11, mid2);}}/*** 获取指定区域内硬币的重量* */private static int sum(int l, int r) {int sum 0;for (int i l; i r; i) {sum a[i];}return sum;}
} 二分查找算法适用于单调的一个函数即数组序列要么升序要么降序 而三分查找算法使用于凸函数常用来求极值问题。 在假币问题中三分查找在n较大的情况下效率是优于二分查找的。 最复杂的情况
下面来回到最开始的问题在不知道假币轻重的情况下我们通过下面的算法来实现其时间复杂度为O(log(以2为底n的对数)) 相比来说这种情况思考起来比较复杂但是好在逻辑清楚只要理解了思路算法还是好实现的下面我们来举一个例子假设有八枚硬币其中有一枚硬币是假币。但是我们不知道假币是比真币重还是轻。先把八枚硬币编号分别表示为abcdefgh从八枚硬币中任取六枚abcdef在天平两端各放三枚进行比较。假设abc三枚放在天平的一端def三枚放在天平的另一端可能出现三种比较结果
⑴ abcdef
⑵ abcdef
⑶ abcdef
若abcdef可以肯定这六枚硬币中必有一枚为假币同时也说明g、h为真币。这时可将天平两端各去掉一枚硬币假设去掉c、f同时将天平两端的硬币各换一枚假设硬币b、e作了互换然后进行第二次比较比较的结果同样可能有三种
① aedb这种情况表明天平两端去掉硬币c、f且硬币b、e互换后天平两端的轻重关系保持不变从而说明了假币必然是ad中的一个这时我们只要用一枚真币例如h和a进行比较就能找出假币。若ah则a是较重的假币若ah则d为较轻的假币不可能出现ah的情况。为什么很简单因为我们判断了ad中有一个假币那么eb都是真币则ed。而aedb可以推出ad所以不管a是真是假都不可能出现ah情况出现
② aedb此时天平两端由不平衡变为平衡表明假币一定在去掉的两枚硬币cf中同样用一枚真币例如h和c进行比较若ch则c是较重的假币若ch则f为较轻的假币不可能出现ch的情况。
③ aedb此时表明由于两枚硬币be的对换引起了两端轻重关系的改变那么可以肯定b或e中有一枚是假币同样用一枚真币例如h和b进行比较若bh则b是较重的假币若bh则e为较轻的假币不可能出现bh的情况。 public class Main {static int[] a {2, 2, 2, 2, 2, 2, 1, 2};static int flag 0;public static void main(String[] args) {int p;if (sum(0, 2) sum(3, 5)) {p fp(6, 7);} else if (sum(0, 2) sum(3, 5)){if (a[0] a[4] a[3] a[1]) {p fp(0, 3);} else if (a[0] a[4] a[3] a[1]) {p fp(2, 5);} else {p fp(1, 4);}} else {if (a[0] a[4] a[3] a[1]) {p fp(1, 4);} else if (a[0] a[4] a[3] a[1]) {p fp(2, 5);} else {p fp(0, 3);}}if (flag 1) {System.out.println(假币轻为第 p 枚);} else {System.out.println(假币重为第 p 枚);}}private static int fp(int l, int r) {int H, L;int x (l1) % 8;if(a[l] a[r]) {H l;L r;} else {H r;L l;}if (a[H] a[x]) {flag 1;return H;} else {flag -1;return L;}}/*** 获取指定区域内硬币的重量* */private static int sum(int l, int r) {int sum 0;for (int i l; i r; i) {sum a[i];}return sum;}
}
