ITPub博客

首页 > 应用开发 > IT综合 > [算法] 从一个 Google 面试题想到的

[算法] 从一个 Google 面试题想到的

原创 IT综合 作者:shagoocn 时间:2007-01-04 22:24:34 0 删除 编辑

  前一段时间看到一道 Google 的面试题在各大论坛被炒得很火,题目如下:“有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。”题目虽然看起来简单,但是仔细想想,此题中蕴含的算法道理以及实用价值还是很值得好好研究一下。石头在网上也看到了不少热心朋友的解法(CSDN、ChinaUnix),看过之后感觉还是挺有启发的,于是总结一下,主要的算法有以下几种:

[@more@]

  <1> 等分段求最小值:这种算法先假设把大楼分成等高的 x 段,这样在最差的情况下,要确定临界段,我们需要投掷 100/x-1 次,确定了临界段之后要确定临界层,我们需要再投掷 x-1 次。这样,问题就成了求函数 f(x)=(100/x-1)+(x-1) 的最小值问题。由于 f(x) 存在最小值且只有一个驻点,所以当 x=10 f(x) 取得最小值,最小值为18。<2> 假设投掷次数是均匀分布的,那么为了使最坏情况的投掷数最小,我们希望无论临界段在哪里,总的投掷数都不变(也就是说将投掷数均匀分布)。这样我们就可以假设第一次投掷的层数是 f,转化成数学模型,可以得到如下方程式 f+(f-1)+...+2+1>=99,即 f(f+1)/2>=99 的最小整数解,解出结果等于14。程序算法如下:

// Equation.cpp
#include
#include
using namespace std;

int f (int i) {
int r;
int s = 0;
while (i >= 1) {
s = s + i;
i--;
}
if (s >= 99) return 1;
else return 0;
}

int main () {
int m;
int n;
for (m = 1; m <= 100; m++) {
if (f(m) == 1) {
n = m; break;
}
}
printf("The result is : %dn", n);
system("pause");
}

  按结果分析看来,方法一的最小值的确比较小(10)但是问题是最大值无法确定(比如假设临界层在第99层则需要仍19下);而方法二的算法好在能得出一个固定的临界层值,这样便于一些问题的处理。总的来说,石头认为两种方法各有所长,虽然方法二看起来的确更接近出题者的本意,但是如果将棋子本身破碎的概率也考虑进去就不一定了(当然,一般来说层数越高破碎的概率应该越大,但是我们试想一下如果假设棋子破碎的几率是和层数成反比,那么使用方法一是否会有更好的效果呢?)。然而不管出题者的意图是什么,我觉得这个题目所引出的数学模型还是很有实用意义的,特别在一些数据挖掘应用中。我猜想这些算法是不是与 Google 数据库的技术内幕有什么联系呢 ... 前几天和一个业内的前辈谈起下一代互联网的技术趋势,说到了所谓的“算法时代”的话题,看来关注一些有趣的算法也不错呢 ... 不知不觉时间又晚了,还是先休息吧 :)

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/8244769/viewspace-888399/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
请登录后发表评论 登录
全部评论
  • 博文量
    11
  • 访问量
    756751