今天看到别人的面试算法题,求找出十包粉末中两包蓝色粉末的最短时间

题目:有4个杯子,10包粉末,其中有2包溶于水变蓝,其余无色,粉末溶于水2min才能显现颜色。求找出两包蓝色粉末的最短时间。假设水和粉末用不完。

方法一:

第一趟:[12,34,56,78]

每个杯子分别放两包加水融化,剩下两包不管。可能的情况:

(1)0个杯子变色,说明剩下两包就是蓝粉末

(2)1个杯子变色,则蓝粉末在这个杯子两包和未融化的两包其中两包,第二趟四包融化一定可以找到

(3)2个杯子变色,则在这两个杯子的四包粉末中,第二趟可找到。

时间均值:E = 2*1/45 + 4*44/45 = 178/45;

方法二:

第一趟:[123;456;78;910]

(1)1个杯子变蓝,如果是3或4号杯子蓝,则就是放入该杯子中的2种粉末,否则在变蓝的杯子的3种粉末中,局部时间均值E1 = 2*2/45 + 4*6/45 = 26/45

(2)2个杯子变蓝,

-如果是前两个杯子变蓝,第二趟放置[14;25;36;15],分析关系:杯子14有联系,24有联系。

a. 杯1变色而杯4不变则

-如果是前面两个杯子有一个变蓝,后两个杯子有一个变蓝,则5种粉末随机取四种放在四个杯子中看现象。

-如果后两个杯子变蓝,则4种粉末分别放在四个杯子中看现象就可以。

时间均值:E = 2*2/45 + 4*43/45 = 176/45;

方法三:

第一趟:[1234; 2567; 3689; 47910]

每个杯子只有一个独立的,每杯都与另外三杯有一个共同粉末(而且一包粉最多只能放在俩杯里),放置方法:1234放在杯子1,234分别放在杯234,567放在杯子2,67分别放杯子34...

(1)不可能只有一个杯子蓝,除了1 10,每包粉末都放在两个杯子里。

(2)两个杯子蓝: 则只能是这两个杯子共有而其他两个杯子无联系的。第一个蓝杯中有两包ab与两个非蓝杯有联系,另一蓝杯中有两包cd与两个非蓝杯有关系。abcd排除后剩下3包粉末。例如杯子12_[1234;2567]蓝,则可能是12,15,25, 局部时间均值E1 = 4*18/45 = 72/45;

(3)三个杯子蓝,则可以排除非蓝杯的四种粉末剩下六种可能;至少有一包是这三个蓝杯中两个杯子的共同颜色,例如杯子123_[1234;2567;3689]蓝,则有可能是16,23,26,28,35,36,局部时间均值E2 = 4*24/45 = 96/45;

(4)四个杯子蓝,则蓝色的粉末放在两个杯子中,且两包蓝色粉末没放在一起;则只能是29,37,46三种组合之一, 局部时间均值E3 = 4*3/45 = 12/45.

时间均值:E = 4;

方法四:枚举

  即每种粉末都放入杯中溶解一次,直到找到两包蓝色粉末,

  (1)仅一趟就成功找到两包蓝色粉末, 局部时间均值E1 = 2*6/45 = 12/45;

(2)两趟就成功找到两包蓝色粉末, 局部时间均值E2 = 4*23/45 = 92/45;

  (3)三趟才成功找到两包蓝色粉末, 局部时间均值E3 = 6*16/45 = 96/45;

时间均值:E = 200/45;

方法五:时间差

  通过间隔段时间投放不同的粉末,观察水体变蓝的时间来判断和确认蓝色粉末。

方法六:.......

时间: 02-26

今天看到别人的面试算法题,求找出十包粉末中两包蓝色粉末的最短时间的相关文章

算法——一天一道算法题篇——找只出现一次的两个数

找只出现一次的两个数 题目: 一个整型数组里除了两个数字只出现一次之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 举例说明: 现在有一个数组:{1,3,4,2,4,3}; 假设数组元素的规模不是很大,想要找到只出现一次的元素,可以定义一个辅助数组,flag[100];里面存放的是数组元素出现的次数,flag数组的下标表示的是数组:{1,3,4,2,4,3}里的元素. 代码如下: package hello.ant; public class AlogArrayFind2 {

算法题:找出整数数组中两个只出现一次的数字

问题:一个整数数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字.要求时间复杂度为O(n),空间复杂度为O(1). 分析:这是一个很新颖的关于位运算的题目. 首先考虑这个问题的一个简单版本:一个整数数组里除了一个数字之外,其他的数字都出现两次,请写程序找出这个只出现一次的数字. 这个问题的突破口在哪?题目中数组的性质是只有一个整数出现一次,其他的都出现两次.这样的话就使我们想到了异或运算的性质:任何一个数字异或它自己都等于0.也就是说如果从头到尾依次异或数组中的每

算法题之找出数组里第K大的数

问题:找出一个数组里面前K个最大数. 解法一(直接解法): 对数组用快速排序,然后直接挑出第k大的数.这种方法的时间复杂度是O(Nlog(N)).N为原数组长度. 这个解法含有很多冗余,因为把整个数组都排序了,而实际上我们不需要这样做. 解法二(K数组排序): 首先,创建一个长度为K的空数组.从原数组中先挑出K个数进行排序并放到这个空数组中.这一步的时间复杂度是O(Klog(K)). 接着,从剩下的N-K个值中,依次遍历并与上面数组的末尾的数(即里面的最大数)相比较,并插入到合适位置.这一步的时

算法题:找出一个数组中相加值最大的连续序列元素

package arithmetic; /** * @author SHI * 求一个数组中相加值最大的连续序列元素 */ public class MaxSequence { public static void main(String[] args) { int[] a=new int[]{-2,9,-3,4,-6,7,-6,4}; findBigSequence(a); } /** * 思想: (1)计算出该数组的所有元素和,假设该值为最大 * (2)从数组下标1到a.length-1依次

算法题:找出一个数组中依次最大的k个元素

package arithmetic; import java.util.Arrays; /** * 找出一个数组中依次最大的k个元素 * @author SHI */ public class FindMaxFigure { public static void main(String[] args) { int[] a=new int[]{1,5,-1,8,0,2}; System.out.println(Arrays.toString(findBigFigure(a, 3))); } /*

算法题:找出同一个序列中的最大值和最小值

package arithmetic; /** * 同时找出一个序列中最大值和最小值 * 分两种情况:(1)序列只有两个元素 * (2)序列有多个元素,有多个元素分别从序列的两端开始查找 * @author SHI */ public class MaxAndMin { public static void main(String[] args) { int[] a = { 122, 41, 4, 5, 7, 2, 89, 122, 34, 56 }; int low = 0; int high

偶然看到的面试算法题_最短时间找出十包粉末中的两蓝粉末。

题目:有4个杯子,10包粉末,其中有2包溶于水变蓝,其余无色,粉末溶于水2min才能显现颜色.求找出两包蓝色粉末的最短时间.假设水和粉末用不完. 解:以下给出四种解法,标记10包粉末为(1,2 ... ) 杯子为[1,2,3,4]首先我想会不会是有某种算法,dp 二分..@[email protected]..没有,懵懵的. 法一:这是我最初想到的比较傻的方法 第一趟:[12,34,56,78] 每个杯子分别放两包加水融化,剩下两包不管.可能的情况: (1)0个杯子变色,说明剩下两包就是蓝粉末

认真对待每一道算法题 之 找明星问题 - 淘宇瀚

n个人中只有一个明星,明星不认识其他所有的人,而其他人都认识明星,不是明星的人可能认识也可能不认识.你每次只可以问一个人是否认识另一个人这样的问题,问最少问多少次可以找出明星. 做法1: 将所有人站队,按照顺序(假如编号分别为1.2.3..n),首先问1,2互相认识,有四种情况出现: (1)1 认识 2,2不认识1, 认识别人的肯定不是明星,排除1: (2)1 不认识2,2认识1, 根据(1)的道理,同样可以排除2: (3)1与2 互相认识,可以断定,两个人都不是明星,随机删除一个就好: (4)

经典算法题每日演练——第十二题 线段树

原文:经典算法题每日演练--第十二题 线段树 这一篇我们来看树状数组的加强版线段树,树状数组能玩的线段树一样可以玩,而且能玩的更好,他们在区间求和,最大,平均 等经典的RMQ问题上有着对数时间的优越表现. 一:线段树 线段树又称"区间树”,在每个节点上保存一个区间,当然区间的划分采用折半的思想,叶子节点只保存一个值,也叫单元节点,所 以最终的构造就是一个平衡的二叉树,拥有CURD的O(lgN)的时间. 从图中我们可以清楚的看到[0-10]被划分成线段的在树中的分布情况,针对区间[0-N],最多有