逻辑题库
手机无线连接电脑-
逻辑题库
1
、考虑一
个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。她们需要
在桌子上
轮流放置硬币
,
每次必需且只能放置一枚硬币
< br>,
要求硬币完全置于桌面内
(
不
能有一
部分悬在桌子外面
),
并且不能
与原来放过的硬币重叠。谁没有地方放置新的硬币
,
谁就输了。
游戏的先行者还就是后行者有必胜策略？这种策略就是什么？
答案
:
先行者在桌子中心放置一枚硬币
,
以后的硬币总就是放在与后
行者刚才放的地方相
对称的位置。这样
,
只要后行者能放
,
先行者一定也有地方放。先行者必胜。
2
、
用线性
时间与常数附加空间将一篇文章的单词
(
不就是字符
)
倒序。
答案
:
先将整篇文章的所有字符逆序
(
从两头起不断交换位置相对称的字符
);<
/p>
然后用同样的
办法将每个单词内部的字符逆序。这样
,
整篇文章的单词顺序颠倒了
,
但单词本身又被转回来
了。
3
、
用线性
时间与常数附加空间将一个长度为
n
的字符串向左循环移动
m
位
(
例
如
,
移动
3
位就变成了
。
答案
:
把字符串切成长为
m
与
n-m
的两半。
将这两个部分分别逆序
,
再对整个字符串逆序。
4
、一个矩形蛋糕
,
蛋糕内部
有一块矩形的空洞。只用一刀
,
如何将蛋糕切成大小相等的两<
/p>
块？
答案
:
注意到平分矩形面积的线都经过矩形的中心。过大矩形与
空心矩形各自的中心画一
条线
,
这条线
显然把两个矩形都分成了一半
,
它们的差当然也就是相等的。<
/p>
5
、
一块矩
形的巧克力
,
初始时由
N x M
个小块组成。每一次您只能把一块巧克力掰成两
个小矩形。最少需要
几次才能把它们掰成
N x M
块
1x
1
的小巧克力？
答案
:N x M - 1
次显然足够了。
这个数目也就是必需的
,
因为每掰一次后当前巧克力的块数
只能增加一
,
把巧克力分成
N x
M
块当然需要至少掰
N x M -
1
次。
6
、
如何快速找出一个
32
位整数的二进制表达里有多少个
？用关于
的个数的线性时
间？
答案
1(
关于数字位数线性
):for(n=0; b; b >>= 1) if
(b & 1) n++;
答案
2(
关于
的个数线性
):for(n=0; b; n++) b &= b-1;
7
、
一个大
小为
N
的数组
,
所有数都就是不超过
N-1
的正整数。用
O(N)
的时间找出重复
的那个数
(
假设只有一个
)
。一个大小为
N
的数组
,
所有数都
就是不超过
N+1
的正整数。用
O(N
)
的时间找出没有出现过的那个数
(
假
设只有一个
)
。
答案
:
计算数组中的所有数的与
,
再计算出
从
1
到
N-1
的所有数的与
,
两者之差即为重复的
那
个数。
计算数组中的所有数的与
,
再计
算出从
1
到
N+1
的所有数的与
,
两者之差即为缺少的
那个数。
逻辑题库
8
、
给出一
行
C
语言表达式
,
判断给定的整数就是否就是一个
2
的幂。
< br>
答案
:(b &
(b-1)) == 0
9
、地球上有多少个点
,
使得从该点出发向南走一英里
,
< br>向东走一英里
,
再向北走一英里之后恰
< br>好回到了起点？
答案
:“
北极点
”
就是一个传统的答案
,
其实这个问题还有其它的答案。
事实上
,
满足要求的点
有无穷多个。
所有距离南极点
1 + 1/(2π)
英里的地方都就是满足要求的
,
向南走一英里后到
达
距离南极点
1/(2π)
的地方
,
向东走一英里后正好绕行纬度圈一周
,<
/p>
再向北走原路返回到起点。
事实上
,
这仍然不就是满足要求的全部点。
距离南极点
1 + 1/(2kπ)
的地方都就是可以的
,
其中
k
可以就是任意一个正整数。
< br>
10
、
A
、
B
两人分别在两座
岛上。
B
生病了
,A
< br>有
B
所需要的药。
C
有一艘小船与一个可
以上锁的箱子。
C
愿意在
A
与
B
之间运东西
,
但东西只能放在箱子里。只要箱子没
被上锁
,C
都会偷走箱子里的东西
,<
/p>
不管箱子里有什么。如果
A
与
B
各自有一把锁与只能开自己那把锁
的钥匙
,A
应该如何把东西安全递交给
B
？
答案
:A
把药放进箱子
,
用自己的锁把箱子锁上。
B
拿到箱子后
,
再在箱子上加一把自己的锁。
箱子运回
A
后
,A
取下自己的锁。箱子再运到
B
手中时
,B
取下自己的锁
,
获得药物。
11
、
一对
夫妇邀请
N-1
对夫妇参加聚会
(
因此聚会上总共有
2N
人
< br>)
。每个人都与所有自
己不认识的人握了一次手。
然后
,
男主人问其余所有人
< br>(
共
2N-1
个人
)
各自都握了几次手
,
得到
的答案全部都不一样。假设每个人都认识自己的配偶
,
那么女主人握了几次手？
答案
:
握手次数只可能就是从
0
到
2N-2
这
< br>2N-1
个数。除去男主人外
,
一共有
2N-1
个人
,
因此每个数恰好出现了一次。其中有一个人
(0)
没有
握手
,
有一个人
(2N-2)
与所有其它的夫妇
都握了手。这两个人肯定就是一对夫妻
,
否则后者将与前者握手
(
从
而前者的握手次数不再就
是
0)
。
除去这对夫妻外
,
有一个人
(1)
只与
(2N-2)
握过
手
,
有一个人
(2N-3)
与除了
(0)
以外的其它
夫妇都握了手。这两个人肯定就是一对夫妻
,
否则后者将与前者
握手
(
从而前者的握手次数不
再就是<
/p>
1)
。
以此类推
,
直到握过
N-2
次手的人与握过
N
次手的人配成一对。
此时
,
除了男主人
及其配偶以外
,
其余所有人都已经配对。根据排除法
,
最后剩下来的那个握手次数为
N-1
的人
就就是女主人了。
<
/p>
12
、两个机器人
,
初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序
,
使得这两个机器人保证可以相遇。程序只能包含
“
左
移
n
个单位
”
、
“
右移
n
个
单位
”,
条件判断
语句
If,
循环语句
while,
以及两个返回
Boolean
值的函数
“
在自己的起点处
”
与
“
在对方的起点
处
”
。您不能使用其它的变量与计数器。
逻辑题库
< br>答案
:
两个机器人同时开始以单位速度右移
,
直到一个机器人走到另外一个机器人的起点
处。然
后
,
该机器人以双倍速度追赶对方。程序如下。
while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}
13
、
如果
叫您从下面两种游戏中选择一种
,
您选择哪一种？为什么？
a
、
写下一
句话。如果这句话为真
,
您将获得
10
美元
;
如果这句话为假
,
您获得的金钱将
少于
10<
/p>
美元或多于
10
美元
(
但不能恰好为
10
美元
)
。
b
、
写下一
句话。不管这句话的真假
,
您都会得到多于
10
美元的钱。
答案
:
选择第一种游戏
,
并写下
“
我既不会得到
10
美元
,
也不会得到<
/p>
10000000
美元
”
。
14
、您在一幢
100
层大楼下
,
有
21
根电线线头标有数字
1
、、
21<
/p>
。这些电线一直延伸到
大楼楼顶
,
楼顶的线头处标有字母
A
、、
U
。您不知道下面的数字与上面的字母的对应关系。
您
有一个电池
,
一个灯泡
,
与许多很短的电线。如何只上下楼一次就能确定电线线头的对应关
系？
答案
:
在下面把
2,3
连在一起
,
把
4
到
6
全连在一起
,
把
7
到
10
全连在一起<
/p>
,
等等
,
这样您
就
把电线分成了
6
个
< br>“
等价类
”,
大小分别为
1, 2, 3, 4, 5, 6
。然后到楼顶
,
测出哪根线与其它所有
电线都不相连
,
哪些线与另外一根相连
,
哪些线
与另外两根相连
,
等等
,
从而确定出字母
A
、、
U<
/p>
各属于哪个等价类。现在
,
把每个等价类
中的第一个字母连在一起
,
形成一个大小为
6
的新等
价类
;
< br>再把后
5
个等价类中的第二个字母连在一起
,
形成一个大小为
5
的新等
价类
;
以此类推。
回到楼下
,
把新的等价类区别出来。这样
,
您就知道了每个数字对应了哪一个原等价类的第几
个字母
,
从而解决问题。
15
、
某种药方要求非常严格
,
您每天需要同时服用
A
、<
/p>
B
两种药片各一颗
,
不能多也不能少。
这种药非常贵
,
您不希望有任何一点的浪费。
一天
,
您
打开装药片
A
的药瓶
,
倒出一粒药片放在
手心
;
然后
打开另一个药瓶
,
但不小心倒出了两粒药片。
< br>现在
,
您手心上有一颗药片
A,
两颗药片
B,
并且您无法区别哪个就是
A,
哪个就是
B
。您如何才能严格遵循药方服用药片
,
并且不能有
任何的浪费？
答案
:
把手上的三片药各自切成两半
,
分成两堆摆放。再取出一粒药片
A,
也
把它切成两半
,
然后在每一堆里加上半片的
A
。现在
,
每一堆药片恰好包含两
个半片的
A
与两个半片的
B
。
一天服用其中一堆即可。
逻辑题库
16
、
您在
一个飞船上
,
飞船上的计算机有
n
个处理器。突然
,
飞船受到外星激光武器的
攻击
,
一些处理器被损坏了。
您知道有
超过一半的处理器仍然就是好的。
您可以向一个处理器询问
另一
个处理器就是好的还就是坏的。一个好的处理器总就是说真话
,
一个坏的处理器总就是
说假话。用
n-2
次询问找出一个好的处理器。
答案
:
给处理器从
1
到
n
标号。
用符号<
/p>
a->b
表示向标号为
a
的处理器询问处理器
b
就是
不
就是好的。首先问
1->2,
如果
1<
/p>
说不就是
,
就把她们俩都去掉
(
去掉了一个好的与一个坏的
,
< br>则剩下的处理器中好的仍然过半
),
然后从
3->4
开始继续发问。如果
1
说
2
就是好的
,
< br>就继续
问
2->3,3-
>4,
……
直到某一次
j
说
< br>j+1
就是坏的
,
把
j
与
j+1
去掉
,
然后问
j-1 ->
j+2;
或者从
j+2
-> j+3
开始发问
,
如果前面已经没有
j-1
了
(
之前已经被
去掉过了
)
。注意到您始终维护着这样
一个
“
链
”,
前面的每一个处理器都说后面那个就是好的。
这条链里的所有处理器要么都就是好
的
,
要么都就是坏的。
当这条链越来越长
,
剩下的处理器越来越少时
,
总有一个时候这条链超过
了剩下的处理器的一半
,
此时可以肯定这条链里的所有处理器都就是好的。或者
,
越来越多的
处理器都被去掉了
< br>,
链的长度依旧为
0,
而最后只
剩下一个或两个处理器没被问过
,
那她们一定
< br>就就是好的了。另外注意到
,
第一个处理器的好坏从来没
被问过
,
仔细想想您会发现最后一个
处
理器的好坏也不可能被问到
(
一旦链长超过剩余处理器的一半<
/p>
,
或者最后没被去掉的就只
剩这一个了时
,
您就不问了
),
因此询问次数不会超过
n-2
。
17
、一个圆盘被涂上了
黑白二色
,
两种颜色各占一个半圆。圆盘以一个未知的速度、按
一个未知的方向旋转。
您有一种特殊的相机可以让您即时观察到
圆上的一个点的颜色。
您需
要多少个相机才能确定圆盘旋转的方
向？
答案
:
您可以把两个相机放在圆盘上相近的两点
,
然后观察哪个点先变色。
事实上
,
只需要
一个相机就够了。控制相机绕圆盘中心顺时针移动
< br>,
观察颜色多久变一次
;
然后让
相机以相同
的速度逆时针绕着圆盘中心移动
,
< br>再次观察变色的频率。可以断定
,
变色频率较慢的那一次
,
相机的转动方向就是与圆盘相同的。
18
、
有
25
匹马
,
速度都不同
,
但每匹马的速度都就是定值。现在只有
5
条赛道
,
无法计时
,
即每赛一场最多只能知道
5
匹马的相对快慢。问最少赛几场可以找出
25
匹
马中速度最快的
前
3
名？
(
百度
2008
年面试题<
/p>
)
每匹马都至少要有一次参赛的机会
,
所以
25
匹马分成
5
组
,
一开始的这
5
场比赛
就是免不了的。接下来要找冠军也很容易
,
每一组的冠军在一起赛一场就行了
(
第
6
场
)
。最后就就是要找第
2
与第
3
名。我们按照第
6
场比赛中得到
的名次依次
把它们在前
5
场比赛中所在
的组命名为
A
、
B
、
C
、
D
、
E
。即
:A
组的冠军就是第
6
场的第
1
名
,B
组的冠军就是第
6
场的第
2
名
…
…
每一组的
5
匹马按照她们已
经赛出的成绩从快到慢编号
: