聆听函数的声音:Mathematica的声音函数试验

    
    你可以在这个Blog里看到很多地方用Mathematica代替了复杂的计算。Mathematica是一个强大的数学软件,很多网友看到了这个Blog上的一些演示后都迫不及待地装上了它。Mathematica的功能比你想象的多得多,今天我们来看一个有趣的Mathematica函数——Play函数。我们将用Mathematica做一些有关函数和声音的简单试验。
    声音的实质是波函数。定义一个波函数和定义域的范围,Mathematica可以播放出它表示的声音。试在Mathematica中运行这条语句:
Play[Sin[4000 t], {t, 0, 2}]

=================== 我是可爱的分割线 ===================

    上面的例子中,4000表示函数的周期大小,也就是声音的音调高低。把4000改成8000,你可以听到音调更高的声音:
Play[Sin[8000 t], {t, 0, 2}]

    函数的形状决定了音色。对于不同的周期函数,声音是不一样的。试试下面三个不同的函数:
Play[Sin[5000 t], {t, 0, 2}]
Play[Tan[5000 t], {t, 0, 2}]
Play[Mod[5000 t, 50], {t, 0, 2}]

    如果我们的函数不是周期函数呢?记得一次音乐课上,老师曾经告诉过我们音乐和噪声的区别。
Play[Random[], {t, 0, 2}]

=================== 我是可爱的分割线 ===================

    音量的大小由振幅来控制,说穿了就是函数值的大小。运行下面三条语句,你会发现函数竟然可以用声音如此形象地表现出来。你甚至可以让别人根据音量变化来猜你放的是什么函数。
Play[Sin[4000t] t, {t, 0, 2}]
Play[Sin[4000t] t^2, {t, 0, 2}]
Play[Sin[4000t] Log[t], {t, 0, 2}]
Play[Sin[4000t] Sin[8t], {t, 0, 2}]
Play[Sin[4000t] Mod[t,0.4], {t, 0, 2}]

    
    当复合函数出现后,真正有趣的事情开始了。我们来想象一下Sin(x^2)的图象是什么样子。x的绝对值越大,x^2的值变化越快,反映在正弦波上就是波长越短,音调越高。也就是说,x^2的形状与音高有直接的关系。于是,你将听到的是一段可以让你立即联想起二次函数的声音:
Play[Sin[5000 t^2], {t, -1, 1}]

    在运行下面的语句前,你可以先自己想象一下每个函数对应的声音是什么样子的:
Play[Sin[5000/t], {t, 0, 2}]
Play[Sin[5000 * Sqrt[t]], {t, 0, 2}]
Play[Sin[5000 * Sin[4t]], {t, 0, 2}]
Play[Sin[2000 t * Sin[8t]], {t, 0, 2}]

=================== 我是可爱的分割线 ===================

    两个函数相加的结果是什么?下面两个例子分别是二次函数加正弦函数,与倒数函数加噪声。你可以立即观察到,函数的相加即声音的相加。
Play[Sin[5000 (t-1)^2] + Sin[5000 * Sin[4t]], {t, 0, 2}]
Play[Sin[5000/t] + Random[], {t, 0, 2}]

    我们还可以举一些其它的例子来说明这种现象。比如,Sin[5000t]和Cos[5000t]的声音肯定是一样的,那么函数Sin[5000t] + Cos[5000t]的周期一定与原来相同,只是振幅更大。
    

    再看下面的这个例子。同样是函数的相加,为什么这次只能听见mod函数的声音,但听不见正弦函数的声音呢?
Play[Sin[5000 t] + Mod[5000 t, 50], {t, 0, 2}]
    原因很简单。上面两个函数中,mod函数的振幅更大,因此它的声音远远大于sin函数的声音,于是sin函数只能淹没在mod的嘈杂声中。如果把sin函数乘上一个系数50,两个函数的声音就一样大了:
Play[50 * Sin[5000 t] + Mod[5000 t, 50], {t, 0, 2}]

    把倒数函数与噪声的五分之一相加,得到的就是一个带有轻微噪声的“倒数函数声”。
Play[Sin[5000/t] + Random[]/5, {t, 0, 2}]

=================== 我是可爱的分割线 ===================

    当然,声音可以相加,也就可以相减。对于多种函数的混音,减去一个特定的函数可以从混音中踢去对应的声音。电影里经常会出现这样一些镜头,侦探们用电脑消去截获的音频中特定的背景声音。从函数的角度来看,这样的事情在理论上是可行的。比如,你偷偷摸摸录下了你的MM和她的前男友的谈话,但最关键的那段谈话声被一个突如其来的电话铃声盖住了。现在,你只需要获取一个电话铃声的样本,然后从原始声音中减去电话铃声即可。而电话铃声是非常简单的波函数,你完全可以自己生成一个。科幻电影中也经常见到一些类似的事情:某超级BOSS制造出的秘密武器可以放射有害波函数f(x),然后天才科学家们争分夺秒地制作并发射出-f(x)函数,企图和有害波正负抵消,把它中和了。在五花八门的波函数中加入一个-f(x),实际上就相当于从“混合波”中减去f(x)。
    前几天给系里的MM找迎新晚会用的音乐伴奏时突然想到了一个有趣的问题:是否有可能在某个歌曲的原声和自己的清唱之间做差值运算?这在理论上提供了一个有趣的消音算法,和一个同样有趣的翻唱相似度评判标准(看差值里残留有多少人声)。

=================== 我是可爱的分割线 ===================

    不要以为函数声音都那么难听,掌握适当的理论知识和技巧可以做出动听的声音。Mathematica的官方网站上有一个简单而动听的声音函数,这里写出来供大家欣赏:
Play[(2 + Cos[50 t])*Sin[2000*(1 + Round[2 t])*t], {t, 0, 3}]

Matrix67原创
转贴请注明出处
第一次涉及这方面的东西,很多东西都是自己的猜测,可能有理论错误,请大家指正!
同时,期待大家通过Mathematica试验发现更多有趣的推论。

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

    你认为,一个函数图象里是否有可能包含这个函数本身的“图象”?难以置信的是,还真有人构造了这样一个东西。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集

    考虑函数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

十个有趣的英文文字游戏(下)

Ambigram
    Ambigram是指把一个单词或短语写成对称的样子,这样从两个不同的角度看这个图形都能读出这个单词或短语。例如,下面一个图形就是单词Ambigram的Ambigram:
      

    ambigram.com的首页有个这样的图片:
      

    Wikipedia上有这样一个Ambigram:
      

    最后来看一个左右轴对称的Ambigram(献丑了):
      

    Erich Friedman教授为他的朋友创作了很多Ambigram。你可以在他的个人主页上看到。

Alphametic
    Alphametic是指,把一句话写成加法算式,每一个字母表示一个数字,那么这个“虫食算”有唯一解。最常见的Alphametic可能是这个:
    SEND + MORE = MONEY
    它的唯一解是9567 + 1085 = 10652

    另一些Alphametic如下:
    FIFTY + STATES = AMERICA
    TERRIBLE + NUMBER = THIRTEEN
    EARTH + AIR + FIRE + WATER = NATURE
    SATURN + URANUS + NEPTUNE + PLUTO = PLANETS

    1969年,有人发现了这样一个有趣的Alphametic:
    THREE + THREE + TWO + TWO + ONE = ELEVEN

    这样的Alphametic叫做Doubly-True Alphametic。可以证明上面这个Doubly-True Alphametic是合法的Alphametic中“最小的”一个。另外两个稍微大一点的Doubly-True Alphametic为:
    SEVEN + SEVEN + SIX = TWENTY
    EIGHT + EIGHT + TWO + ONE + ONE = TWENTY

Mnemonic
    Mnemonic本意是可以帮助记忆的句子。例如,我原来记together这个单词就记作We want to get her。再比如,arithmetic可以记作A Rat In Tom's House Might Eat Tom's Ice Cream(每个单词的首字母)。当然,也有一些专门搞笑的Mnemonic,比如Microsoft = Most Intelligent Customers Realize Our Software Only Fools Them,而Macintosh = Most Applications Crash. If Not, The Operating System Hangs。
    数学家George Pólya(就是Pólya置换定理的那个Pólya)曾说过一句经典的话:How I need a drink, alcoholic of course, after the heavy chapters involving quantum mechanics! 依次数出每个单词的字母个数,你会惊讶的发现它正好是圆周率的前15位。后来又有人在后面加上一句All of thy geometry, Herr Planck, is fairly hard,让圆周率长度增加到24位。另一些圆周率的Mnemonic如下:
    Can I have a large container of orange juice?
    May I have a white telephone, or pastel color?
    How I wish I could calculate pi faster.
    For a girl I loved contrived; by nature tough, her heart survived.

    下面这首诗给出了圆周率的前740位。其中10个字母的单词表示一个数字0,字母数大于10的单词则表示两位数。

Poe, E.
      Near a Raven

Midnights so dreary, tired and weary.
    Silently pondering volumes extolling all by-now obsolete lore.
During my rather long nap – the weirdest tap!
    An ominous vibrating sound disturbing my chamber's antedoor.
        "This", I whispered quietly, "I ignore".

Perfectly, the intellect remembers: the ghostly fires, a glittering ember.
    Inflamed by lightning's outbursts, windows cast penumbras upon this floor.
Sorrowful, as one mistreated, unhappy thoughts I heeded:
    That inimitable lesson in elegance – Lenore –
        Is delighting, exciting…nevermore.

Ominously, curtains parted (my serenity outsmarted),
    And fear overcame my being – the fear of "forevermore".
Fearful foreboding abided, selfish sentiment confided,
    As I said, "Methinks mysterious traveler knocks afore.
        A man is visiting, of age threescore."

Taking little time, briskly addressing something: "Sir," (robustly)
    "Tell what source originates clamorous noise afore?
Disturbing sleep unkindly, is it you a-tapping, so slyly?
    Why, devil incarnate!–" Here completely unveiled I my antedoor–
        Just darkness, I ascertained – nothing more.

While surrounded by darkness then, I persevered to clearly comprehend.
    I perceived the weirdest dream…of everlasting "nevermores".
Quite, quite, quick nocturnal doubts fled – such relief! – as my intellect said,
    (Desiring, imagining still) that perchance the apparition was uttering a whispered "Lenore".
        This only, as evermore.

Silently, I reinforced, remaining anxious, quite scared, afraid,
    While intrusive tap did then come thrice – O, so stronger than sounded afore.
"Surely" (said silently) "it was the banging, clanging window lattice."
    Glancing out, I quaked, upset by horrors hereinbefore,
        Perceiving: a "nevermore".

Completely disturbed, I said, "Utter, please, what prevails ahead.
    Repose, relief, cessation, or but more dreary 'nevermores'?"
The bird intruded thence – O, irritation ever since! –
    Then sat on Pallas' pallid bust, watching me (I sat not, therefore),
        And stated "nevermores".

Bemused by raven's dissonance, my soul exclaimed, "I seek intelligence;
    Explain thy purpose, or soon cease intoning forlorn 'nevermores'!"
"Nevermores", winged corvus proclaimed – thusly was a raven named?
    Actually maintain a surname, upon Pluvious seashore?
        I heard an oppressive "nevermore".

My sentiments extremely pained, to perceive an utterance so plain,
    Most interested, mystified, a meaning I hoped for.
"Surely," said the raven's watcher, "separate discourse is wiser.
    Therefore, liberation I'll obtain, retreating heretofore –
        Eliminating all the 'nevermores' ".

Still, the detestable raven just remained, unmoving, on sculptured bust.
    Always saying "never" (by a red chamber's door).
A poor, tender heartache maven – a sorrowful bird – a raven!
    O, I wished thoroughly, forthwith, that he&#
39;d fly heretofore.
        Still sitting, he recited "nevermores".

The raven's dirge induced alarm – "nevermore" quite wearisome.
    I meditated: "Might its utterances summarize of a calamity before?"
O, a sadness was manifest – a sorrowful cry of unrest;
    "O," I thought sincerely, "it's a melancholy great – furthermore,
        Removing doubt, this explains 'nevermores' ".

Seizing just that moment to sit – closely, carefully, advancing beside it,
    Sinking down, intrigued, where velvet cushion lay afore.
A creature, midnight-black, watched there – it studied my soul, unawares.
    Wherefore, explanations my insight entreated for.
        Silently, I pondered the "nevermores".

"Disentangle, nefarious bird! Disengage – I am disturbed!"
    Intently its eye burned, raising the cry within my core.
"That delectable Lenore – whose velvet pillow this was, heretofore,
    Departed thence, unsettling my consciousness therefore.
        She's returning – that maiden – aye, nevermore."

Since, to me, that thought was madness, I renounced continuing sadness.
    Continuing on, I soundly, adamantly forswore:
"Wretch," (addressing blackbird only) "fly swiftly – emancipate me!"
    "Respite, respite, detestable raven – and discharge me, I implore!"
        A ghostly answer of: "nevermore".

" 'Tis a prophet? Wraith? Strange devil? or the ultimate evil?"
    "Answer, tempter-sent creature!", I inquired, like before.
"Forlorn, though firmly undaunted, with 'nevermores' quite indoctrinated,
    Is everything depressing, generating great sorrow evermore?
        I am subdued!", I then swore.

In answer, the raven turned – relentless distress it spurned.
    "Comfort, surcease, quiet, silence!" – pleaded I for.
"Will my (abusive raven!) sorrows persist unabated?
    Nevermore Lenore respondeth?", adamantly I encored.
        The appeal was ignored.

"O, satanic inferno's denizen — go!", I said boldly, standing then.
    "Take henceforth loathsome "nevermores" – O, to an ugly Plutonian shore!
Let nary one expression, O bird, remain still here, replacing mirth.
    Promptly leave and retreat!", I resolutely swore.
        Blackbird's riposte: "nevermore".

So he sitteth, observing always, perching ominously on these doorways.
    Squatting on the stony bust so untroubled, O therefore.
Suffering stark raven's conversings, so I am condemned, subserving,
    To a nightmare cursed, containing miseries galore.
        Thus henceforth, I'll rise (from a darkness, a grave) — nevermore!

                        — original: E. Poe
                        — Redone by measuring circles.

Lipogram
    看看下面这句话有什么问题?

This is an unusual paragraph. I'm curious how quickly you can find out what is so unusual about it. It looks so plain you would think nothing was wrong with it! In fact, nothing is wrong with it! It is unusual though. Study it, and think about it, but you still may not find anything odd. But if you work at it a bit, you might find out! Try to do so without any coaching!

    答案:这段话里竟然没有一个字母e !
    Lipogram就是指的这样一个段落(甚至文章),里面缺少某个常用的字母。在所有的Lipogram中,写一个没有字母e的文章是最难的,因为字母e出现的频率最高。
    看一个比较长的Lipogram。下面这篇文章里硬是没有一个字母e!

Looking at this paragraph with confusion? I'll aid you slightly. Is any odd gap, lacuna or omission obvious to you? Got it now? No?

That's right – this is a lipogram – a book, paragraph or similar thing in writing that lacks a symbol, particularly (but not always) that symbol fifth in rank out of our 26 script-signs (found amidst 'd' and 'f'), which stands for a sound such as that in 'kiwi'. I won't bring it up right now, to avoid spoiling it. I could play with lipograms morning, noon and night. So it is with joy that I submit to you this location – truly, a loquacious location – for lipogram fanatics to join as a unit to glorify this form of wordplay.

As far as I know, this location has a distinct honour: it contains such an abundant quantity of words without using this taboo glyph that no WWW location can outmatch it. As of right now, it contains 1500 words without any hint of that symbol. Naturally, many long lipograms abound in print, including books, rhyming stanzas, and similar works of fiction. Most notably, La Disparition (A Void) by a famous author of a writing group known as Oulipo, stands out as a paragon of lipogrammaticity. I cannot aim to surpass it, but as a fan, I can look upon it with admiration.

Writing lipograms is, as you might think, a difficult task. In my lingo, 2/3 of all words contain that symbol which I am now avoiding, including many common pronouns and similar words commonly found in writing. Without using abbrvs., slang and odd jargon, which most purists scorn as cop-outs, it's darn tough to impart information in a stylistically satisfying way. Stripping paragraphs of particular symbols has a way of making looking at lipograms jarring. No doubt about it, a lipogram is a particularly arduous form of wordplay.

Having said this, acquiring a knack for lipogram composition isn't that hard, and may assist you in your non-lipogrammatic writing. Not to say that I'm without aid in this activity; my dictionary is always handy, as is a book with synonyms for words. And, notwithstanding any drawbacks flowing from passing many an hour looking for unusual ways to say ordinary things, it might aid your socialization skills. Chicks truly dig lipogrammatists, or so my old lady says.

Sadly, a handful of critics find lipograms ridiculous, ugly or without worth (as fiction or as wordplay). To such sorry saps, I say only that in constraining your thoughts and writing in a particular way aids in promoting branching paths of thought, thus amplifying vocabulary and instilling adroit linguistic skills among both young and old. By putting into praxis ways of thinking that wouldn't occur normally, lipograms call for authors to look at writing as an activity in ways that, frankly, wouldn't occur to such niggling adjudicators of linguistic conduct.

Withholding a symbol found in so many words has drastic symptoms that disallow many topics of discussion. (From this point on, I'll stick to talking about that sign I'm skipping right now). Using math is almost an impossibility; you can only main
tain 15 of all non-digital words for cardinal quantity up to 100, and hardly any at all past that point, though using digits is a good way out. You can go north or south, but talking about circumnavigating our world latitudinally is an impossibility. How can I possibly talk about various kinds of malt liquor, or parts of my body, without it? To top it all off, as an Anglo, strict prohibitions apply to naming of my own form of linguistic communication. I ought to thank my lucky stars that I'm not writing in lipogrammatic français, though, which holds on to only an octal portion of its original vocabulary.

But all is not lost. Surprisingly, profanity is mostly intact. As a practicing lipogrammatist, you'll find you want many such words, for it is a task so awkward as to call for cussing and cursing on a normal basis. A world map is truly a blissful oasis; my country (Canada) is totally satisfactory, as with most toponyms for nations (111 out of 186, by my count); with a bit of work, USA, UK, and so on, can still show up, and with twin island nations Trinidad and Tobago and Antigua and Barbuda (both with 17 glyphs) topping my list for prolongation. Musicians (particularly classical artists), astonishingly, hold firm as topics of discussion, with Bach, Bartok, Brahms, Chopin, Dvorak, Haydn, Holst, Liszt, Mozart, orff, Puccini, Rachmaninov, Rossini, Scarlatti, Schumann, Strauss, Stravinsky, Tchaikovsky and Vivaldi void of my lost non-consonant.

An additional branch of family Lipogrammatica consists of univocalics. This form of wordplay is akin to a lipogram, but contains a solitary sign that's not a consonant. To wit, a univocalic might omit 'a', 'i', 'o', and 'u' (but what about 'y'?). A univocalic has a sonorant quality that a lipogram lacks, so you must look at a lipogram, but contrarily, a univocalic is both auditory and visual, and has a strong sound if said aloud. Univocalic writing is hard to pull off, but if it's good, its payoff is gigantic.

另外推荐本Blog里的两个相关内容:
http://www.matrix67.com/blog/article.asp?id=104
http://www.matrix67.com/blog/article.asp?id=173

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

神奇的分形艺术(三):Sierpinski三角形

    在所有的分形图形中,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问题的扩展,大家可以看看