idea's blog

查看我的网站的访问记录, 发现很多来自百度的"goodle earth". 原来是 google 的错误拼写. 查看 goodle.com 这个网站, 是一个韩国网站, 不知道该网站现在值多少钱.

Google Earth 的下载链接在: http://earth.google.com

(30分)
芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限．其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．坏芯片和其它芯片比较时，会随机的给出好或是坏。

题目中给出的最重要信息是比较方法. 根据比较方法, 我们可以得出最重要的结论是, 如果两个芯片两两比较出现了坏的情况, 那么这两个芯片必有至少一个是坏的. 定义一个方法bcmp(a,b),表示a和b两两比较, 返回值0表示至少有一块芯片是坏的, 1表示a,b都是好的或者都是坏的.

因为好芯片比坏芯片多, 所以从2K块芯片中随机取出K块芯片必然有至少一块好芯片, 也可能全部都是好芯片. 将这K块芯片中的随机一块基准芯片与其它所有的K-1块芯片进行bcmp(), 如果全返回1, 说明这K块芯片全部都是好芯片, 因为如果至少有一块坏芯片话, 该坏芯片必能被其中至少的一块好芯片检测出来.

如果不是全部都是好芯片的情况, 那么当bcmp()返回0时, 同时将两块芯片排除, 得到的2(K-1)块芯片仍然满足题设的条件. 然后继续进行二分.

如果K为1时, 两块芯片都是好的.

该算法最坏的情况是对芯片进行二分总是无法得到全部都是好芯片的情况, 而且直到最后一次bcmp才返回0. 所以比较次数 ((K-1)+(K-2)+...+1)*2=(K^2-K). 注意到bcmp()进行再次比较.

解题思想: 递归.

==== 2009年10月9日更新: 经过长期的思索, 终于想到一种复杂度只有O(n)的算法:

O(N)解法1:

2K个芯片分成K对两两比较，结果有三种：好-好，好-坏，坏-坏。

（1）好-好：扔掉任意一块
（2）好-坏：都扔掉
（3）坏-坏：都扔掉

只要原来2K块芯片里好的比坏的多，那么留下的<=K块芯片里一定还能保证好的比坏的多。这样下去最后总能留下一块好的芯片。时间复杂度O(N).

我上大学, 最希望的事是和大师交流, 无论他是哪个学科的大师. 但是, 我所在的学校从学术统计上来说, 这种大师只有几位, 资源稀缺, 所以我们一百多名同学没有在课堂上见过这种人.

曾经有一位年龄在50多岁样子的硕士生导师作为我们的任课教师, 他在课堂上对一百多名计算机科学专业的学生宣称, 计算机行业已经没有什么可发明的了, 你们只需要好好学习别人已经做好的库就可以了. 在1899年, 美国专利局局长杜耐尔提议关闭自己所在的美国专利局, 因为他认为"所有能被发明的东西都已经被发明出来了". 无法想像, 一百多年后竟然有一位中国的大学教师作出这种可笑的言论.

然后他教育学生要好好学习, 因为科学的学习是苦的, 他同时在黑板上写了一个大大的"苦"字. 谁知, 他接着讲理由时就让人不舒服了. 他从"苦"字中间引出一条线, 然后写上一个更大的"钱"字, 扮作惊讶地说, 但是苦中有钱啊! 如此俗不可耐.

在解释API对于编程和软件开发的重要性时, 他实在是没有任何能力用一点点的文字来支持他的观点了, 竟然模仿台湾的综艺节目主持人上窜下跳, 像个猴子一样怪叫:"API好耶--这东西非常有用耶". 天啊, 我即使坐三天两夜的火车也没有现在这样恶心得想吐! 像他这种水平, 应该去乡间给大爷大妈作科普宣传, 而不是在大学讲堂里误人子弟. 一个50多岁样子的硕士生导师, 竟然无法用专业词句来解释一个概念, 竟然要落到使用像3岁小孩故意怪叫来吸引大人注意的方式.

在一堂科学课上, 教师不使用科学的态度来讲学, 却跟江湖说书人一样, 真是让人失望.

他这样做, 本质来说是他科学水平确实有限, 他本来就是到乡间做科普宣传员的料, 同时这也是他对待科学的态度问题. 科学是严肃的, 但是他却把科学当作奇技淫巧.

几百年前, 乾隆皇帝认为西方的科学是奇技淫巧. 几百年过去了, 中国没有了封建皇帝, 但是大众还是以奇技淫巧的眼光看待科学. 中国的综合国力落后西方发达国家几十年, 但是很多中国人的科学思想却落后西方文明几个世纪.

一百多页的PDF文档, 竟然就占了100多M内存不说, 还假死. 滚屏比玩顶级3D游戏还卡, 这是什么渲染水平! 选定超过1/4页面的文本, 程序就死了. 有这样的垃圾文档格式吗? 而且, 据说PDF文档的编辑是付费专利. PDF应该从地球上消失, 因为它是十足的垃圾, 连基本的性能都无法达到!

推荐HTML, 如果是HTML文档, 你还可以编辑, PDF你就别想了.

今天参加一个SUN的OpenSolaris编程大赛的宣讲会. 轮到做Solaris内核开发的一个技术人员演讲时, 我感受到了做技术的人的一些问题.

他说话不连贯, 经常找不到合适的中文词汇表达自己. 有时有说出了浅显的英文词汇, 却不知道如何翻译成中文. 与其说他在做演讲, 不如说他在介绍一些技术词汇和短语.

我认为做技术的人很容易出现这些问题:

1. 不能很好的理解非技术人员提出的问题.

在提问时间, 有一位同学大概是问, 在单核机器上编译生成的, 并且经过SUN的编译器使用多核技术进行优化的二进制代码在多核机器上运行能否利用并且有效地利用到多核. 这对做操作系统内核开发的人根本就是常识. 但是, 他在解读该同学的话上不太了解. 因为该同学并没有按照他们内核开发者的日常交流方式.

2. 过分专注以至于对其它基本知识缺乏了解.

他显然是使用Vi或者Emacs进行开发, 但是他今天却介绍SUN Studio开发工具. 他从命令行启动SUN Studio, 并且说应该能在桌面建立一个启动图标吧. 这显然可以, 而且很轻易就能做到 -- 只需要建立一个启动器. 他应该不提这个问题.

3. 看不起与自己使用不相同技术的人.

他问, 有人在Unix, Linux 或者 Solaris 下写过程序吗? 当我回答说我使用 Linux 写 Java 程序的时候, 他感到失望极了, 好像 Java 不是编程语言. 他接着问, 有人写过内核程序吗? 没人.

SUN的人今天的失误是, 用了一个不太了解技术的女职员和一个不善表达的技术人员(而且技术太好)来推广产品. 对于使用Windows的人, 要介绍他们使用UNIX类操作系统, 不要多说UNIX的技术有多先进, 而是应该说UNIX解决日常问题的优越方面.

不知道何故, 被百度封杀了. 在baidu搜索site:ideawu.net 表明我的网站没有被收录. 不过, 主要从 google.com 带来的流量比以前 google和baidu 总共带来的流量还要多.