1.1 让CPU占用率曲线听你指挥 ★★★

写一个程序,让用户来决定Windows任务管理器(Task Manager)的CPU占用率。程序越精简越好,计算机语言不限。例如,可以实现下面三种情况[1]
CPU的占用率固定在50%,为一条直线;
CPU的占用率为一条直线,具体占用率由命令行参数决定(参数范围1~ 100);
CPU的占用率状态是一条正弦曲线。


- Miloyip Miloyip:本书的题目中,除了1.1和1.10和操作系统相关,其他题目都是纯算法/数据结构的问题,
不涉及其他计算机领域(例如程序语言/范式、计算机架构、软件工程、资料库等等),
可以考虑加入纯算法和数据结构以外的有趣题目,使内容更贴近书名。

- lispython lispython这个链接谈到对1.1的一些改进建议。
- michaelpeng michaelpeng:原书中的代码都把通过busy和sleep控制CPU利用率的代码和计算曲线的代码放到一个函数里.一个函数负责一个职责会更好,可以抽象出一个绘制CPU曲线利用率的函数,接受一个y=f(t)形式的函数作为参数来绘制曲线可扩展性.
- gaobo gaobo关键在于让读者深入理解taskmgr中的CPU占用采样的原理,调用什么函数可以模拟CPU的占用。既然是要说Windows API的事儿,索性说得透彻一点儿,比如怎么样在函数执行前“清场”,把其它正在运行的非系统进程暂停以免影响输出结果。另外,还可以把这个题目的要求扩展到网络吞吐曲线或是任何“Windows性能监视器”中的统计对象来输出指定的曲线(或用其组合来画出更复杂的图像),才有趣呢。
- gnuhpc gnuhpc附上另外两个网上讨论的链接:Playing with the CPU Usage Curve Write code to make CPU usage display a sine wave
- liuh liuh希望P11能够重新整理下文字,特别是代码清单1-5,这一页,对没有Windows编程背景的读者,可读性近似为0了。

[Jianqiang Bao]这道题目的C#解法及分析:http://www.cnblogs.com/azure/archive/2010/03/24/1693365.html

- flyinghearts flyinghearts
本节过于关注在windows平台的具体实现细节。应该将这些实现细节挪到补充知识当中,比如程序要实现busy/idle函数(分别表示CPU工作/空闲多少毫秒)和计时函数getTime,getTime的实现是平台相关的,在Windows平台是用GetTickCount还是timeGetTime,精度怎么样,这些不应该是读者所关注的,应该放在扩展知识中详细说明,事实上GetTickCount和CRT的clock的精度都是15/16ms,用GetTickCount不如用C标准库的clock。
对动态适应解法,应该给出一个用C++解决问题的大概思路,比如通过枚举进程获得其它进程在某段时间内的CPU工作时间从而算出所占的CPU百分比,而不是直接给一个C#函数。另外,可能要用ZwSuspendProcess(linux可以直接通过发送信号)挂起某些进程才能真正实现动态适应。
希望改版后,能花更多的篇幅,描述怎么画周期性变化的曲线,非周期性变化的曲线,希望能更多的关注算法原理,像画曲线,本质就是用锯齿状的折线来近似。

- flyinghearts flyinghearts
bczm 01.doc 第10页的 代码清单1-4 :
PI值应该是3.1415926536(而不是3.1415926535,注意四舍五入)
int amplitude = TOTAL_AMPLITUDE / 2;
busySpan[i] = (DWORD)(amplitude + (sin(PI * radian) * amplitude));
这两句太能误导人了,尽管公式正确,但是让人看不明白怎么推出来的:
建议改成:
double busyRatio = 0.5 * (1 + sin(PI * radian));
busySpan[i] = TOTAL_AMPLITUDE * busyRatio;

建议修改的代码如下:
//C++ code to make task manager generate sine graph
//#include<cstdlib>
#include<cmath>
#include<windows.h>
 
void drawSine()
{
 const double PI = 3.1415926536; //pi值
 const int SAMPLING_COUNT = 200; //一个周期内采样点数量
 //INTERVAL对应原程序的TOTAL_AMPLITUDE
 const int INTERVAL = 300; //两次采样的时间间隔
 
 //由于正弦曲线是周期性变化,只要处理一个周期就够了。
 //把曲线的一个周期划分成SAMPLING_COUNT份进行采样,
 //两次采样的时间间隔为INTERVAL毫秒,
 //计算每个采样点的振幅值,该值就是在这段INTERVAL时间内CPU工作时间所占的比率
 
 // 个人倾向于使用两个常量周期PERIOD和采样数SAMPLING_COUNT,
 // PERIOD值决定了形状,可以通过改变SAMPLING_COUNT值调整所画曲线的精确度
 // const double PERIOD = 60000; //60000 ms 一个周期
 // const int SAMPLING_COUNT = 200; //200个点
 // const double INTERVAL = PERIOD / SAMPLING_COUNT; //采样间隔
 
 const double radianIncrement = 2.0 * PI / SAMPLING_COUNT; //抽样弧度的增量
 
 DWORD busyTime[SAMPLING_COUNT]; //busyTime 对应原程序的 busySpan
 double radian = 0.0;
 for(int i = 0; i < SAMPLING_COUNT; i++) {
 double busyRatio = 0.5 * (1 + sin(radian));
 busyTime[i] = (DWORD)(busyRatio * INTERVAL);
 radian += radianIncrement;
 }
 
 DWORD startTime = 0;
 for (int j = 0; ;j = (j + 1) % SAMPLING_COUNT) {
 startTime = GetTickCount();
 while ((GetTickCount() - startTime) <= busyTime[j]) {}
 //Sleep(INTERVAL - busyTime[j]);
 DWORD idleTime = INTERVAL - busyTime[j];
 Sleep(idleTime);
 }
}
 
 
int main()
{
 drawSine();
 return 0;
}

- lzprgmr lzprgmr
bczm 01.doc, P7:
>>假设这段代码要运行的CPUP4 2.4Ghz2.4 * 109次方个时钟周期每秒)。现CPU每个时钟周期可以执行两条以上的代码,我们取平均值两条,于是有2 400 000 000 * 2/5 = 960 000 000(循环/秒),也就是说CPU 1钟可以运行这个空循环960 000 000次。
这里是不是搞反了, 一条指令一般需要多个时钟周期,而不是一个时钟周期可以执行多个指令,平均为2的话,应该是(2 400 000 000 )/5 * 2 = 240 000 000

- firewoods firewoods
最后一句话: "了解并应用了上面的API,就可以考虑在简历中写上“精通Windows”了。", 看起来有点太夸大了.

- pluskid pluskid
这道题目我们曾经在学校趣味程序设计竞赛上用过,当然,还加了其他的扩展,比如多核,在这里的文中已经有提过。此外还要支持从命令行传入除了 sin 之外的其他函数,当然这就涉及到简单表达式解析等方面的问题,一方面是将考察的内容更加全面一点,但是作为本书的内容一股脑塞到这里却并不太合适。不过有一个扩展是和这里比较相关的,就是 judge 会运行另一个干扰程序。当然干扰程序的干扰不能太过分,比如在某个时间段 cpu % 不能超过 60% ,如果干扰程序本身就造成了超过 60% 的 cpu 占用率的话,仅用 sleep 是没有办法让函数图像能如预想的那样的。在干扰程序存在的情况下,主要需要考虑就是根据其他程序的 cpu 占用率来调整自己应该空循环的时间,此外还有一个小 trick 就是每一轮先 sleep 再空循环,这样可以避免空循环超额(因为无法控制自己在 sleep 阶段别的程序的 cpu 占用)的情况。






























- huangkun huangkun
代码清单1-1有个小错误,第二行缺少了一个右括号。

1.2 中国象棋将帅问题 ★★★

下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-1所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”)。
image019.jpg
图1-1
A、B二子被限制在己方3×3的格子里运动。例如,在如上的表格里,A被正方形{d10, f10, d8, f8}包围,而B被正方形{d3, f3, d1, f1}包围。每一步,A、B分别可以横向或纵向移动一格,但不能沿对角线移动。另外,A不能面对B,也就是说,A和B不能处于同一纵向直线上(比如A在d10的位置,那么B就不能在d1、d2以及d3的位置上)。
请写出一个程序,输出A、B所有合法位置。要求在代码中只能使用一个变量。
- MichaelPeng MichaelPeng: 这里隐含了一个假设:程序是用 C/C++语言写的.有些脚本语言里这个问题可以很简单
- gaobo gaobo即使用 C/C++ 语言写也可以很简单,书上就写了一个很简明扼要的程序,不过能为那个神来之笔的程序写点儿注释让人看得更明白就更好一些了。
- linfuqing linfuqing这里是我自己对此题目的解法及分析.
- lzprgmr lzprgmr
  • P17, 代码清单1-6,最开始那些define与注释, 要么全部注释掉,要么移到代码清单外面- 不然一看就是重复define
  • P20, 第二个实现的确精巧,但最好解释一下为什么取值81,以及用/ 与%模拟了双重循环
  • P20, 代码清单1-7其实是最直接的二重循环,感觉还是用了两个变量 - 为了使此解说的过去,最好把题改成:只用一个字节的空间,而不是一个变量。

- firewoods firewoods
因为要输出所有的解, 所以无论是双循环, 单循环或者是采用位运算时间复杂度都是一样的.问题的关键是智能采用一个变量.
第一个实现中的用位运算来解决这个问题,显得有点太复杂了, 如果要讲解位运算的方法,可以考虑换一个实例.
而第二个实现代码简单的多, 也能体现出编程之美来, 所以最好着重讲解一下第二个算法.
实际上, 如果我们用3进制, 那么第二种算法实际上就是基于三进制的数据存储以及判断三进制中第1位和第三位的数字是否相等.
另外: i%9%3 = i%3

- flyinghearts flyinghearts
希望能将限制只用一个变量,改成只用一个字节存储变量。
书上的代码,相当于手动实现了位域(这本来是编辑器所做的)

代码清单1-6:
#define RSET(b, n) (b = ((LMASK & b) | n))
#define LSET(b, n) (b = ((RMASK & b) | (n << HALF_BITS_LENGTH)))
这两个宏中n如果是表达式的话,由于运算符的优先级顺序,可能得不到想要的结果,应该将n用括号括起来

希望将代码用C++的const常量和inline函数重写,而不是用宏,并增加自增函数
for (setX(1); getX() <= total; incX())
for (setY(1); getY() <= total; incY())
...

- pluskid pluskid
这个题目后面提供的解法让人看了之后觉得题目就是在玩文字游戏,有点像做脑筋急转弯了,题目里要求只能用一“个”变量,然而目前书里提供的三种解法实际上都是用了多个变量,只不过是通过将两个变量通过某种编码方式压缩在一“个”整数里了,所以“看起来”像是一个变量,而实际上并不是。

实际上,位置坐标有两个 (A 和 B),因此如果只用一个循环变量,必然有一个位置坐标需要硬编码枚举出来。但是由于题目中的要求,将帅不同列,所以 B 的可行的位置坐标实际上是依赖于 A 当前的坐标的,亦即是动态的,不能简单硬编码枚举。一个没有技术含量的解法就是枚举 A 的坐标,然后动态计算 B 的坐标,类似于这样:

print_B(1)
print_B(2)
...
print_B(9)

其中传进去的参数是 A 的位置,print_B 函数里可以用一个循环变量来计算 B 的可行位置。这样就只用了一个变量,虽然用了“多次”,但是它确实是同一个,比如,你可以声明一个全局变量来使用。

另一个稍微有点技术含量的解法是,注意到,虽然 B 的可行位置依赖于 A 的位置,所以是动态的,但是这个动态可行位置其实可以通过非常简单的方法计算出来。具体来说,设 A 的位置为 a ,那么 B 的可行位置为 1 + ([1, 2, 4, 5, 7, 8] + (a-1)) % 9 。这里数组表示对每一个元素分别做相应的运算。画一个图就会非常明了了。这样一来,这种解法的完整的代码可以写作如下:

#include <stdio.h>
 
#define P(a,b) printf("A = %d, B = %d\n", a+1, b+1)
#define Print(a) do { P(a, (a+1)%9); P(a, (a+2)%9); \
 P(a, (a+4)%9); P(a, (a+5)%9); \
 P(a, (a+7)%9); P(a, (a+8)%9); \
 } while(0)
 
int main()
{
 int i = 0;
 for (i = 0; i < 9; ++i)
 Print(i);
 return 0;
}
 
只在 main 函数里用了一个循环变量迭代 1 到 9 表示 A 的位置。当然,如果连 A 的位置也通过硬编码枚举,用宏来做可以做到连一个变量都不用。

- huangkun huangkun 最后的位域实现觉得是一种投机取巧。这里关键的是如何把二维的信息用一维的方式来压缩,或者用九进制,或者用位压缩。位域的做法其实用结构体也一样。觉得这不是一种非常符合要求的做法。
- flyinghearts flyinghearts有点太沉闷,不应该做为前三篇文章之一,应该移到后面去。《光影切割问题》和NIM游戏等几篇,容易引起读者的兴趣,可以挪到前面。
- flyinghearts flyinghearts
1.要求“输出A、B所有合法位置”这个合法位置该怎么表示,按照插图,我想一般都会理解成:(d1,f10) 这样的位置表示,而不是解答中的那个(7, 3)这种表示。
2.解法中的位运算,算是基本功吧,没必要解释那么详细并列出计算公式。把它们替换成几行代码,反而让人更容易理解。
- gaopeng gaopeng@flyinghearts
关于第一条,这种表示更简洁,书中后来也有说明,个人觉得应该还好

- uniquestudio uniquestudio我觉得第二题和第三题 换下位置,因为第三题更吸引人。将帅问题使用一个变量,解法有种投机取巧的感觉,让人从第一题的过山车一下子落到了一马平川。

1.3 一摞烙饼的排序 ★★★

星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:
“我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。
我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到大小有序的结果呢?”如图1-2所示。
你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢?
image032.jpg
图1-2
- linfuqing linfuqing这里是我自己对此题目的解法及分析.
- firewoods firewoods
算法实现上应该是分枝定界法, 建议可以增加对分枝定界算法的原理和应用场合的描述.
- lzprgmr lzprgmr挺趣味的一个题,通过烙饼引入一个不同以往的排序算法,随即引出分支定界,两点小问题:
  • P23代码的构造函数中,请初始化指针成员为NULL,析构函数中,删除数组请使用delete []
  • >> (P27) 结合上面两点,我们希望UpperBound越小越好,而下界(LowerBound)越大越好。假设有神仙指点,只要告诉神仙当前的状态,他就能告诉你最少需要多少次翻转。这样,我们可以花费ON2)的时间得到最优的方案。
这段话感觉有点玄乎, 最好能解释下O(N2)怎么来的

- huangkun huangkun 感觉代码清单1-8过于繁琐了,以类似伪代码的形式给出Search函数的实现就行。面试时候可能需要这样完整的实现,书中只要能够解释清楚就行。
还有一个小问题,不知道是我的问题还是:P26页那个O(N^2)是什么意思,我至今仍然没有看懂?

- matrix67 matrix67
关于翻饼排序的问题,还有一个有趣的话题,可以加在O(n)构造解之前:

1. 如何用翻饼操作实现交换中间任意两张相邻的饼?
实现后,我们就可以把这个问题当作只能交换相邻元素的排序问题做了,有了O(n^2)次翻饼的构造解。

2. 如何用翻饼操作实现对中间任意多张连续的饼的逆序操作?

3. 如何用翻饼操作实现交换任意两张(可能不相邻)的饼?
实现后,我们就可以把这个问题当普通的排序问题做了,有了O(n log n)次翻饼的构造解。

1.4 买书问题 ★★★

在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中,一共有五卷。假设每一卷单独销售均需8欧元[2] 。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:
本数  折扣
2    5%
3    10%
4    20%
5    25%
在一份订单中,根据购买的卷数及本数,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望计算出的总额尽可能的低。
要求根据以上需求,设计出算法,能够计算出读者所购买一批书的最低价格。
- gaobo gaobo此题可以加入团购背景,从单变量目标函数的贪心算法扩展到实现多变量目标函数的最优化,也可以从卖家的角度看看应该怎样设计团购价格策略实现利润最大化。

- cwzw cwzw《编程之美》----1.4买书问题。

对买书问题有变形的贪心算法证明:
符号:【3】y3表示享受3卷的折扣y3次,即一共有3*y3本书。其他类推。
折扣条件 【5】 25% 【4】20% 【3】10% 【2】5% 【1】0%
算法如下:
1. 对给定要买的书籍书卷的数量按小到大排序,不妨设书卷(A,B,C,D,E)的各自购买数量为(x1,x2,x3,x4,x5)(x1<=x2<=x3<=x4<=x5).
2. 按照贪心算法得到有 【5】本书享受折扣 x1 次,【4】本享受x2-x1次, 【3】有x3-x2次,【2】有x4-x3次,【1】有x5-x4次。
3. 享受【5】本折扣{A,B,C,D,E}和【3】任意折扣{B,D,E}的总是能分拆成两份【4】折扣{A,B,D,E},{B,C,D,E}。故将第2步中所得的【5】x1,【3】x3-x2,合并入【4】折扣中. {如x3-x2<=x1则新的折扣布局为【5】x1-x3+x2,【4】x2-x1+2*(x3-x2),【3】0,【2】x4-x3,【1】x5-x4.}
4. 按上述计算全部折扣。
算法证明:设要购买y本书,并且按最优折扣有【5】y5,【4】y4,【3】y3,【2】y2,【1】y1。现在来考察最优折扣的解得结构。
因为【5】+【3】总能拆分成【4】+【4】并且【4】+【4】=1.6>【5】+【3】.故在最优折扣中y5和y3必然有一个为0(或两个都为0)
现在分情况讨论
y5=0.考察,【5】y5=0,【4】y4,【3】y3,【2】y2,【1】y1。
【1】y1的集合中卷数必然只有一种(若有两重卷书则够成【2】折扣),不妨设其为卷E。
【2】y2的集合中卷数必然只有两种(【3】+【1】>【2】+【2】),并且其中一种为卷E。不妨设为D,E。
同理:【3】y3集合中卷数种类只有三种,并包含D,E。不妨设为C,D,E.
【4】中可有五种卷,但其只能是{A,C,D,E},{B,C,D,E}类型折扣。若有不包含{CDE}型的折扣(如ABCD)则可与【3】中的CDE合并分拆成【5】+【2】>【4】+【3】.
这样就得到了:
A B C D E
【5】 0 0 0 0 0
【4】 XA XB y4 y4 y4
【3】 y3 y3 y3
【2】 y2 y2
【1】 y1

{A,B,C,D,E}的数量为(XA,XB,y3+y4,y3+y4+y2,y4+y3+y2+y1), 其中XA+XB=y4.
可知当书卷C数量y3+y4>= XA+XB=y4书卷A+B的数量时,用上述变形的贪心算法恰好得到最优折扣的解。
当y5!=0,y3=0时候:考察,【5】y5,【4】y4,【3】y3=0,【2】y2,【1】y1。的结构。
【1】y1的集合中卷数必然只有一种(若有两重卷书则够成【2】折扣),不妨设其为卷E。
【2】y2的集合中卷数必然只有两种(【3】+【1】>【2】+【2】),并且其中一种为卷E。不妨设为D,E。
【3】y3=0。
【4】y4的集合中折扣类型必然都包含{D,E}。故为Z1{BCDE},Z2{ACDE},Z3{ABDE},其中Z1+Z2+Z3=y4。
现在证明【4】中只能有两种折扣类型。(反证法)
若有三种 则有{BCDE}+{ACDE}+{ABDE}={ABCDE}+{ABCDE}+{DE}
但是折扣模型【4】+【4】+【4】<【5】+【5】+【2】所以与最优解矛盾。
故【4】y4中的折扣类型最多只能有两种。不妨设其为Z1{BCDE},Z2{ACDE}
其中Z1+Z2=y4.
【5】y5的集合为{A,B,C,D,E}。
现在有
A B C D E
【5】 y5 y5 y5 y5 y5
【4】 Z1 Z2 y4 y4 y4
【3】 0 0 0
【2】 y2 y2
【1】 y1

{A,B,C,D,E}的数量分别为(y5+Z1,y5+Z2,y5+y4,y5+y4+y2,y4+y5+y2+y1), 其中
Z1+Z2=y4。当卷A+卷B数量y5+Z1+y5+Z2=2*y5+y4>y5+y4卷C的数量时候,最优折扣模型也可由上述变形的 贪心算法得到。
综合上述,算法正确!

代码:(假设数组a已经按小到大排序)
float Optimize_ discount(int a[],int n=5{
 
 If(a[0]>=a[2]-a[1])
 
 {
 
 return (a[0]+a[1]-a[2])*5*25%+(a[1]-a[0]+2a[2]-2a[1])*20%+(a[3]-a[2])*5%; }
 
 else
 
 { return (a[1]-a[0]+2*a[0])*20%+(a[2]-a[1]-a[0])*10%+(a[3]-a[2])*5%;}
 
}

- flyinghearts flyinghearts
希望对五种书的编号不要使用 卷一, 第一卷 之类,而是使用英文字母,如卷A
避免读者看书不够仔细,产生误解

P31 表1-1 折扣计算表
有的数拆分成3个、4个、5个,7拆分成3+2+2,没列出来,为什么要将6的拆分2+2+2列出来?

P32 解法一:
在小于5本的情况下,直接按折扣买就好了:
这句话和后面的几句话,都是基于假设:每次购买不考虑书的种类,希望能强调这一点

贪心策略建议我们买Y5本卷五,Y4-Y5本卷四,Y3-Y4本卷三,Y2-Y3本卷二和Y1-Y2本卷一。
应该是: 贪心策略建议我们: Y5次每次购买5本,Y4-Y5每次购买4本,……后面的也要做相应的调整。
另外,这个贪心策略考虑了每次购买的书具体种类,与前面的假设相反,读起来有点别扭。
应该强调下:新的调整是5新的调整是5+3->4+4,这个调整在考虑了书的具体种类时,一定能够做到。

P34
如果换一个思路呢?比如根据贪心算法计算出一个表,如表1-3,直接套用总数为10本以下的调整方法,找出所有违反贪心算法的反例,直接进行调整(如把所有5+3的组合改变成为4+4的组合)呢?这样是否可以充分利用贪心算法的便捷,同时又对其不足和反例进行调整?

这种想法是错误的,反例(折扣分别为:10% 12.5% 19% 23% 25%, 只有5+3->4+4不满足贪心算法):
对12本书,4+4+4组合折扣大于5+5+2,根本就不能通过查表来判断

要查表的话,对任一种5卷的买书折扣方案,可能要计算6、7、8、11、12、13、16、17、18、21和22这11个买法。


1.5 快速找出故障机器 ★★

关心数据挖掘和搜索引擎的程序员都知道,我们需要很多的计算机来存储和处理海量数据。然而,计算机难免出现硬件故障而导致网络联系失败或死机。为了保证搜索引擎的服务质量,我们需要保证每份数据都有多个备份。
简单起见,我们假设一个机器仅储存一个标号为ID的记录(假设ID是小于10亿的整数),假设每份数据保存两个备份,这样就有两个机器储存了同样的数据。
1. 在某个时间,如果得到一个数据文件ID的列表,是否能够快速地找出这个表中仅出现一次的ID?
2. 如果已经知道只有一台机器死机(也就是说只有一个备份丢失)呢?如果有两台机器死机呢(假设同一个数据的两个备份不会同时丢失)?

- lzprgmr lzprgmr
对于两台ID相同的机器死机的情况,解法四可以充分利用解法三:
if xor(all IDs) != 0
解法三
else
id = (sum(原ID) - sum(剩下的ID))/2

就无须立方程,解方程了

- flyinghearts flyinghearts:题目没把问题说清楚,而且题目的背景也不够好,根据“我们需要很多的计算机来存储和处理海量数据”和“假设一个机器仅储存一个标号为ID的记录”,可以得到结论:ID数量不会很大,这样先排序再统计,效率也不会差。(- gaobo gaobo@flyinghearts 看起来这个题目像是实际问题。另外,这个题目想说明的应该是解决这个问题的巧妙思路吧)

解法一:
“如果ID的数量多达几G甚至几十G”,基于前面的理由,这个假设不成立。
和解法二,本质差不多,可以合并在一块,简单的描述下。
解法一还有一个错误:“假设有N个ID,且ID的取值在0~(N-1)之间”这个假设已经违背了题目的本意(“假设ID是小于10亿的整数”)。(- gaobo gaobo@flyinghearts 没觉得这个是个错误啊~)

解法三:
x(i)=f(...),书中说,“显然,f的形式不只一种”但实际上,我们能找到的只有xor函数,关于对x(i)的一大段介绍没有说清楚为什么可以用异或xor函数。对该函数最关键的一点:xor满足交换率和结合率(- gaobo gaobo@flyinghearts 这个可以加个说明),书中却没有提到。
a xor b = b xor a a xor b xor c = a xor (b xor c) = a xor c xor b
a xor a = 0 a xor 0 = a
正因为满足交换率和结合率才有:
a xor b xor c xor b xor a
= (a xor a) xor (b xor b) xor c
= 0 xor 0 xor c
= c

解法四:
如果将题目改成:每个机器只保存一个记录,因为某个操作错误,造成某台机器的记录被另一个覆盖,求找出被覆盖的记录编号。那么通过两个方程求解,是种很好的方法。但应用于本题,要去求64位整数的平方根,给人一种很糟糕的感觉。
- finalbob finalbob:怎么寻找数组中的频繁项?

1.6 饮料供货 ★★★

在微软亚洲研究院上班,大家早上来的第一件事是干啥呢?查看邮件?No,是去水房拿饮料:酸奶、豆浆、绿茶、王老吉、咖啡、可口可乐……(当然,还是有很多同事把拿饮料当作第二件事)。
管理水房的阿姨们每天都会准备很多的饮料给大家,为了提高服务质量,她们会统计大家对每种饮料的满意度。一段时间后,阿姨们已经有了大批的数据。某天早上,当实习生小飞第一个冲进水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鲜橙多时,阿姨们逮住了他,要他帮忙。
从阿姨们统计的数据中,小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞,STC(Smart Tea Corp.)负责给研究院供应饮料,每天总量为V。STC很神奇,他们提供的每种饮料之单个容量都是2的方幂,比如王老吉,都是23 = 8升的,可乐都是25 = 32升的。当然STC的存货也是有限的,这会是每种饮料购买量的上限。统计数据中用饮料名字、容量、数量、满意度描述每一种饮料。
那么,小飞如何完成这个任务,求出保证最大满意度的购买量呢?

- firewoods firewoods
按照书中的解释, 每种饮料的上限是V/Vi个, 所以其实可以理解为没有上限约束.
如果没有所有饮料的容量都是2的幂这个条件, 其实是个背包问题.
但是加上这个条件以后, 可以用贪婪算法来解.
首先计算饮料单位满意度, 即Si = Hi /Bi, 我们的目标就是尽量多的购买满意度靠前的饮料.
所以对Si排序.
按从大到小的顺序遍历这些饮料, 如果V>Bj,则j饮料买V/Bj瓶,V=V%Bj
循环直到W等于0即可. 如果V不为0, 则无论怎么挑选饮料都无法达到总量V.

- lzprgmr lzprgmr
  • 首先,我觉得题意不是很清楚,我是看了答案后才算真正明白题意的
  • 其次,解法二使用备忘录方法递归求解,与解法一使用动态规划递推求解相比,效率有提高吗?我觉得解法二由于频繁的递归调用,反倒会影响效率。
    或者有我没考虑到的地方? 所以最好能对解法二分析一下复杂度来证明的确比解法一好。

- flyinghearts flyinghearts:
题目应该说明:购买量是一定等于V,还是满足 <= V,这道题是“多重背包”问题, 后面的解法不考虑每种饮料的数量限制,把它当做“完全背包”。
应该把题目改成两小问题分成两种情况:限制和不限制饮料数量。
- gaobo gaobo@flyinghearts:
大家满意度最高了应该就达到目标了,限制每种饮料的最高量是什么原因呢?

1.7 光影切割问题 ★★★

不少人很爱玩游戏,例如CS[3] ,游戏设计也成为程序开发的热点之一。我们假设要设计破旧仓库之类的场景作为战争游戏的背景。仓库的地面会因为阳光从屋顶的漏洞或者窗口照射进来而形成许多光照区域和阴影区域。简单起见,假设不同区域的边界都是直线[4] ,我们把这些直线都叫做“光影线”,并假设没有光影线是平行于Y轴的,且不存在三条光影线相交于一点的情况。
那么,如果我们须要快速计算某个时刻,在X坐标[A, B]区间的地板上被光影划分成多少块。如何设计算法?
image073.jpg
图1-3
- matrix67 matrix67
看到这幅图便想到了另一个经典的问题:

补充问题:从中去掉最少的线,使得剩下的线不相交。
答案:等价于求最长上升子序列

可以补充与逆序对相关的问题。例如:

补充问题:给定一组无序数列,问冒泡排序整个过程要做多少次交换?
答案:统计逆序对。

补充问题:给定一个数列,再给定一个数k,问平均数大于k的连续子序列有多少个?
答案:每个数都减k,然后算前缀和,然后统计逆序对。

补充问题:http://en.wikipedia.org/wiki/Fifteen_puzzle

- flyinghearts flyinghearts:
“求逆序数”本身可以做为一个专题,应该详细介绍。

1.8 小飞的电梯调度算法 ★★

微软亚洲研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯在每层都停。实习生小飞常常会被每层都停的电梯弄得很不耐烦,于是他提出了这样一个办法:
由于楼层并不太高,那么在繁忙的上下班时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。所有的乘客都从一楼上电梯,到达某层楼后,电梯停下来,所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候,每个乘客选择自己的目的层,电梯则自动计算出应停的楼层。
问:电梯停在哪一层楼,能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。

- flyinghearts flyinghearts:
应该说明:在电梯自动计算出应停的楼层后,乘客是否可以走出电梯。直接从一楼走楼梯到目的地。乘客直接从一楼走楼梯,也是符合题目要求的。并且能得到更优的解。
解法二,还需证明得到的局部解就是全局最优解,才能与给出的代码一致。
- gaobo gaobo
我觉得这个题目最大的问题在于,如何知道电梯里面要到每层楼的人数?
比如有1个人按3楼, 10个人去6楼,10 个人不会都去按6楼这个按钮的
除非更改下电梯里面的输入,或许也算个小发明:)

- matrix67 matrix67
从数学的角度来看,可以证明,问题的解就是所有人想去的楼层的中位数。如果给定Tot[i]这个数组,我们有办法在O(n)的时间里找出这个中位数来。这个问题可以扩展到二维的情形:给出平面上n个点,求出到所有点的曼哈顿距离最小的点。由于这个点光左右动不会对竖直分量造成影响,光上下动也不会对水平分量造成影响,因此答案就是所有点的x坐标的中位数,和所有点的y坐标的中位数。

但从算法角度来看,原文的解答方案更为巧妙——我们可以用O(1)的时间“推出”下一层的花费,从而在O(n)的时间直接算出每一层的花费。这让我想起下面这个类似的问题:定义一棵树的“中心”为,到所有结点距离之和最小的那个结点,求出一棵树的中心。
这个题目和文中的原题目非常像,几乎是从一个模子里出来的。容易想到O(n^2)求树的中心的朴素算法。O(n)的算法如下:用O(n)的时间遍历树,可以得出根到所有结点的距离和,以及以各结点为根的子树的结点数。然后考虑两个相邻的结点 i 和 j ,如果已知 i 到所有结点的距离和,可以用O(1)的时间“推出” j 到所有结点的距离和。因此,从根开始,可以依次“推出”其它各点到所有结点的距离和,不断记录最小值即可。
有趣的是,如果边上有权或者顶点上有权,算法同样适用。而电梯的问题,则是顶点有权的树的一种特殊情况。

- finalbob finalbob扩展问题:求图的直径

1.9 高效率地安排见面会 ★

在校园招聘的季节里,为了能让学生们更好地了解微软亚洲研究院各研究组的情况,HR部门计划为每一个研究组举办一次见面会,让各个研究组的员工能跟学生相互了解和交流(如图1-4所示)。已知有n位学生,他们分别对m个研究组中的若干个感兴趣。为了满足所有学生的要求,HR希望每个学生都能参加自己感兴趣的所有见面会。如果每个见面会的时间为t,那么,如何安排才能够使得所有见面会的总时间最短?
最简单的办法,就是把m个研究组的见面会时间依次排开,那我们就要用m * t的总时间,我们有10多个研究小组,时间会拖得很长,能否进一步提高效率?
image091.jpg
图1-4
- lzprgmr lzprgmr:


- lzprgmr lzprgmr
对于扩展问题一,有一段这样的描诉:
>>>此外,相信有些读者已经发现,在上述算法中,查找一个可行颜色的时候,我们遍历了整个isForbidden数组。如果我们使用更高效的存储数据结构(例如,堆),可以进一步把时间复杂度降低到ON * log2N
不知是否可以详解一下,如何化解掉当前区间和所有前面的区间的冲突检测:
int nMaxColors = 0, i, k, j;
for(i = 0; i < N; i++)
{
 for(k = 0; k < nMaxColors; k++)
 isForbidden[k] = false;
 __**for(j = 0; j < i; j++)**__
 if(Overlap(b[j], e[j], b[i], e[i]))
 isForbidden[color[j]] = true;
 for(k = 0; k < nMaxColors; k++)
 if(!isForbidden[k])
 break;
 if(k<nMaxColors)
 color[i] = k;
 else
 color[i] = nMaxColors++;
}
return nMaxColors;



1.10 双线程高效下载 ★★★

我们经常需要编写程序,从网络上下载数据,然后存储到硬盘上。一个简单的做法,就是下载一块数据,写入硬盘,然后再下载,再写入硬盘……不断重复这个过程,直到所有的内容下载完毕为止。能否对此进行优化?
我们不妨对问题做一些抽象和简化。
1. 假设所有数据块的大小都是固定的。你可以使用一个全局缓存区:
Block g_buffer[BUFFER_COUNT]
2. 假设两个基本函数已经实现(你可以假定两个函数都能正常工作,不会抛出异常):
// downloads a block from Internet sequentially in each call
// return true, if the entire file is downloaded, otherwise false.
bool GetBlockFromNet(Block * out_block);
 
// writes a block to hard disk
bool WriteBlockToDisk(Block * in_block);
上述的想法可以用代码清单1-1中的伪代码实现。
image007.gif
while(true)
{
 bool isDownloadCompleted;
 isDownloadCompleted = GetBlockFromNet(g_buffer);
 WriteBlockToDisk(g_buffer);
 if(isDownloadCompleted)
 break;
}
可以看到,在上述方法中,我们要下载完一块数据之后才能写入硬盘。下载数据和写入硬盘的过程是串行的。为了提高效率,我们希望能够设计两个线程,使得下载和写硬盘能并行进行。
线程A:从网络中读取一个数据块,存储到内存的缓存中。
线程B:从缓存中读取内容,存储到文件中。
试实现如下子程序:
1. 初始化部分
2. 线程A
3. 线程B
你可以使用下面的多线程API(如代码清单1-2)。
image009.gif
class Thread
{
public:
 // initialize a thread and set the work function
 Thread(void (*work_func)());
 // once the object is destructed, the thread will be aborted
 ~Thread();
 // start the thread
 void Start();
 // stop the thread
 void Abort();
};
 
class Semaphore
{
public:
 // initialize semaphore counts
 Semaphore(int count, int max_count);
 ~Semaphore();
 // consume a signal (count--), block current thread if count == 0
 void Unsignal();
 // raise a signal (count++)
 void Signal();
};
 
class Mutex
{
public:
 // block thread until other threads release the mutex
 WaitMutex();
 // release mutex to let other thread wait for it
 ReleaseMutex();
};
如果网络延迟为L1,磁盘I/O延迟为L2,将此多线程与单线程进行比较,分析这个设计的性能问题,并考虑是否还有其他改进的设计方法?

- flyinghearts flyinghearts:
实际上是设计一个下载器,希望多讨论些实现一个下载器的一些设计细节。比如支持断点续传,多线程分块下载。
- gaobo gaobo@flyinghearts:
感觉这个题目就是想说明对称美,确实没包含真正一个下载器的设计细节

1.11 NIM(1)一排石头的游戏 ★

面试是一个让面试双方互相增进了解的过程,不一定总是你问我答,有时候两人可以玩一些游戏,比如:
N块石头排成一行,每块石头有各自固定的位置(如图1-5所示)。两个玩家依次取石头,每个玩家每次可以取其中任意一块石头,或者相邻的两块石头,石头在游戏过程中不能移位(即编号不会改变),最后能将剩下的石头一次取光的玩家获胜。
这个游戏有必胜策略吗?
image118.jpg
图1-5

1.12 NIM(2)“拈”游戏分析 ★★★

我们再来看一个类似的游戏。
有N块石头和两个玩家A和B,玩家A先将石头分成若干堆,然后按照BABA……的顺序不断轮流取石头,能将剩下的石头一次取光的玩家获胜(如图1-6所示)。每次取石头时,每个玩家只能从若干堆石头中任选一堆,取这一堆石头中任意数目(大于0)个石头。
请问:玩家A要怎样分配和取石头才能保证自己有把握取胜?
image125.jpg
图1-6





1.13 NIM(3)两堆石头的游戏 ★★★
在前面两个题目中,我们讨论了被称为“NIM(拈)”的这种游戏及其变种的玩法和必胜策略,下面我们将讨论这类游戏的另一种有趣的玩法。
假设有两堆石头,有两个玩家会根据如下的规则轮流取石头:
每人每次可以从两堆石头中各取出数量相等的石头,或者仅从一堆石头中取出任意数量的石头;
最后把剩下的石头一次拿光的人获胜,如图1-7所示。
例如,对于数量分别为1和2的两堆石头,取石头的第一个玩家必定将会输掉游戏。因为他要么只能从任意一堆中取一块石头,要么只能从两堆中各取出一块石头。但无论他采用哪种方式取,最后,剩下的石头总是恰好能被第二个玩家一次取光。
定义一个函数如下:

要求返回一个布尔值,表明首先取石头的玩家是否能赢得这个游戏。
image129.jpg
图1-7

- matrix67 matrix67
看完NIM这几节,非常精彩。提几个建议
1. 筛质数的比喻非常贴切,但我建议在筛质数和NIM(3)之间加入一个一维的必胜必败态筛选例子作为过渡,读者会更容易理解。我喜欢举的一个例子是,一堆硬币共n个,游戏双方轮流取硬币,规定一次只能取1枚、2枚或4枚,先取完者胜。
2. 既然讲到NIM,应该提一下impartial game。可以点明,筛选必胜必败态是impartial game的“万能解法”,先筛出结果再在此基础上寻找规律,是寻求简单必胜策略的常见思路。
3. NIM(3)中的数列是Beatty数列,有一定的普遍性和实际应用,可以提一下
4. 几个扩展问题都偏难了,可以多加一些简单的组合游戏
5. 有些不解的是,NIM(4)的提示中,为什么要加一个“好像”?

1.14 连连看游戏设计 ★★

连连看是一种很受大家欢迎的小游戏。微软亚洲研究院的实习生们就曾经开发过一个类似的游戏——Microsoft Link-up。
图1-8为Microsoft Link-up的一个截图。如果用户可以把两个同样的图用线(连线拐的弯不能多于两个)连到一起,那么这两个头像就会消掉,当所有的头像全部消掉的时候,游戏结束。游戏头像有珍稀动物、京剧脸谱等。Microsoft Link-up还支持用户输入的图像库,微软的同事们曾经把新员工的漫画头像加到这个游戏中,让大家在游戏之余也互相熟悉起来。
image146.jpg
图1-8
假如让你来设计一个连连看游戏的算法,你会怎么做呢?要求说明:
1. 怎样用简单的计算机模型来描述这个问题?
2. 怎样判断两个图形能否相消?
3. 怎样求出相同图形之间的最短路径(转弯数最少,路径经过的格子数目最少)?
4. 怎样确定死锁状态,如何设计算法来解除死锁?

1.15 构造数独 ★★★

数独(日语:数独,sudoku)是一个历史悠久,最近又特别流行的数学智力游戏。它不仅具有很强的趣味性,而且能锻炼我们的逻辑思维能力。数独的“棋盘”是由九九八十一个小方格组成的。玩家要在每一个小格中,分别填上1至9的任意一个数字,让整个棋盘每一列、每一行,以及每一个3×3的小矩阵中的数字都不重复。
据说“数独”游戏在日本非常流行,在地铁车厢和候车室里,每天都可以看到人们埋头于游戏的情景,甚至有专门的“数独”游戏机出现。
现在很多杂志和报纸上的游戏专版也有数独栏目,一般的方式是提供一个不完整的数独,让读者填完所有数字。
既然数独这个游戏这么好玩,我们也写一个吧!图1-9是作者写的一个数独游戏的初始画面。
image151.jpg
图1-9
在面试中,由于时间限制,面试者不会期望应聘者写出全部程序,一般会要求回答设计中的几个关键问题,例如:
程序的大致框架是什么?用什么样的数据结构存储数独游戏中的各种元素?如何生成一个初始局面?

- michaelpeng michaelpeng Peter Norvig的一篇用Python解数独的文章:http://norvig.com/sudoku.html
- tintalk tintalk Section 1.15, Page 94 has a typo, where "GenarateValidMatrix()" should be "GenerateValidMatrix()".

- lzprgmr lzprgmr 连连看和数独感觉都是非常好的题目,分别应用了广度优先搜索和深度优先搜索算法。建议是在数独后加个扩展问题:如何用程序解数独(应该也是深度优先搜索)==


- flyinghearts flyinghearts:本题最好和另一道合并,集中介绍数独的相关知识。
两个解法都没有解决“如何生成初始局面”。书上的解法是在一个解上随机删除数字,但却忽视了数独的一个重要特征——“解是唯一”, 如果有两个以上解,就不应该称为数“独”。随机删除格子构建好的局面,必须判断是否有两种以上的解。

书上关于构建一个解的方法太麻烦了。实际上,只要几步操作就可以了:
第1行全部填充为:1 2 3 4 5 6 7 8 9,
后面的行中的数字均为第一行数字加上一个常数k(1<=k<=8),如果和大于9就减去9。
(显然第2行和第3行加的数是3或6 )
第4-6行,为前3行加上一个数a(第4行为第1行+a,第5行为第2行+a,数可取1)
第7-9行,为前3行加上一个数b(比如2)
(注意到前3行的第一列的数除以3的余数相同,因而可取a%3 和 b%3 分别为1或2)

得到1个解后,再用洗牌算法,生成一个1-9不重复的随机序列,将解中的1-9个数字分别映射到这个序列。

代码:
const int M = 3, N = M * M;
int arr[N] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
int extra[N] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
srand(clock());
 
//struct Block { int t[M]; };
//Block *block = reinterpret_cast<Block*>(extra);
//std::random_shuffle(block + 1, block + M);
//
//for (int i = 0; i < N; i += M)
// std::random_shuffle(extra + i, extra + i + M);
 
std::random_shuffle(arr, arr + N);
 
for (int i = 0; i < N; ++i) {
 for (int k = extra[i] - 1, j = 0; j < N; ++j)
 printf(" %d", (arr[j] + k) % 9u + 1);
 printf("\n");
}
printf("\n");

- matrix67 matrix67 同上,删掉数字的同时必须满足解是唯一的。这将会带来另一系列有趣的问题:一个合法数独(有唯一解的数独)至少要提供多少个数字?最多可以有多少个“零条件规则区域”?这都是很有趣的编程问题。查看更多:
http://www.matrix67.com/blog/archives/725


1.16 24点游戏 ★★★

24点是一种老少咸宜的游戏,它的具体玩法如下:
给玩家4张牌,每张牌的面值在1~13之间,允许其中有数值相同的牌。采用加、减、乘、除四则运算,允许中间运算存在小数,并且可以使用括号,但每张牌只能使用一次,尝试构造一个表达式,使其运算结果为24。
请你根据上述游戏规则构造一个玩24点游戏的算法,要求如下。
输入:n1, n2, n3, n4 。
输出:若能得到运算结果为24,则输出一个对应的运算表达式。

输入:11, 8, 3, 5
输出:(11-8)×(3+5)= 24
- micaelpeng micaelpeng:我写过一篇关于24点的博客, 提供了使用后缀表达式解24点游戏的一个思路,添加新的二元运算符相对也比较容易.

- flyinghearts flyinghearts:
应该补充: 如何在输出结果中,怎样去除多余的括号,使输出结果可读性更好。
另外,还可以增加扩展题: 找出所有的独立的解。
- gaobo gaobo@flyinghearts:
去掉多余括号是一个问题,另外还有就是去掉显而易见的变换,也就是看起来“不同”的解(例如:明显的交换律),不过这个“不同”到什么程度需要定义。

- gaobo gaobo
这个问题我弄了个解法:
http://yishan.cc/blogs/gpww/archive/2011/04/20/1812.aspx

- matrix67 matrix67
可以扩展的问题还有,在 1 2 3 4 5 6 7 8 9 中间添加加减号,使算式等于100。例如:12 + 3 - 4 + 5 + 67 + 8 + 9 = 100。数字顺序不能改变,相邻数字可以相连,给这个问题带来了很多新的元素。如果允许加乘除号、括号,甚至小数点的话,问题会更有意思。

还有一个类似的问题非常适合补充:算出一个指定的数需要多少个数字1?可以用加减乘除,可以把若干个1连接起来。
例如,算2011可以用11个1:(1111 - 111) * (1 + 1) + 11 = 2011
如果允许乘方运算,就更好玩了。算出2011只需要用10个1:(11 - 1) ^ (1 + 1 + 1) * (1 + 1) + 11 = 2011
用10个1算出2011还有一个更妙的方法:(1 + 1) ^ 11 - 111/(1 + 1 + 1) = 2011
怎样找出这些解,无疑是一个非常吸引人的问题。

更有意思的问题则是找出这样的算式:
343 = (3 + 4) ^ 3,
4096 = (4 + 0 * 9) ^ 6
16384 = 16 ^ 3 * (8 - 4)

另外两种值得一提的扩展问题:
http://www2.stetson.edu/~efriedma/multi/
http://www2.stetson.edu/~efriedma/form/

1.17 俄罗斯方块游戏 ★★★

俄罗斯方块(英文:Tetris)是从20世纪80年代开始风靡全世界的电脑游戏。俄罗斯方块是由下面这几种形状的积木块构成,如图1-10所示。
image190.jpg
图1-10
如果你说你没玩过Tetris游戏,面试者一定会比较惊讶,不过面试者还是会耐心地跟你解释它的游戏规则:
n 积木块会从游戏区域上方开始缓慢落下。
n 玩家可以做的操作有:90度旋转积木块,左右移动积木块,或者让积木块加速落下。
n 积木块移到游戏区域最下方或是落到其他积木块上无法移动时,就会固定在该处,而之后新的积木块就会出现在区域上方开始落下。
n 当游戏区域中某一行格子全部由积木块填满,则该行会消失并成为玩家的得分。一次删除的行数越多,得分越多。
n 当积木块堆到区域最上方,则游戏结束。
好,现在的问题是:
1. 如果你是设计者,如何设计各种数据结构来表示这个游戏的各种元素,如每一个可活动的积木块、在底层堆积的积木等。
2. 现在已经知道底层积木的状态,然后在游戏区域上方出现了一个新的积木块,你如何运用刚才设计的数据结构来判断新的积木块要如何移位或旋转,才能最有效率地消除底部累积的积木?
3. 有些版本的Tetris游戏有一个预览窗口,从预览窗口可以看到下一个积木块是什么形状。玩家这时候就可以提前计划,比如,如果下一个积木块是一根长条,我们就不要把最深的“峡谷”堵住。那么我们有了这个新的参数,如何改写上一个程序,才能最有效率地消除底部累积的积木?

1.18 挖雷游戏 ★★★

挖雷(Minesweeper)游戏很受Windows用户的喜爱,它的游戏规则很简单,盘面上有数字标明周围地雷的数量,游戏者根据数字提示,清除没有地雷的方块,标出盘面上的所有地雷即可,如图1-11所示。
image208.jpg
图1-11
这样一个“古老”的游戏,有什么可以挖掘的呢?
问题1:如果用户想为这个“古老”的游戏增加一个新功能,即按一个功能键,就能看到剩余所有未标识的方块是否有地雷的概率。你能否实现这一功能?
问题2:如果上一个问题太难了,可以让程序先标识所有肯定有地雷的方块。

- uniquestudio uniquestudio1.18的扫雷游戏和4.11扫雷游戏的概率有点重复,可以考虑将两题合并。最好有高人得出解法,然后放在最后一题作为凤尾。
  1. ^ 当面试的同学听到这个问题的时候,很多人都有点意外。我把我的笔记本电脑交给他们说,这是开卷考试,你可以上网查资料,干什么都可以。大部分面试者在电脑上的第一个动作就是上网搜索“CPU 控制50%”这样的关键字,当然没有找到什么直接的结果。不过本书出版以后,情况可能就不一样了。
  2. ^ 这是我们为了计算的方便而制定的价钱,不保证8欧元可以买到这样的书。
  3. ^ CS:英文名称为Half-life或Counter-Strike,一种风靡全球的第一人称动作类枪战游戏。
  4. ^ 在设计中,曲线也可以用一组直线来模拟以简化模型,加快速度。