递归

趣题：用最简单的话来描述一个集合

/ 5 条评论

    定义f(n)的值为将n拆分成若干个2的幂的和，且其中每个数字出现的次数不会超过两次的方案数。规定f(0)=1。
    例如，有5种合法的方案可以拆分数字10：1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 和 2+8。因此，f(10)=5。
    请用一句最简单的话来描述集合{ f(n)/f(n-1) }。证明你的结论。

    注意：答案远比一个递归公式来得精辟，来得巧妙。如果你发现了我们的结论，你会一眼认定它为正确答案。

    答案：数列{ f(n)/f(n-1) }以最简形式包含了所有的正有理数。

    如果n是奇数（等于2m+1），那么数字1（即2^0）必须出现且只能出现一次。现在的问题就是，2m的拆分方案中有多少个方案不含数字1呢？稍作思考你会立即发现，它就等于f(m)，因为m的所有拆分方案的所有数都乘以2后正好与不含1的2m拆分方案一一对应。因此，f(2m+1) = f(m)
    如果n是偶数（等于2m），那么数字1要么没有出现，要么恰好出现两次。对于前一种情况，我们有f(m)种可能的方案；第二种情况则有f(m-1)种方案。因此，f(2m) = f(m) + f(m-1)
    另外，显然f(k)都是正数。于是，f(2k-1) = f(k-1) < f(k-1)+f(k) = f(2k)
    这样，我们可以得到以下三个结论：

    结论1：gcd( f(n),f(n-1) ) = 1
    证明：对n进行数学归纳。显然gcd( f(1),f(0) ) = gcd(1,1) = 1
    假设对于所有小于n的数结论都成立。根据n的奇偶性，下面两式中必有一个成立：
    gcd( f(n),f(n-1) ) = gcd( f(2m+1),f(2m) ) = gcd( f(m), f(m)+f(m-1) ) = gcd( f(m),f(m-1) ) = 1
    gcd( f(n),f(n-1) ) = gcd( f(2m),f(2m-1) ) = gcd( f(m)+f(m-1), f(m-1) ) = gcd( f(m),f(m-1) ) = 1

    结论2：如果f(n+1)/f(n) = f(n'+1)/f(n')，那么n=n'
    证明：还是数学归纳法。当max(n,n')=0时结论显然成立，因为此时n=n'=0。
    假如对于所有小于n的数结论都成立。由于f(2k-1)<f(2k)，那么要想f(n)/f(n-1) = f(n')/f(n'-1)，n与n'的奇偶性必须相同，于是可以推出f(m)/f(m-1) = f(m')/f(m'-1)，根据归纳我们有m=m'，这就告诉我们n=n'。

    结论3：对于任何一个有理数r，总存在一个正整数n使得r=f(n)/f(n-1)。
    证明：把r写成两个互素的数p和q的比。我们对max(p,q)施归纳。
    显然，当p=q=1时结论成立，此时n=1。
    不妨设p<q，那么定义r'为p/(q-p)。根据归纳假设，总存在一个数m满足r'=f(m)/f(m-1)。于是r=f(2m+1)/f(2m)。当p>q时同理可证明。

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

Tupper自我指涉公式：图象里竟然包含式子本身

/ 32 条评论

    你认为，一个函数图象里是否有可能包含这个函数本身的“图象”？难以置信的是，还真有人构造了这样一个东西。2001年，Jeff Tupper发表的一篇论文里提到了这样一个有趣的不等式：
  
    在0 <= x <= 105，n <= y <= n + 16的范围内，这个不等式对应的图象是这个样子：
  

其中，n = 96093937991895888497167296212785275471500433966012930665150551927170280239526642
46896428421743507181212671537827706233559932372808741443078913259639413377234878
57735749823926629715517173716995165232890538221612403238855866184013235585136048
82869333790249145422928866708109618449609170518345406782773155170540538162738096
76025656250169814820834187831638491155902256100036523513703438744618483787372381
98224849863465033159410054974700593138339226497249461751545728366702369745461014
655997933798537483143786841806593422227898388722980000748404719

    你会觉得这个很神奇吗？你也许会想，天哪，这个是怎么构造出来的啊！但仔细思考之后，你会发现这个一点都不神奇。事实上明白了道理之后你可以构造出无数个这样的式子来。现在给你一些时间让你思考一下，你能否看出其中的奥秘？

    就像魔术揭秘一样，说穿了真相后上面的这些东西就一点意思都没有了。在这个式子里，涉及到x和y的变量时都加上了取整符号，因此整个图象都是一格一格的。这样，不等式右边的式子就简化为y div 17 * 2^(-17x – y mod 17) mod 2，其中x和y都为整数。接着观察，一个数乘以2的负k次方相当于对应的二进制数右移k位，那么x * 2^(-k) mod 2实质上就是二进制数x右起第k位上的数字。对于某个自然数t，当17t <= y < 17(t+1)时，指数-17x – y mod 17恰好对应所有的负整数，于是位于y=17t和y=17t+16之间的图象的每个像素和t的二进制中的每一位数字一一对应。随着t值的增加，图形的像素会一点一点地变化。当纵坐标足够大时，必然会出现一段高度为17的图象，图象的样子和不等式本身的样子相同。当然，你也可以在里面“找到”任何你想要的图象，只需要把图象还原为二进制数并转换为十进制即可。你甚至可以告诉你的MM，说你发现了一个函数，函数在某个位置的图象正好是某某某我爱你的字样。

Matrix67原创
转贴请注明出处
最近发现了一些很不厚道的人，希望大家注意哦！

神奇的分形艺术（四）：Julia集和Mandelbrot集

/ 44 条评论

    考虑函数f(z)=z^2-0.75。固定z0的值后，我们可以通过不断地迭代算出一系列的z值：z1=f(z0), z2=f(z1), z3=f(z2), …。比如，当z0 = 1时，我们可以依次迭代出：

z1 = f(1.0) = 1.0^2 – 0.75 = 0.25
z2 = f(0.25) = 0.25^2 – 0.75 = -0.6875
z3 = f(-0.6875) = (-0.6875)^2 – 0.75 = -0.2773
z4 = f(-0.2773) = (-0.2773)^2 – 0.75 = -0.6731
z5 = f(-0.6731) = (-0.6731)^2 – 0.75 = -0.2970
…

    可以看出，z值始终在某一范围内，并将最终收敛到某一个值上。
    但当z0=2时，情况就不一样了。几次迭代后我们将立即发现z值最终会趋于无穷大：

z1 = f(2.0) = (2.0)^2 – 0.75 = 3.25
z2 = f(3.25) = (3.25)^2 – 0.75 = 9.8125
z3 = f(9.8125) = (9.8125)^2 – 0.75 = 95.535
z4 = f(95.535) = (95.535)^2 – 0.75 = 9126.2
z5 = f(9126.2) = (9126.2)^2 – 0.75 = 83287819.2
…

    经过计算，我们可以得到如下结论：当z0属于[-1.5, 1.5]时，z值始终不会超出某个范围；而当z0小于-1.5或大于1.5后，z值最终将趋于无穷。
    现在，我们把这个函数扩展到整个复数范围。对于复数z0=x+iy，取不同的x值和y值，函数迭代的结果不一样：对于有些z0，函数值约束在某一范围内；而对于另一些z0，函数值则发散到无穷。由于复数对应平面上的点，因此我们可以用一个平面图形来表示，对于哪些z0函数值最终趋于无穷，对于哪些z0函数值最终不会趋于无穷。我们用深灰色表示不会使函数值趋于无穷的z0；对于其它的z0，我们用不同的颜色来区别不同的发散速度。由于当某个时候|z|>2时，函数值一定发散，因此这里定义发散速度为：使|z|大于2的迭代次数越少，则发散速度越快。这个图形可以编程画出。和上次一样，我用Pascal语言，因为我不会C的图形操作。某个MM要过生日了，我把这个自己编程画的图片送给她^_^

{$ASSERTIONS+}

uses graph;

type
   complex=record
      re:real;
      im:real;
   end;

operator * (a:complex; b:complex) c:complex;
begin
   c.re := a.re*b.re - a.im*b.im;
   c.im := a.im*b.re + a.re*b.im;
end;

operator + (a:complex; b:complex) c:complex;
begin
   c.re := a.re + b.re;
   c.im := a.im + b.im;
end;

var
   z,c:complex;
   gd,gm,i,j,k:integer;
begin
   gd:=D8bit;
   gm:=m640x480;
   InitGraph(gd,gm,'');
   Assert(graphResult=grOk);

   c.re:=-0.75;
   c.im:=0;
   for i:=-300 to 300 do
   for j:=-200 to 200 do
   begin
      z.re:=i/200;
      z.im:=j/200;
      for k:=0 to 200 do
      begin
         if sqrt(z.re*z.re + z.im*z.im) >2 then break
         else z:=(z*z)+c;
      end;
      PutPixel(i+300,j+200,k)
   end;

   readln;
   CloseGraph;
end.

    代码在Windows XP SP2，FPC 2.0下通过编译，麻烦大家帮忙报告一下程序运行是否正常（上次有人告诉我说我写的绘图程序不能编译）。在我这里，程序运行的结果如下：

    这个美丽的分形图形表现的就是f(z)=z^2-0.75时的Julia集。考虑复数函数f(z)=z^2+c，不同的复数c对应着不同的Julia集。也就是说，每取一个不同的c你都能得到一个不同的Julia集分形图形，并且令人吃惊的是每一个分形图形都是那么美丽。下面的六幅图片是取不同的c值得到的分形图形。你可能不相信这样一个简单的构造法则可以生成这么美丽的图形，这没什么，你可以改变上面程序代码中c变量的值来亲自验证。

c = 0.45, -0.1428
  

c = 0.285, 0.01
  

c = 0.285, 0
  

c = -0.8, 0.156
  

c = -0.835, -0.2321
  

c = -0.70176, -0.3842
  

    类似地，我们固定z0=0，那么对于不同的复数c，函数的迭代结果也不同。由于复数c对应平面上的点，因此我们可以用一个平面图形来表示，对于某个复数c，函数f(z)=z^2+c从z0=0开始迭代是否会发散到无穷。我们同样用不同颜色来表示不同的发散速度，最后得出的就是Mandelbrot集分形图形：
    

    前面说过，分形图形是可以无限递归下去的，它的复杂度不随尺度减小而消失。Mandelbrot集的神奇之处就在于，你可以对这个分形图形不断放大，不同的尺度下你所看到的景象可能完全不同。放大到一定时候，你可以看到更小规模的Mandelbrot集，这证明Mandelbrot集是自相似的。下面的15幅图演示了Mandelbrot集的一个放大过程，你可以在这个过程中看到不同样式的分形图形。

网上可以找到很多小程序实现Mandelbrot集的放大过程。把上面给出的代码改一改，你也可以写出一个这样的程序来。

Update：2011 年 8 月 31 日，我对这个话题做了更进一步的讨论 http://www.matrix67.com/blog/archives/4570

十个有趣的英文文字游戏（上）

/ 13 条评论

Crossword
    Crossword我就不用多废话了，这应该是最流行的英文文字游戏。和大多数人想象的不同，构造一个Crossword谜题非常难。真正的Crossword谜题里的空格比你想象的更多，整个填字区域要做到中心对称，而且通常每个Crossword需要有一个特定的主题。去年有一个记录片叫Wordplay，很不错（我给它打了8分）。记录片里介绍了很多和Crossword有关的文化，包括出谜人、解谜人、俱乐部、比赛等很多内容。
    下面是一个以数学为主题的Crossword，大家没事可以做做。答案在本文最后面。

  
Across

1. Cut corners
5. The __ plane, or S(7)
9. Hydrogen
14. Large reptile
16. Column
17. Gives the slope of a tangent to a curve
19. Book by Zienkiewicz and Taylor, abbr.
20. Divide
21. Sin reciprocal
22. The playing field, in nim
25. "I saw Blanusa's paper __ after it appeared." — Tutte
26. pronoun
27. Hydroxyl group bonded to a doubly-bonded carbon atom
28. (e^z – e^(-z))/2
29. Bar
30. The sphinx is a __-tile
31. __-digit
32. Fit
35. A type of map projection
38. The ___ hypothesis is independent of Zermelo-Fraenkel-Choice
39. Floor coverings, frequently symmetrical
40. Graph theorist Hai Peng
41. Angle
42. Branch or Dedekind
43. Math __ (where to find a prof)
44. 2, 4, 6, 30, 32, 34, 36, 40, 42 …
46. Art __
47. Computer Algebra: Systems and Algorithms for Algebraic Computation editor
48. MAA president Graham
49. Rule
50. As opposed to LHS
51. The gamma function has these at negative integers
57. Puzzle creator van Deventer
58. Tries
59. Paris river
60. Philosopher Descartes
61. Charts

Down

1. Saturnine
2. Director of Ulugh Beg's observatory
3. 3-30 KHz, as heard by "whistler" receivers
4. An OOPL or tower.
5. Plow
6. Supped
7. Proof of existance, without a specific example
8. Hermite orthogonal polynomial
9. Stat
10. GTE rival
11. Quasi-conformal enemy of Edmund Landau
12. (23/9)^5 and 109, for example
13. Ergo
15. Pilot stunt: "pulling ___"
18. Faraday theory, later proven by Arrhenius
22. Peace prize winner Shimon
23. J of ___ and Appl
24. The Inverse Variational Problem in Classical Mechanics author
25. The "sampling" function
26. A searching method for Ramsey numbers
28. "What I give form to in daylight is only one per cent of what I have __ in darkness." — Escher
29. boxers
31. High school math
32. Add-with-carry, inverse congruential, rule 30, dice, etc.
33. Chaos and Fractals author Dietmar
34. Graphica author Michael
36. ICOSAHOM editor Andrew
37. Focus, for example
42. Triangle part studied by Kimberling
43. In anatomy, away from the origin
44. More than 1500 math papers have his name
45. Where Set theory: On the structure of the real line was written
46. Actor Knotts
47. Number theorist Peter
49. Sported
50. Theorem
52. Cylinder
53. O'__ group (order 460815505920)
54. Skater Midori
55. Mind plotter
56. It's better than angle-angle-side

Anagram
    Anagram是指调整一个单词或短语的字母顺序后组成另外一个单词或短语，通常前后两者的关系有点讽刺意味。比如，《达芬奇密码》上就有一个：
    O, Draconian devil! Oh, lame saint! = Leonardo da Vinci, The Mona Lisa

    经典的Anagram非常有意思。看下面几个Anagram：
    Listen = Silent
    Dormitory = Dirty Room
    Desperation = A Rope Ends It
    Mother-in-law = Woman Hitler
    A telephone girl = Repeating "Hello"
    The country side = No City Dust Here

    一些Anagram有可能很长。比如这一个：
    To be or not to be: that is the question, whether tis nobler in the mind to suffer the slings and arrows of outrageous fortune.
    = In one of the Bard's best-thought-of tragedies, our insistent hero, Hamlet, queries on two fronts about how life turns rotten.

    另一个有趣的Anagram是这样：
    Eleven plus two = Twelve plus one

Pangram
    Pangram是指这样一种句子，它虽然不长，但包含了所有26个英文字母。Pangram常用于打字机测试和字体演示。大家最熟悉不过的是Windows字体演示时所用的Pangram：
    The quick brown fox jumps over the lazy dog.

    而Macintosh的字体演示则是使用的这个Pangram：
    Cozy lummox gives smart squid who asks for job pen.

    另一个比较常见的Pangram如下：
    Pack my box with five dozen liquor jugs.

    当然，有人肯定想问，有没有最短的Pangram？当然有。有的Pangram只有26个字母（每个字母恰好用一次），这样的Pangram叫做Perfect pangram。比如下面这一个：
    New job: fix Mr. Gluck's hazy TV, PDQ!

Autogram
    Autogram又叫做Self-enumerating Sentence，是指一句话的内容描述的正是这句话本身。下面是一些常见的Autogram：
    This sentence contains five words.
    This sentence contains thirty-six letters.
    There are fourteen vowels in this sentence.

    1982年，Scientific American月刊上刊登出一个Autogram杰作：

Only the fool would take trouble to verify that his sentence was composed of ten a's, three b's, four c's, four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens and, last but not least, a single !

    另一个类似的Autogram如下：

This autogram contains five a's, one b, two c's, two d's, thirty-one e's, five f's, five g's, eight h's, twelve i's, one j, one k, two l's, two m's, eighteen n's, sixteen o's, one p, one q, six r's, twenty-seven s's, twenty-one t's, three u's, seven v's, eight w's, three x's, four y's, and one z.

Palindrome
    Palindrome是指这样一种单词或句子，从左往右和从右往左读都是一样的。例如，单词eye, noon, level, racecar, redivider都是Palindrome。一些比较长的句子也可能是Palindrome，比如USACO上曾出现过这样一个Palindrome：
    Madam, I'm Adam.

    另一些有趣的Palindrome如下：
    Never odd or even.
    Was it a cat I saw?
    Step on no pets!
    Dammit, I'm mad!
    Rise to vote, sir.
&nbs
p;   God lived as a devil dog.
    A man, a plan, a canal — Panama!

    1814年，当拿破仑被流放到Elba岛时，拿破仑曾说过：
    Able was I ere I saw Elba.

    这里有一份号称世上最长的Palindrome。

Alphamagic Square
    1986年，一个叫Lee Sallows的电子工程师发现了这样一个3阶幻方：
5       22      18
28      15      2
12      8       25

    初看之下这个幻方似乎没有什么特别之处。然而，把它转换成文字后：
five            twenty-two      eighteen
twenty-eight    fifteen         two
twelve          eight           twenty-five

    再数一下每个单词的字母个数，我们可以得到一个新的幻方，它恰好由3到11这9个数字组成：
4       9       8
11      7       3
6       5       10

Matrix67收集整理
转贴请注明出处

      

神奇的分形艺术（三）：Sierpinski三角形

/ 36 条评论

    在所有的分形图形中，Sierpinski三角形可能是大家最熟悉的了，因为它在OI题目中经常出现，OJ上的题目和省选题目中都有它的身影。这篇文章将简单介绍Sierpinski三角形的几个惊人性质。如果你以前就对Sierpinski三角形有一些了解，这篇文章带给你的震撼将更大，因为你会发现Sierpinski三角形竟然还有这些用途。

Sierpinski三角形的构造
      
    和之前介绍的两种图形一样，Sierpinski三角形也是一种分形图形，它是递归地构造的。最常见的构造方法如上图所示：把一个三角形分成四等份，挖掉中间那一份，然后继续对另外三个三角形进行这样的操作，并且无限地递归下去。每一次迭代后整个图形的面积都会减小到原来的3/4，因此最终得到的图形面积显然为0。这也就是说，Sierpinski三角形其实是一条曲线，它的Hausdorff维度介于1和2之间。

    Sierpinski三角形的另一种构造方法如下图所示。把正方形分成四等份，去掉右下角的那一份，并且对另外三个正方形递归地操作下去。挖个几次后把脑袋一歪，你就可以看到一个等腰直角的Sierpinski三角形。

      

    Sierpinski三角形有一个神奇的性质：如果某一个位置上有点（没被挖去），那么它与原三角形顶点的连线上的中点处也有点。这给出另一个诡异的Sierpinski三角形构造方法：给出三角形的三个顶点，然后从其中一个顶点出发，每次随机向任意一个顶点移动1/2的距离（走到与那个顶点的连线的中点上），并在该位置作一个标记；无限次操作后所有的标记就组成了Sierpinski三角形。下面的程序演示了这一过程，程序在fpc 2.0下通过编译。对不起用C语言的兄弟了，我不会C语言的图形操作。
{$ASSERTIONS+}

uses graph,crt;

const
   x1=320;  y1=20;
   x2=90;   y2=420;
   x3=550;  y3=420;
   density=2500;
   timestep=10;

var
   gd,gm,i,r:integer;
   x,y:real;

begin
   gd:=D8bit;
   gm:=m640x480;
   InitGraph(gd,gm,'');
   Assert(graphResult=grOk);

   x:=x1;
   y:=y1;
   for i:=1 to density do
   begin
      r:=random(3);
      if r=0 then
      begin
         x:=(x+x1)/2;
         y:=(y+y1)/2;
      end
      else if r=1 then
      begin
         x:=(x+x2)/2;
         y:=(y+y2)/2;
      end
      else begin
         x:=(x+x3)/2;
         y:=(y+y3)/2;
      end;
      PutPixel(round(x),round(y),white);
      Delay(timestep);
   end;
   CloseGraph;
end.

Sierpinski三角形与杨辉三角
    第一次发现Sierpinski三角形与杨辉三角的关系时，你会发现这玩意儿不是一般的牛。写出8行或者16行的杨辉三角，然后把杨辉三角中的奇数和偶数用不同的颜色区别开来，你会发现杨辉三角模2与Sierpinski三角形是等价的。也就是说，二项式系数（组合数）的奇偶性竟然可以表现为一个分形图形！在感到诧异的同时，冷静下来仔细想想，你会发现这并不难理解。
      
    我们下面说明，如何通过杨辉三角奇偶表的前四行推出后四行来。可以看到杨辉三角的前四行是一个二阶的Sierpinski三角形，它的第四行全是奇数。由于奇数加奇数等于偶数，那么第五行中除了首尾两项为1外其余项都是偶数。而偶数加偶数还是偶数，因此中间那一排连续的偶数不断地两两相加必然得到一个全是偶数项的“倒三角”。同时，第五行首尾的两个1将分别产生两个和杨辉三角前四行一样的二阶Sierpinski三角形。这正好组成了一个三阶的Sierpinski三角形。显然它的最末行仍然均为奇数，那么对于更大规模的杨辉三角，结论将继续成立。

Sierpinski三角形与Hanoi塔
    有没有想过，把Hanoi塔的所有状态画出来，可以转移的状态间连一条线，最后得到的是一个什么样的图形？二阶Hanoi塔反正也只有9个节点，你可以自己试着画一下。不断调整节点的位置后，得到的图形大概就像这个样子：
      
    如果把三阶的Hanoi塔表示成无向图的话，得到的结果就是三阶的Sierpinski三角形。下面的这张图说明了这一点。把二阶Hanoi塔对应的无向图复制两份放在下面，然后在不同的柱子上为每个子图的每个状态添加一个更大的盘子。新的图中原来可以互相转移的状态现在仍然可以转移，同时还出现了三个新的转移关系将三个子图连接在了一起。重新调整一下各个节点的位置，我们可以得到一个三阶的Sierpinski三角形。
  
    显然，对于更大规模的Hanoi塔问题，结论仍然成立。

Sierpinski三角形与位运算
    编程画出Sierpinski三角形比想象中的更简单。下面的两个代码（实质相同，仅语言不同）可以打印出一个Sierpinski三角形来。
const
   n=1 shl 5-1;
var
   i,j:integer;
begin
   for i:=0 to n do
   begin
      for j:=0 to n do
         if i and j = j then write('#')
         else write(' ');
      writeln;
   end;
   readln;
end.
#include <stdio.h>
int main()
{
    const int n=(1<<5)-1;
    int i,j;
    for (i=0; i<=n; i++)
    {
        for (j=0; j<=n; j++)
           printf( (i&j)==j ? "#" : " ");
        printf("n");
    }    
    getchar();
 &n
bsp;  return 0;
}
    上面两个程序是一样的。程序将输出：
#                              
##                              
# #                            
####                            
#   #                          
##  ##                          
# # # #                        
########                        
#       #                      
##      ##                      
# #     # #                    
####    ####                    
#   #   #   #                  
##  ##  ##  ##                  
# # # # # # # #                
################                
#               #              
##              ##              
# #             # #            
####            ####            
#   #           #   #          
##  ##          ##  ##          
# # # #         # # # #        
########        ########        
#       #       #       #      
##      ##      ##      ##      
# #     # #     # #     # #    
####    ####    ####    ####    
#   #   #   #   #   #   #   #  
##  ##  ##  ##  ##  ##  ##  ##  
# # # # # # # # # # # # # # # #
################################

    这个程序告诉我们：在第i行第j列上打一个点当且仅当i and j=j，这样最后得到的图形就是一个Sierpinski三角形。这是为什么呢？其实原因很简单。把i和j写成二进制（添加前导0使它们位数相同），由于j不能大于i，因此只有下面三种情况：
    情况一：
    i = 1?????
    j = 1?????
    问号部分i大于等于j
    i的问号部分记作i'，j的问号部分记作j'。此时i and j=j当且仅当i' and j'=j'

    情况二：
    i = 1?????
    j = 0?????
    问号部分i大于等于j
    i的问号部分记作i'，j的问号部分记作j'。此时i and j=j当且仅当i' and j'=j'

    情况三：
    i = 1?????
    j = 0?????
    问号部分i小于j
    此时i and j永远不可能等于j。i' < j'意味着i'和j'中首次出现数字不同的那一位上前者为0，后者为1，那么i和j做and运算时这一位的结果是0，与j不等。

    注意到，去掉一个二进制数最高位上的“1”，相当于从这个数中减去不超过它的最大的2的幂。观察每一种情况中i,j和i',j'的实际位置，不难发现这三种情况递归地定义出了整个Sierpinski三角形。
    嘿！发现没有，我通过Sierpinski三角形证明了这个结论：组合数C(N,K)为奇数当且仅当N and K=K。这篇文章很早之前就计划在写了，前几天有人问到这个东西，今天顺便也写进来。
    另外，把i and j=j 换成i or j=n也可以打印出Sierpinski三角形来。i and j=j表示j的二进制中有1的位置上i也有个1，那么此时i or (not j)结果一定全为1（相当于程序中的常量n），因此打印出来的结果与原来的输出正好左右镜像。

Matrix67原创
转贴请注明出处

网友Voldemort在12楼和13楼很辛苦地帖了一个杨辉三角模2问题的扩展，大家可以看看