智力题（第二集）

问题一：如何快速找出一个32位整数的二进制表达里有多少个”1”？用关于”1”的个数的线性时间？
答案：错误答案是
while(x){if(x&0x1)count++;x>>=1;}//当x为负数，那么这就是一个无限循环。
正确解答是：
while(x){x=x&(x-1);count++;}//这里就是最好的解答，并别x中有多少1就会循环几次，
效率高。
问题二：
用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，”abcdefg”移动3位就变成了”defgabc”）。
答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。
分析：这个方案的总共需要交换n次，如果换作另一种思路，m位m位向右移动，最好情况会比这种方法少
移动m位，最坏情况多移动(m-n%m)*m-m次。

#include <iostream>
#include <string.h>
using namespace std;
void runleftstring(char *ptr,int x)
{
    int n = strlen(ptr);
    int i=0;
    int j=n-1;
    char tmp;
    while(i<j)
    {
        tmp = ptr[i];
        ptr[i]=ptr[j];
        ptr[j]=tmp;
        i++;
        j--;
    }   
    int mid = n - x-1;
    j=mid;
    i=0;
    while(i<j)
    {
        tmp = ptr[i];
        ptr[i]=ptr[j];
        ptr[j]=tmp;
        i++;
        j--;
    }
    i=mid+1;
    j=n-1;
    while(i<j)
    {
        tmp = ptr[i];
        ptr[i]=ptr[j];
        ptr[j]=tmp;
        i++;
        j--;
    }
}
int main()
{   
    char s[]="abcdefg123456789";
    runleftstring(s,5);
    cout<<s<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

第三题：
给出一行C语言表达式，判断给定的整数是否是一个2的幂。
答案:if(x&(x-1)==0)那么这个整数就是2的幂。
分析:1，10，1000，10000，100000，1000000，2的幂就是2的n次方，那么就只能有一位是1，
其他位就必须是0，所以有x&(x-1)==0判断这个数是不是2的幂。
第四题：
考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，
每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放
过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
答案：先行者在中心放一枚硬币，以后方的硬币总是与后行者相对称的地方，这样只要后行者有地方放，那么先
行者必有地方放。策略先行者必胜。

第五题：
如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元
或多于10美元（但不能恰好为10美元）。
b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
答案：选择第一种游戏，写下：“我既不会得到10美元，也不会得到1000000000美元”.
分析：1.假设这句话是真话，a选项中如果这句话为真就获得10美元，但是我的这句话是我不会得到10美元
矛盾，所以不成立。
2.假设这句话是假话，a选项中如果这句话是假话会获得不等10美元，满足我既不会得到10美元这句话，
但是如果想我写的话是假话，那么只有第二句话是真话了，于是我将得到1000000000美元。

第六题：
某种药方要求非常严格，你每天需要同时服用A、B两种药片各一颗，不能多也不能少。这种药非常贵，你不
希望有任何一点的浪费。一天，你打开装药片A的药瓶，倒出一粒药片放在手心；然后打开另一个药瓶，
但不小心倒出了两粒药片。现在，你手心上有一颗药片A，两颗药片B，并且你无法区别哪个是A，哪个是B。
你如何才能严格遵循药方服用药片，并且不能有任何的浪费？
答案：将手心里面的药片每一片从中间分开，分成两堆，再取一片A药也分成2份，分别放置两堆中，每次服用
时只取一堆就OK。
分析：本来是服用1片A与1片B就刚好，可是多了1片B，将原来一堆的药片都从中间分开分成2堆，于是我们再取
1片A分成2片分别放入两堆里面，就可以求出来。

第七题：
一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。
你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？
答案：控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，
再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。
第八题：
地球上有多少个点，使得从该点出发向南走一英里，向东走一英里，再向北走一英里之后恰好回到了起点？
答案：传统答案是在北极点。实际上这个题的答案是无穷多个，距离南极点1+1/（2π）位置，此位置往
南走1英里，则r=1/2π，周长d=2πr=1,刚好等于要往东走的英里，于是又回到1/2π的位置，再往北走1就回到
了原点，依次类推，其实在1+1/(2kπ)（k=1,2,3,4….）的位置都可以回到原点。（pai把我纠结的）

第九题：
一对夫妇邀请N-1对夫妇参加聚会（因此聚会上总共有2N人）。每个人都和所有自己不认识的人握了一次手。
然后，男主人问其余所有人（共2N-1个人）各自都握了几次手，得到的答案全部都不一样。假设每个人都认识自己的配偶，
那么女主人握了几次手？
答案：N-1
分析：有2N-1个人，且他们握手次数都不相同，因为不可能跟自己握手，那么握手的范围是0-（2N-2），如果第一对夫妻中
的女士握手0次，那么该对夫妻中的男士可以握手2N-2次，第二对夫妻中的女士要跟第一对夫妻中的男士握手，那么第二对、
夫妻中的女士握手1次，该对夫妻中的男士握手2N-3次。。。以此类推，直到握过N-2次手的人和握过N次手的人配成一对。
此时，除了男主人及其配偶以外，其余所有人都已经配对。根据排除法，最后剩下来的那个握手次数为N-1的人就是女主人了。
第十题：
如何选择4个砝码可以称出40g以内的所有质量。
答案：1，3，9，27
分析：首先选择1g作为开始，这样我有了一个1g的砝码，我可以表示的质量范围是-1g到1g，我无法表示2g，于是，为了表示2g
的质量，我选择3g，因为3-1=2，为什么这样做？这样做是为了让我的可以表示范围更大一些，有了1，3我们可以表示的范围
是1到4g，同样无法表示5g,于是我们再取9g，5=9-4，这样就可以组合得到5g的表示，从而是取值范围最大化的呈现，此刻能
表示的大小范围是1-13，同理，表示到13已经是极限了，无法表示14g，于是我们选择27，因为27-13=14，刚好表示，此刻可以
表示的范围是1-40g,就是我们要求的结果。