|
锁定老帖子 主题：几道比较有深度的题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-10-06
1。现有一百层高楼和两个棋子，棋子从X层上掉落摔到地面刚好摔碎（即X层以下是摔不碎的）
请问至少需要多少次摔棋子试验就一定能够找到X层是第几层？（棋子摔碎了就不能再用了） 2。求一组数中第二大的元素，要求从效率上考虑。 3。有n个水桶，组成一个环，相邻两个有水管连接， 水管中间有阀门，都关上。 初始条件是：水桶有水，深度不一，保存在数组a[n]里面。 问：设计算法，针对具体的a[n]，使得打开阀门最少情况下，水桶深度相同。 时间复杂度 <O(n^2),最佳是o（N）. 4。有N个人买可乐，每5空瓶送1瓶 问共需要买多少瓶？ 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2008-10-06
1：34次
|
| 返回顶楼 | |
|
发表时间：2008-10-07
chenpingtai2008 写道 1。现有一百层高楼和两个棋子，棋子从X层上掉落摔到地面刚好摔碎（即X层以下是摔不碎的）
请问至少需要多少次摔棋子试验就一定能够找到X层是第几层？（棋子摔碎了就不能再用了） 至少需要18次摔棋子试验就一定能够找到X层是第几层 这是个查找问题 当可以有无数个棋子的时候，可以用2分（3分...）查找获得O[XlogX]的性能 当棋子只有一个的情况下，只能从第2楼开始一层一层往上试进行线性查找 注意到棋子只有2个 所以，第一个棋子可以每隔n层试验一次，这个棋子第n*k层摔碎以后， 再从第n*(k-1)+1层开始试验第2个棋子，最多需要试验n-1次就可以得到X 所以需要的次数是(X/n)+n-1 而如果k达到(X/n)的最大值的时候第一个棋子仍然没有摔碎的话 剩下的楼层显然不足n-1层 所以，用(X/n)+n-1次试验一定能够知道X 于是，得到如下表达式 y = (X/n)+n-1 其中y就是一定能查找到X的次数 当n = X的平方根的时候，y取最小值 注意到n是整数 所以，当X是整数的平方的时候，min(y)=X的平方根*2-1 当X不是整数的平方的时候，min(y)=X的平方根*2 X在1-100的范围内min(y)的最大值为19 不过，在这里，题目有一点模糊的地方： 站在第100层的地板上扔棋子，实际的高度是第99层天花板的高度 而从1楼的地板上扔棋子是没有意义的 所以，实际上X的范围应当是1-99， 于是得出结果是18次 |
| 返回顶楼 | |
|
发表时间：2008-10-07
chenpingtai2008 写道 2。求一组数中第二大的元素，要求从效率上考虑。 线性查找求最大值 每次最大值变量被替换前的值保留下来，就是第二大的
public class Test2ndMax {
public static void main(String[] args)
{
int[] intArray = new int[] {
1, -5, 20, 14, 56, 67, 23, 99, 188, 87, 290, 34, 144, 250, 400
};
System.out.println("the second max integer is : " + search2ndMax(intArray));
}
public static int search2ndMax(int[] intArray)
{
if (intArray == null
|| intArray.length <= 1
){
throw new IllegalArgumentException();
}
int result = intArray[0];
int max = intArray[0]; //最大值变量
for (int i = 1 ; i < intArray.length ; i++)
{
if (intArray[i] > max
){
result = max;
max = intArray[i];
}
}
return result;
}
}
引用 the second max integer is : 290 |
| 返回顶楼 | |
|
发表时间：2008-10-07
armorking 写道 chenpingtai2008 写道 1。现有一百层高楼和两个棋子，棋子从X层上掉落摔到地面刚好摔碎（即X层以下是摔不碎的）
请问至少需要多少次摔棋子试验就一定能够找到X层是第几层？（棋子摔碎了就不能再用了） 至少需要18次摔棋子试验就一定能够找到X层是第几层 这是个查找问题 当可以有无数个棋子的时候，可以用2分（3分...）查找获得O[XlogX]的性能 当棋子只有一个的情况下，只能从第2楼开始一层一层往上试进行线性查找 注意到棋子只有2个 所以，第一个棋子可以每隔n层试验一次，这个棋子第n*k层摔碎以后， 再从第n*(k-1)+1层开始试验第2个棋子，最多需要试验n-1次就可以得到X 所以需要的次数是(X/n)+n-1 而如果k达到(X/n)的最大值的时候第一个棋子仍然没有摔碎的话 剩下的楼层显然不足n-1层 所以，用(X/n)+n-1次试验一定能够知道X 于是，得到如下表达式 y = (X/n)+n-1 其中y就是一定能查找到X的次数 当n = X的平方根的时候，y取最小值 注意到n是整数 所以，当X是整数的平方的时候，min(y)=X的平方根*2-1 当X不是整数的平方的时候，min(y)=X的平方根*2 X在1-100的范围内min(y)的最大值为19 不过，在这里，题目有一点模糊的地方： 站在第100层的地板上扔棋子，实际的高度是第99层天花板的高度 而从1楼的地板上扔棋子是没有意义的 所以，实际上X的范围应当是1-99， 于是得出结果是18次 先从14层扔（碎了试1-13） 再从27层扔（碎了试15-26） 再从39层扔（碎了试28-38） 再从50层扔（碎了试40-49） 再从60层扔（碎了试51-59） 再从69层扔（碎了试61-68） 再从77层扔（碎了试70-76） 再从84层扔（碎了试78-83） 再从90层扔（碎了试85-89) 再从95层扔（碎了试91-94） 再从99层扔（碎了试96-98） 最后从100层扔（如果确认临界层肯定存在的话，这步都可以省了）。 |
| 返回顶楼 | |
|
发表时间：2008-10-07
楼上的是正解
|
| 返回顶楼 | |
|
发表时间：2008-10-07
补：
100颗豆 5个犯人 1---5号 他们从中取豆子 规定必须取至少一个 并且不能交流 如果拿的最多的要死 拿的最少的要死 拿的一样多的也要死 后面一个拿的可以数剩下的豆子 然后决定拿多少个 犯人都比较聪明 但是他们的原则是 要让自己最大希望生存下来 那么你说最后的结果是什么 |
| 返回顶楼 | |
|
发表时间：2008-10-07
armorking 写道 chenpingtai2008 写道 1。现有一百层高楼和两个棋子，棋子从X层上掉落摔到地面刚好摔碎（即X层以下是摔不碎的）
请问至少需要多少次摔棋子试验就一定能够找到X层是第几层？（棋子摔碎了就不能再用了） 至少需要18次摔棋子试验就一定能够找到X层是第几层 这是个查找问题 当可以有无数个棋子的时候，可以用2分（3分...）查找获得O[XlogX]的性能 当棋子只有一个的情况下，只能从第2楼开始一层一层往上试进行线性查找 注意到棋子只有2个 所以，第一个棋子可以每隔n层试验一次，这个棋子第n*k层摔碎以后， 再从第n*(k-1)+1层开始试验第2个棋子，最多需要试验n-1次就可以得到X 所以需要的次数是(X/n)+n-1 而如果k达到(X/n)的最大值的时候第一个棋子仍然没有摔碎的话 剩下的楼层显然不足n-1层 所以，用(X/n)+n-1次试验一定能够知道X 于是，得到如下表达式 y = (X/n)+n-1 其中y就是一定能查找到X的次数 当n = X的平方根的时候，y取最小值 注意到n是整数 所以，当X是整数的平方的时候，min(y)=X的平方根*2-1 当X不是整数的平方的时候，min(y)=X的平方根*2 X在1-100的范围内min(y)的最大值为19 不过，在这里，题目有一点模糊的地方： 站在第100层的地板上扔棋子，实际的高度是第99层天花板的高度 而从1楼的地板上扔棋子是没有意义的 所以，实际上X的范围应当是1-99， 于是得出结果是18次 思路正确，但是细节没有注意到，第一个棋子隔n个，没坏时，下一次要隔n-1个，这样总次数不会超过n就能检查出来。 要保证n + n-1 + n-2 + ... + 1 >= 100 所以 n*(n+1)/2 >=100 n的最小值是 14 序列是14-27-39-50-60-69-77-84-90-95-98-99-100 检查一下，不论第一个子在哪个序列值上坏了，总次数都不会超过14次！ 13的序列是：13-25-36-46-55-63-70-76-81-85-88-90-91-? 如果到91还没坏，次数就超过13了。 因此最终答案是：需要14次摔棋子试验，就一定能够找到X层是第几层。 题目有一点模糊的地方，不影响答案！ 呵呵，没注意上面LZ已经给出正确答案了！ 发散一下，如果有三个棋子如何？ |
| 返回顶楼 | |
|
发表时间：2008-10-07
public class Test2ndMax {
public static void main(String[] args)
{
int[] intArray = new int[] {
1, -5, 20, 14, 56, 67, 23, 99, 188, 87, 290, 34, 144, 250, 400
};
System.out.println("the second max integer is : " + search2ndMax(intArray));
}
public static int search2ndMax(int[] intArray)
{
if (intArray == null
|| intArray.length <= 1
){
throw new IllegalArgumentException();
}
int result = intArray[0];
int max = intArray[0]; //最大值变量
for (int i = 1 ; i < intArray.length ; i++)
{
if (intArray[i] > max
){
result = max;
max = intArray[i];
}
}
return result;
}
}
这段程序貌似有bug,我拿这组数字来测试就有问题{ 1, -5, 20, 14, 56, 67, 23, 99, 188, 87, 290, 34, 144, 250, 400, 300 },它返回的仍然是290 引用 the second max integer is : 290 不过做点小小的调整就Ok了
public static int search2ndMax(int[] intArray) {
if (intArray == null || intArray.length <= 1) {
throw new IllegalArgumentException();
}
int secResult = intArray[0];
int max = intArray[0];
for (int i = 1; i < intArray.length; i++) {
if (intArray[i] > max) {
secResult = max;
max = intArray[i];
} else if (intArray[i] > secResult && intArray[i] < max) {
secResult = intArray[i];
}
}
if (secResult == intArray[0]) {
System.out.println("Illegal Argument!");
throw new IllegalArgumentException();
}
return secResult;
}
|
| 返回顶楼 | |
|
发表时间：2008-10-07
这段程序貌似有bug,我拿这组数字来测试就有问题{ 1, -5, 20, 14, 56, 67, 23, 99, 188, 87,
290, 34, 144, 250, 400, 300 },它返回的仍然是290 引用 the second max integer is : 290 不过做点小小的调整就Ok了
if (intArray[i] > max)
{
result = intArray[i];
}
public class Test2ndMax {
public static void main(String[] args)
{
int[] intArray = new int[] {
1, -5, 20, 14, 56, 67, 23, 99, 188, 87,
290, 34, 144, 250, 400, 300
};
System.out.println("the second max integer is : " + search2ndMax(intArray));
}
public static int search2ndMax(int[] intArray)
{
if (intArray == null
|| intArray.length <= 1
){
throw new IllegalArgumentException();
}
int result = intArray[0];
int max = intArray[0];
for (int i = 1 ; i < intArray.length ; i++)
{
if (intArray[i] > max
){
result = max;
max = intArray[i];
continue;
}
if (intArray[i] > result
){
result = intArray[i];
}
}
return result;
}
}
|
| 返回顶楼 | |
