分钟之类的

题目，火星得已经可以考古了，这 里就不再说了。个别题目本

Blog

原来有过详

细的介绍，这里也不再提了。

1.

考虑一个双人游戏。

游戏在一个圆桌上进行。

每个游戏者都有足 够多

的硬币。

他们需要在桌子上轮流放置硬币，

每次必需且只能放置一枚硬币，

要求

硬币完全置于桌面 内

（不能有一部分悬在桌子外面）

，

并 且不能与原来放过的硬

币重叠。

谁没有地方放置新的硬币，

谁就输了。

游戏的先行者还是后行者有必胜

策略？这种策略是什么？

答案：先行者在桌子中心放置一枚 硬币，以后的硬币总是放在与后行者

刚才放的地方相对称的位置。这样，只要后行者能放 ，先行者一定也有地方放。

先行者必胜。

2.

用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。

答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的

< br>字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词

顺 序颠倒了，但单词本身又被转回来了。

3.

用线性时间和常数附加空间将一个长度为

n

的字符串向左循环移 动

m

位（例如，”abcdefg”移动

3

位就变成了”defgabc”）。

答案：把字符串切成长为

m

和

n-m

的两半。将这两个部分分别逆序，再

对整个字 符串逆序。

4.

一个矩形蛋糕，

只用一刀，

如何将蛋 糕

切成大小相等的两块？

答案： 注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩

形各自的中心画一条线，

这条线显然把两个矩形都分成了一半，

它们的差当然也

是相等的。

5.

一块矩形的巧克力，初始时由

N

x

M

个小块组成。每一次你只能把一

块巧 克力掰成两个小矩形。最少需要几次才能把它们掰成

N x M

块

1×1

的小巧

克力？

答案：

N x M - 1

次显然足够了。这个数目也是必需的，因为每掰一次

后当前巧克力的块数 只能增加一，把巧克力分成

N x M

块当然需要至少掰

N x M

- 1

次。

6.

如何快速找出一个

32

位整数的二进制表达里有多少个”1″？用关

于”1″的个数的线性时间？

答案

1< /p>

（关于数字位数线性）：

for(n=0; b; b >>= 1) if (b & 1) n++;

答案

2< /p>

（关于”1″的个数线性）：

for(n=0; b; n++) b &= b-1;

7.

一个大小为

N

的数组，所有数都是不超过

N-1

的正整数。用

O(N)

的

时间找出重复的那个数（假设只有 一个）。一个大小为

N

的数组，所有数都是不

< br>超过

N+1

的正整数。用

O(N )

的时间找出没有出现过的那个数（假设只有一个）。

1

文档来源为

:

从网络收集整理

.word

版本可编辑

.

欢迎下载支持

.

答案： 计算数组中的所有数的和，再计算出从

1

到

N-1

的所有数的和，

两者之差即为重复的那个数。计算数 组中的所有数的和，再计算出从

1

到

N +1

的所有数的和，两者之差即为缺少的那个数。

8.

给出一行

C

语言表达式，判断给定的整 数是否是一个

2

的幂。

答案：

(b & (b-1)) == 0

9.

地球上有多少个点，使得从该点出发向南走一英里，向东走一英里，

再向北走一英里之后恰好回到了起点？

答案： “北极点”是一个传统的答案，其实这个问题还有其它的答案。

事实上，满足要求的点有 无穷多个。所有距离南极点

1 + 1/(2π)英里的地方都

是满足要求的，向南走一英里后到达距离南极点

1/(2π)的地方，向东走一英里

后正好绕行纬度圈一周，

再向北走原路返回到起点。

事实上，

这仍然不是满足要

求的全部点。距离南极点< /p>

1 + 1/(2kπ)的地方都是可以的，其中

k

可以是任意

一个正整数。

10.

A

、

B

两人分别在两座岛上。

B

生病了，

A

有

B

所需要的药。

C

有一艘

小船和一个可以上锁的箱子。

C

愿意在

A

和

B

之间运东西，但东西只能放在箱子

里。只要箱子没被上锁，

C< /p>

都会偷走箱子里的东西，不管箱子里有什么。如果

A

和

B

各自有一把锁和只能开自己那把锁的钥匙，

A

应该如何把东西安全递交给

B