给定一个集合S和数n，从集合S中取出两个不同的数a,b满足a+b=n的总方案数叫做“集合S中关于n的互补数对个数”。是否有可能把全体非负整数划分为A、B两个集合，使得对于任意一个n，集合A和集合B中关于n的互补数对的个数都相同？

 
Read more…

1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。

2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

题目来源：http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1

Read more…

    三个人坐成一个圆圈，每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在，他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对，并且没有人猜错，那他们就获胜了；只要有任何一个人猜错，或者所有人都写的“放弃”，那么他们就输了。如果在游戏开始前他们能够商量一个策略，那么最好的策略是什么？
    仔细想一下你会发现，要想保证他们百分之百地获胜是不可能的，因为游戏中大家不能交流信息，谁也不能保证自己能猜对。但是，有一种策略能保证他们有75%的几率获胜。事实上，当人数n=2^k-1时，我们有一种方法可以让获胜的概率达到(2^k-1)/(2^k)。你能想到这种策略吗？

    设身处地地想，你会想到一个很自然的策略：如果一个人看到另外两个人的帽子颜色一黑一白，那这个人就放弃（换了你你也不敢猜）；如果另外两个人的帽子颜色一样，那你就猜相反的颜色（概率上看也要大些）。我们来看一下在哪些情况下使用这样的策略能够获胜：

3个黑帽子：每个人都看到两个黑帽子，每个人都猜自己是白帽子，所有人都猜错；
2个黑帽子，1个白帽子：戴黑帽子的人看到一黑一白，于是放弃；戴白帽子的人看的是两个黑帽子，因此他将猜对，从而所有人都获胜；
2个白帽子，1个黑帽子：和上面这种情况是类似的，所有人都将获胜；
3个白帽子：和第一种情况是类似的，所有人都猜错。

    注意到只有在第一种情况和第四种情况下才会输掉游戏，这两种情况占了所有情况的2/8。于是，使用这种策略有75%的概率获胜。

    我们需要想一想，在这个看似几乎不可能获胜的游戏中，为什么这种策略会有如此高的获胜概率。最关键的就是，这种策略充分利用了胜负判断的准则：大家要错就一起错，只有一个人错怪划不来的；要获胜就只让一个人猜对，多几个人同时猜对也没用。

    根据上面的讨论，我们开始尝试把游戏的人数推广到一般的n。为了叙述方便，我们把每个人头顶上的帽子颜色依次用0和1来表示，数字1表示黑帽子，数字0表示白帽子。于是所有可能的情况就是2^n个01串。游戏开始前n个人预先约定一些“保留串”。他们的策略就是，观察其余n-1个人的帽子颜色：如果和所有的保留串都不匹配里，则放弃；如果恰好符合某个保留串，就猜自己是相反的颜色。比如，当n=3时，他们可以约定两个保留串000和111。如果实际情况是001的话，前两个人看到的是?01和0?1，不属于任何一个保留串，于是放弃；第三个人看到的是00?，正好和000相符，于是他就反过来猜自己不是那个0。注意到一些有趣的事实：如果实际情况恰好就是这些保留串之一，那大家就全猜错了；如果实际情况与所有保留串都相差两个数字以上，那大家全部放弃；如果实际情况与某个保留串恰好差一个数字，那只有一个人猜对，其余人放弃，从而获得胜利。现在的问题就是，如何寻找一个保留串集合，使得和某个保留串只差一个数字的情况尽可能的多。注意，我们必须要保证，任意两个保留串之间不能只差一个数字，这样的话才能保证发现有相符保留串的人不会面临“两可”的情况。假如你找到了t个保留串，则保证获胜的情况最多有t*n个（每个串“变一位”都有n种方法）。显然，最完美的情况就是t+t*n恰好等于总的情况数2^n。当n=2^k-1时，t+t*n是有可能恰好等于总情况数2^n的，也就是说每种可能的情况要么就是一个保留串，要么与唯一的一个保留串恰好差一位。此时，t+t*n=t(n+1)=t*(2^k)=2^(2^k-1)，t应该等于2^(2^k-1-k)。下面我们说明这t个保留串是如何生成的。
    每个保留串都由原码和校验码两部分组成。我们把n位01串的位置编号转化为二进制，二进制里只有一个数字1的位置（即左起第1,2,4,8,…位）叫做校验码，有至少两个1的位置（3,5,6,7,9,…等其余位置）上的数字称作原码。显然，原码应该有n-k位（即2^k-1-k位）。枚举2^(n-k)种原码的01组合，对于每一组原码，定义第i个校验码的值为，除了它本身以外，所有编号的二进制表达中右起第i个数字为“1”的位置上一共有奇数个1还是偶数个1（相当于把标“x”的位置上的数异或一遍）。比如，第2个校验码是1，当且仅当有奇数个位置上的原码满足，位置编号的二进制表达形如…???1?且该位置上的数值正好也是1。所有可能的原码加上它对应校验码就是我们的保留串。

  01串:     a1  a2  a3  a4  a5  a6  a7
十进制编号:  1   2   3   4   5   6   7

二进制编号: 001 010 011 100 101 110 111
校验码1(a1):         x       x       x
校验码2(a2):         x           x   x
校验码3(a4):                 x   x   x
保留串0:     0   0   0   0   0   0   0
保留串1:     1   1   0   1   0   0   1
保留串2:     0   1   0   1   0   1   0
保留串3:     1   0   0   0   0   1   1
保留串4:     1   0   0   1   1   0   0
   ……      ……     ……        
保留串14:    0   0   1   0   1   1   0
保留串15:    1   1   1   1   1   1   1

    我们可以说明，对于任一个n位01串，只要它不是我们的保留串，我都有办法只变动一个数字让原码和校验码相符（从而变成一个保留串）。我们可以观察一下，由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同，直接把它改过来就是了；如果有多位校验码不同，那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑，这样的一位原码显然是唯一存在的。同时，我们可以保证任两个

    警告，千万不要去计算pi的二进制表达。数学家们猜想pi是一个正规数(normal number)，也就是说它包含了任意一个有限长的01串，所有n位长的01串都以相等的概率出现在pi的二进制中。

    如果你偏要去计算它，你会：

• 侵犯版权（包括所有书籍、小说、报纸、杂志、网站、音乐、电影、软件，甚至是Windows源码）；
• 侵犯商标权；
• 拥有大量非法的激情无码大片；
• 拥有大量国家最高机密；
• 制造出非法的DVD破解软件；
• 制造对小胡同志的恐吓信；
• 拥有所有人的身份证号、信用卡号、电话号码和各种密码；
• 亵渎伊斯兰教（理论上并不是非法的，但你下半辈子得和Salman Rushdie躲在一起）；
• 亵渎科学论派（非法！问问Keith Henson就知道）。

    同时，你的电脑里会包含有目前所有已知的最邪恶的电脑病毒──事实上还包括有所有未知的最邪恶的病毒。
    我的电脑上有很多极度私密的文件，我不希望你把它们浏览个遍。
    你或许想，我只计算几位就行了；但何必去冒这个险呢？谁也说不准，算到哪一位时你会找到关于Kennedy刺杀案的秘密文件，或者你邻居的六岁小女孩和家里的狗狗XX的恶心照片，或者还未发行的最新一部Star Wars的完整拷贝。反正，千万别去算它。
    同样的警告还适用于e、根号2、Euler常数、phi、除0以外的代数数的余弦值和其它各种各样的实数。
    这也是为什么这些数总是被表示成十进制数的原因。

来源：http://everything2.net/index.pl?node_id=1302963

    在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
    古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296…  这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 – a^2 – b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 – (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
    古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：

2      0; 30
3      0; 20
4      0; 15
5      0; 12
6      0; 10
8      0; 7, 30
9      0; 6, 40
10     0; 6
12     0; 5
15     0; 4
16     0; 3, 45
18     0; 3, 20
20     0; 3
….    ….

    
    古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。

    古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：

  46 x 22 = 1012
   1   22
   2   44     44
   4   88   + 88
   8  176  + 176
  16  352
  32  704  + 704
          ——-
            1012

    上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
    无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。

  46 x 22 = 1012
  46   22
  23   44     44
  11   88   + 88
   5  176  + 176
   2  352
   1  704  + 704
          ——-
            1012

做人要厚道
转贴请注明出处