十大另类程序语言(下)

5. TMMLPTEALPAITAFNFAL语言 http://p-nand-q.com/humor/programming_languages/tmmlpteal.html
    你没看错,上面这一排毫无意义的字母是一个语言的名称。它是The Multi-Million Language Project To End All Language Projects And Isn't That A Fine Name For A Language的缩写。TMMLPTEALPAITAFNFAL语言没有固定的语法规则,每一天都是不同的语法。例如,2000年10月13日你可以使用DIV但不能使用MOD;到了10月14日时你可以使用MOD了但DIV又不能用了。因此,你今天写的程序运行起来完全正常,但是到了明天就无法编译了。下面是一个TMMLPTEALPAITAFNFAL的Hello World程序,当然现在已经无法编译了。
    DECLARE CELL 100 AS READPOS
    DECLARE 10 AS NEWLINE
    WRITE CHAR NEWLINE
    COPY "Hello, World" TO CELL 0
    COPY 0 TO READPOS
    WHILE READPOS INDIRECT DO GOSUB 300
    WRITE CHAR NEWLINE
    RETURN
LINE 300: WRITE CHAR READPOS INDIRECT
    ADD 1 TO READPOS
    RETURN

4. l33t语言 http://web.archive.org/web/20050329085620/http://electrod.ifreepages.com/l33t.htm
    Leetspeak是国外网络上曾经流行的一种字母书写方式,就像这个样子。很多电影和美剧的名字也是Leetspeak,比如se7en、numb3rs、s1m0ne等等。l33t程序的代码故意仿照这种风格。它的代码中只有0到9这九个数字是有意义的,其它的字符都没用。因此,你可以先写好一篇文章,然后依次把里面出现的字母替换成你的l33t代码,让一段Leetspeak文字中隐藏一个小程序。下面就是一个Hello World示例程序:
   // "Hello World" by Stephen McGreal.
   // Note that the views expressed in this source code do not necessarily coincide with those of the author :o)
  
   Gr34t l33tN3$$?
   M3h...
   iT 41n't s0 7rIckY.
  
   l33t sP33k is U8er keWl 4nD eA5y wehn u 7hink 1t tHr0uGh.
   1f u w4nn4be UB3R-l33t u d3f1n1t3lY w4nt in 0n a b4d4sS h4xX0r1ng s1tE!!!;p
   w4r3Z c0ll3cT10n2 r 7eh l3Et3r!
  
   Qu4k3 cL4nS r 7eh bE5t tH1ng 1n teh 3nTIr3 w0rlD!!!
   g4m3s wh3r3 u g3t to 5h00t ppl r 70tAl1_y w1cK1d!!
   I'M teh fr4GM4stEr aN I'lL t0t41_1Ly wIpE teh phr34k1ng fL00r ***j3d1 5tYlE*** wItH y0uR h1dE!!!!L0L0L0L!
   t3lEphR4gG1nG l4m3rs wit mY m8tes r34lLy k1kK$ A$$
  
   l33t hAxX0r$ CrE4t3 u8er- k3wL 5tUff lIkE n34t pR0gR4mm1nG lAnguidGe$...
   s0m3tIm3$ teh l4nGu4gES l00k jUst l1k3 rE41_ 0neS 7o mAkE ppl Th1nk th3y'r3 ju$t n0rMal lEE7 5pEEk but th3y're 5ecRetLy c0dE!!!!
   n080DY unDer5tAnD$ l33t SpEaK 4p4rT fr0m j3d1!!!!!
   50mE kId 0n A me$$4gEb04rD m1ghT 8E a r0xX0r1nG hAxX0r wH0 w4nT2 t0 bR34k 5tuFf, 0r mAyb3 ju5t sh0w 7eh wAy5 l33t ppl cAn 8E m0re lIkE y0d4!!! hE i5 teh u8ER!!!!
   1t m1ght 8E 5omE v1rus 0r a Pl4ySt4tI0n ch34t c0dE.
   1t 3v3n MiTe jUs7 s4y "H3LL0 W0RLD!!!" u ju5t cAn'T gu3s5.
   tH3r3's n3v3r anY p0iNt l00KiNg sC3pT1c4l c0s th4t, be1_1Ev3 iT 0r n0t, 1s whAt th1s 1s!!!!!
  
   5uxX0r5!!!L0L0L0L0L!!!!!!!

3. Java2K语言 http://p-nand-q.com/humor/programming_languages/java2k.html
    Java2K是一种非确定性的语言,程序正常运行是有一定概率的。很多时候程序并不能按照你的意愿去运行,即使是系统函数也不会总是去做它该做的事。所有的函数都有两种不同的解释,程序运行时会随机选择一个作为实际调用的函数。
    几乎所有的系统函数返回正确结果都只有90%的可能性,因此程序运行的最终结果或多或少都和预期结果不同。写出正确率尽量高的Java2K程序是一个非常有趣的挑战。

2. Chef语言 http://www.dangermouse.net/esoteric/chef.html
    一个完整的Chef程序代码分为三个部分:程序名、变量声明和一系列栈操作。所有的操作都写成食谱的样子。例如,Put x into the mixing bowl就表示把变量x压入栈中,而Stir for 2 minutes则表示把栈顶元素向下移两格。下面的程序打印出前100个Fibonacci数。
Fibonacci Numbers with Caramel Sauce.

Ingredients.
100 g flour
250 g butter
1 egg

Method.
Sift the flour. Put flour into mixing bowl. Serve with caramel sauce. Stir for 2 minutes. Remove egg. Rub the flour until sifted. Stir for 2 minutes. Fold the butter into the mixing bowl. Pour contents of the mixing bowl into the baking dish.

Serves 1.

Caramel Sauce.

Ingredients.
1 cup white sugar
1 cup brown sugar
1 vanilla bean

Method.
Fold white sugar into mixing bowl. Put white sugar into mixing bowl. Fold brown sugar into mixing bowl. Clean mixing bowl. Put white sugar into mixing bowl. Remove vanilla bean. Fold white sugar into mixing bowl. Melt white sugar. Put vanilla bean into mixing bowl. Refrigerate. Heat white sugar until melted. Put white sugar into mixing bowl. Remove vanilla bean. Fold white sugar into mixing bowl. Caramelise white sugar. Put vanilla bean into mixing bowl. Refrigerate. Cook white sugar until caramelised. Put white sugar into mixing bowl. Serve with caramel sauce. Fold brown sugar into mixing bowl. Put white sugar into mixing bowl. Add vanilla bean. Serve with caramel sauce. Add brown sugar.

1. Shakespeare语言 http://shakespearelang.sourceforge.net/
    在所有的另类语言中,Shakespeare语言可能是最搞笑的了,并且难以置信的是它居然是SourceForge.net的一个项目。Shakespeare的代码完全模仿莎士比亚的戏剧。它也是一个基于栈的程序语言,程序中出场的每一个人物都代表一个栈。Shakespeare的代码自由度很高,因此同一个程序你可以写出完全不同的代码出来。Shakespeare的Hello World代码如下:
The Infamous Hello World Program.

Romeo, a young man with a remarkable patience.
Juliet, a likewise young woman of remarkable grace.
Ophelia, a remarkable woman much in dispute with Hamlet.
Hamlet, the flatterer of Andersen Insulting A/S.

                    Act I: Hamlet's insults and flattery.

                    Scene I: The insulting of Romeo.

[Enter Hamlet and Romeo]

Hamlet:
You lying stupid fatherless big smelly half-witted coward!
You are as stupid as the difference between a handsome rich brave
hero and thyself! Speak your mind!

You are as brave as the sum of your fat little stuffed misused dusty
old rotten codpiece and a beautiful fair warm peaceful sunny summer's
day. You are as healthy as the difference between the sum of the
sweetest reddest rose and my father and yourself! Speak your mind!

You are as cowardly as the sum of yourself and the difference
between a big mighty proud kingdom and a horse. Speak your mind.

Speak your mind!

[Exit Romeo]

                    Scene II:
The praising of Juliet.

[Enter Juliet]

Hamlet:
Thou art as sweet as the sum of the sum of Romeo and his horse and his
black cat! Speak thy mind!

[Exit Juliet]

                    Scene III: The praising of Ophelia.

[Enter Ophelia]

Hamlet:
Thou art as lovely as the product of a large rural town and my amazing
bottomless embroidered purse. Speak thy mind!

Thou art as loving as the product of the bluest clearest sweetest sky
and the sum of a squirrel and a white horse. Thou art as beautiful as
the difference between Juliet and thyself. Speak thy mind!

[Exeunt Ophelia and Hamlet]

                    Act II: Behind Hamlet's back.

                    Scene I: Romeo and Juliet's conversation.

[Enter Romeo and Juliet]

Romeo:
Speak your mind. You are as worried as the sum of yourself and the
difference between my small smooth hamster and my nose. Speak your
mind!

Juliet:
Speak YOUR mind! You are as bad as Hamlet! You are as small as the
difference between the square of the difference between my little pony
and your big hairy hound and the cube of your sorry little
codpiece. Speak your mind!

[Exit Romeo]

                    Scene II: Juliet and Ophelia's conversation.

[Enter Ophelia]

Juliet:
Thou art as good as the quotient between Romeo and the sum of a small
furry animal and a leech. Speak your mind!

Ophelia:
Thou art as disgusting as the quotient between Romeo and twice the
difference between a mistletoe and an oozing infected blister! Speak
your mind!

[Exeunt]

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

十大另类程序语言(上)

10. LOLCODE语言 http://lolcode.com/
    国外流行一种lolcat图片,经常出现在论坛的头像和签名图里。lolcat图片里有一只很乖的小动物(通常是小猫),旁边写几句很可爱的话(比如故意的语法错误、拼写错误、近似发音或者网络缩略语)。很多web 2.0的宕机页面就是一张lolcat图片。LOLCODE就是用这种可爱的猫猫语言来写程序。LOLCODE的代码通俗易懂,写起来非常可爱,小MM一定会喜欢。比如看看下面这段代码:
HAI
CAN HAS STDIO?
I HAS A VAR
GIMMEH VAR
IZ VAR BIGGER THAN 10?
    YARLY
        BTW this is true
        VISIBLE "BIG NUMBER!"
    NOWAI
        BTW this is false
        VISIBLE "LITTLE NUMBER!"
    KTHX
KTHXBYE

9. BrainFuck语言 http://www.muppetlabs.com/~breadbox/bf
    BrainFuck语言是最简单的程序语言之一,只有8个有效字符,每个字符都有一个特定的含义。这8个字符控制一个指针在线性表里进行移动、读写、循环等操作。所有其它的字符都当作注释处理。我的Blog里曾对BrainFuck有过专门的介绍
    我很喜欢这个语言,甚至下载了它的编译器,写出不少BrainFuck程序。例如,下面这段代码可以输出我的网站域名“matrix67.com”:
++++++++++[>+++++++++++<-]>-.
<+++[>----<-]>.<+++++[>++++<-]>-.--.
<+++[>---<-]>.<+++++[>+++<-]>.
>+++++[>+++++++++++<-]>-.+.<+++[>---<-]>.<<
<+++++[>----<-]>-.<+++[>++++<-]>.--.

    BrainFuck语言有很多扩展。用不同的单词来代替这8个符号可以得到更多好玩的程序语言,有一些语言竟是把BrainFuck程序编码成图片或音乐作为程序代码。

8. Malbolge语言 http://www.lscheffer.com/malbolge.shtml
    Malbolge是最早的一个以代码丑陋为目标而设计出的程序语言,你几乎不可能读懂Malbolge的代码。它共有8条指令,所有运算都基于3进制,控制程序流的唯一指令是无条件跳转。它的Hello World程序如下:
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@986543W10/.R,+O<

7. Whitespace语言 http://compsoc.dur.ac.uk/whitespace/
    很多语言在编译时都会自动忽略空格、换行和Tab,而Whitespace语言正好相反,这个语言的有效字符只有三个(就是前面提到的三个空白符号),其它字符一律当作注释处理。这个语言对于机密工作者尤其有用,你可以把一个完整的Whitespace程序插入到一篇普通的文章中,谁也不会知道这里面竟然隐藏了一个机密代码。Whitespace也可以防止别人打印出源代码盗走。Whitespace源码的扩展名为.ws,这里是一个Whitespace的Hello World程序。我的Blog里也曾经介绍过Whitespace

6. Befunge语言 http://quadium.net/funge/spec98.html
    Befunge的代码是二维的。它用 < > v ^ 这四个符号来控制一个指针在代码中移动,指针经过一个字符或数字则把它压入一个栈,四则运算符号的功能就是弹出栈顶两个元素进行计算后把结果压回去。用 _ 和 | 来表示有条件的方向选择:当栈顶元素为0时向右(上)走,否则向左(下)走。& 和 ~ 分别用于读入数字或字符并压入栈,句号和逗号分别表示将栈顶元素作为整数或字符输出。最后以一个@符号表示程序结束。Befunge代码的注释不需要任何符号标明,你可以把注释写在程序的任何地方,只要运行时指针不会经过它就行了。你甚至可以把注释写在程序正中间,然后写代码时绕开注释写成一圈。Befunge的Hello World程序如下:
                 v
>v"Hello world!"0<
,:
^_25*,@

    看一个复杂的例子。我找了一个算圆周率的Befunge程序,看起来非常壮观。
aa*          v                  +------------------------+
vp*9920p*9930<                  | Pi generator in Bef-97 |
>:09a*pa*3/1+19a*p09a*g:09b*v   |                        |
v_@# g*b90 p*b910        < p<   | 7/2/1997, Kevin Vigor  |
>19a*g:+1-29b*p19a*g::09v       +------------------------+
v*a90g*b90*g*b91: _v#p*9<
>g-#v_ 2a*+$  v  :$
    >1-aa*ga*+v  p
v1:/g*b92p*991:<  *
>9b*p29b*g*199*gv9
v*b92p*aa-1g*990-<9
>g2-29b*p099*g1-:0^
v -9p*b92:%ag*991  <
>#v_ 299*g1+299*p>       ^
  >09b*g:#v_$v
v93p*b90-1<
>9*g199*ga/+.v
     v:g*992 <p*9 92-<
    v_29b*g399*p ^
    >09b*g:#v_v      1
vp*b90-1    < $      g
>199*g9`#v_'9,v      *
         >'0, >' ,299^

    通常认为Befunge是第一个基于“二维控制流”的语言,后来衍生出的一大批类似的语言都是受的Befunge影响。例如PingPong语言就是把Befunge的四种箭头符号换成正反斜杠,控制指针移动方向90度旋转,起一个反弹的作用。

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

C语言速成手册(六):其它问题、后记

预处理指令
    以一个井号开头的行都叫做预处理指令。除了#include指令外,我们还经常用到#define指令。#define指令可以告诉编译器,编译时把代码中出现的特定标识当作什么来处理。例如,我们可以这样写:
#define NAME_OF_MY_POTENTIAL_GF "ZPR"
    这样,编译器会在编译前把代码中出现NAME_OF_MY_POTENTIAL_GF的地方全部替换成"ZPR"。这种替换是无条件的,但是有一个例外:当指定的标识属于某个字符串(被引号引起来)时替换不会发生。例如,下面两行代码会输出NAME_OF_MY_POTENTIAL_GF defined as: ZPR
printf("NAME_OF_MY_POTENTIAL_GF defined as: ");
printf(NAME_OF_MY_POTENTIAL_GF);

    其中,后面那个NAME_OF_MY_POTENTIAL_GF被自动替换为"ZPR"。如果哪一天ZPR不要我了,我就可以非常方便地让整个程序适用于另一个MM。

    C语言中通常会用#define代替const。例如,下面的代码假设了输入数据n<=2000。
#include <stdio.h>
#define MAX 2000

int main()
{
   int f[MAX][MAX];
   int i,j,n;
   scanf("%d",&n);
   for ( i=0; i<n; i++ )
   {
      for ( j=0; j<=i; j++ )
      {
          f[i][j] = j ? (f[i-1][j] + f[i-1][j-1]) % 10000 : 1;
          printf( "%5d" , f[i][j] );
      }
      printf("n");
   }

   return 0;
}

    下面的这些指令也是合法的:
#define begin {
#define end }
#define and &&
#define or ||

    #define定义的指令允许带参数。例如,下面的定义也是合法的:
#define sqr(x) x*x
    观察下面的这个程序:
#include <stdio.h>
#define begin {
#define end }
#define writeln(num) printf("%dn",num)
#define sqr(x) x*x

int main()
begin
   writeln(sqr(100));
   writeln(sqr(10+2));
end

    程序输出:
10000
32

    为什么第二个输出的数是32不是144?不要忘了sqr中的x不是一个变量,编译器仅仅是把x替换为10+2,因此sqr(10+2)的结果是10+2*10+2,当然是32咯。为了避免这种情况,这样写就没问题了:
#define sqr(x) ( (x) * (x) )
    下面这个定义很常用:
#define MAX(a,b) ( ((a) > (b)) ? (a) : (b) )

    如果你想写出一个很有个性的C代码,反复使用#define是一个不错的选择。例如,这段代码就极具个性,一个光棍的形象跃然于屏幕上。然而,真正把#define发挥得淋漓尽致的,还是要数这段代码

static声明
    在函数中的变量声明前加一个static可以使这个变量具有“记忆性”。观察下面的程序:
#include <stdio.h>
void printNum()
{
   int a=1;
   static int b=1;
   printf("%d %dn", a++, b++);
}
int main()
{
   int i;
   for ( i=1; i<=5; i++ )
       printNum();
   return 0;
}

    程序输出:
1 1
1 2
1 3
1 4
1 5

short类型和int类型的范围
    最初我们列出的C语言类型和Pascal类型的对比只能提供一个参考。事实上不同的编译器中short和int的范围可能不同。你可以查一下前面说过的limits.h来确定这些类型的实际范围。通常short是16位整数,long是32位整数。在Windows下Dev-C++中int类型是32位。

对64位整型的处理
    和Free Pascal一样,对64位整数类型的处理总是比较麻烦。
    首先,对long long赋值很可能会发生错误,你可以在常数后添加一个LL表明这是long long类型。其次,C语言中有些函数是要区分数据类型的,你需要根据数据类型选用恰当的函数。最后,long long类型的输出很可能也有问题,此时你可以用"%lld"来替换"%d",表明输出的是一个long long类型。在Windows下总要装点怪,我在Windows编译时非要用"%I64d"才行。
    下面的程序代码在Windows下Dev-C++中一切正常。
#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long a;
    a = -5841314520LL;
    a = llabs(a);
    a = a + 1;
    printf("%I64d",a);
    return 0;
}

查漏补缺
    这个系列到这里就结束了。还有我没有说到的语法点吗?欢迎大家补充。

后记
    C语言速成手册到这里就结束了。这很可能是网上现有的原创C语言教材中讲解最快,篇幅最短的,因为它只适合已经学过其它语言,了解程序设计基础知识的人。这一系列的文章略过了大量的概念讲解、示例代码和习题,你可以自己在网上阅读一些C语言程序作为补充。以后我可能还会写一些类似的文章介绍其它语言。下一步我计划写C与C++的区别,对象和类的介绍以及C++的新特性。再以后我可能会向Java或者Ruby的方向发展。
    祝各位努力转C的OIer暑假愉快。

Matrix67原创
转贴请注明出处

数论部分第一节:素数与素性测试

    一个数是素数(也叫质数),当且仅当它的约数只有两个——1和它本身。规定这两个约数不能相同,因此1不是素数。对素数的研究属于数论范畴,你可以看到许多数学家没事就想出一些符合某种性质的素数并称它为某某某素数。整个数论几乎就围绕着整除和素数之类的词转过去转过来。对于写代码的人来说,素数比想像中的更重要,Google一下BigPrime或者big_prime你总会发现大堆大堆用到了素数常量的程序代码。平时没事时可以记一些素数下来以备急用。我会选一些好记的素数,比如4567, 124567, 3214567, 23456789, 55566677, 1234567894987654321, 11111111111111111111111 (23个1)。我的手机号前10位是个素数。我的网站域名的ASCII码连起来(77 97 116 114 105 120 54 55 46 99 111 109)也是个素数。还有,我的某个MM的八位生日也是一个素数。每次写Hash函数之类的东西需要一个BigPrime常量时我就取她的生日,希望她能给我带来好运。偶尔我叫她素MM,没人知道是啥意思,她自己也不知道。
    素数有很多神奇的性质。我写5个在下面供大家欣赏。

1. 素数的个数无限多(不存在最大的素数)
  证明:反证法,假设存在最大的素数P,那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1(所有的素数乘起来加1)。显然这个数不能被任一素数整除(所有素数除它都余1),这说明我们找到了一个更大的素数。

2. 存在任意长的一段连续数,其中的所有数都是合数(相邻素数之间的间隔任意大)
  证明:当0<a<=n时,n!+a能被a整除。长度为n-1的数列n!+2, n!+3, n!+4, …, n!+n中,所有的数都是合数。这个结论对所有大于1的整数n都成立,而n可以取到任意大。

3. 所有大于2的素数都可以唯一地表示成两个平方数之差。
  证明:大于2的素数都是奇数。假设这个数是2n+1。由于(n+1)^2=n^2+2n+1,(n+1)^2和n^2就是我们要找的两个平方数。下面证明这个方案是唯一的。如果素数p能表示成a^2-b^2,则p=a^2-b^2=(a+b)(a-b)。由于p是素数,那么只可能a+b=p且a-b=1,这给出了a和b的唯一解。

4. 当n为大于2的整数时,2^n+1和2^n-1两个数中,如果其中一个数是素数,那么另一个数一定是合数。
  证明:2^n不能被3整除。如果它被3除余1,那么2^n-1就能被3整除;如果被3除余2,那么2^n+1就能被3整除。总之,2^n+1和2^n-1中至少有一个是合数。

5. 如果p是素数,a是小于p的正整数,那么a^(p-1) mod p = 1。
  这个证明就有点麻烦了。
    首先我们证明这样一个结论:如果p是一个素数的话,那么对任意一个小于p的正整数a,a, 2a, 3a, …, (p-1)a除以p的余数正好是一个1到p-1的排列。例如,5是素数,3, 6, 9, 12除以5的余数分别为3, 1, 4, 2,正好就是1到4这四个数。
    反证法,假如结论不成立的话,那么就是说有两个小于p的正整数m和n使得na和ma除以p的余数相同。不妨假设n>m,则p可以整除a(n-m)。但p是素数,那么a和n-m中至少有一个含有因子p。这显然是不可能的,因为a和n-m都比p小。
    用同余式表述,我们证明了:
(p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
    也即:
(p-1)! ≡ (p-1)! * a^(p-1) (mod p)
    两边同时除以(p-1)!,就得到了我们的最终结论:
1 ≡ a^(p-1) (mod p)

    可惜最后这个定理最初不是我证明的。这是大数学家Fermat证明的,叫做Fermat小定理(Fermat's Little Theorem)。Euler对这个定理进行了推广,叫做Euler定理。Euler一生的定理太多了,为了和其它的“Euler定理”区别开来,有些地方叫做Fermat小定理的Euler推广。Euler定理中需要用一个函数f(m),它表示小于m的正整数中有多少个数和m互素(两个数只有公约数1称为互素)。为了方便,我们通常用记号φ(m)来表示这个函数(称作Euler函数)。Euler指出,如果a和m互素,那么a^φ(m) ≡ 1 (mod m)。可以看到,当m为素数时,φ(m)就等于m-1(所有小于m的正整数都与m互素),因此它是Fermat小定理的推广。定理的证明和Fermat小定理几乎相同,只是要考虑的式子变成了所有与m互素的数的乘积:m_1 * m_2 … m_φ(m) ≡ (a * m_1)(a * m_2) … (a * m_φ(m)) (mod m)。我为什么要顺便说一下Euler定理呢?因为下面一句话可以增加我网站的PV:这个定理出现在了The Hundred Greatest Theorems里。

    谈到Fermat小定理,数学历史上有很多误解。很长一段时间里,人们都认为Fermat小定理的逆命题是正确的,并且有人亲自验证了a=2, p<300的所有情况。国外甚至流传着一种说法,认为中国在孔子时代就证明了这样的定理:如果n整除2^(n-1)-1,则n就是素数。后来某个英国学者进行考证后才发现那是因为他们翻译中国古文时出了错。1819年有人发现了Fermat小定理逆命题的第一个反例:虽然2的340次方除以341余1,但341=11*31。后来,人们又发现了561, 645, 1105等数都表明a=2时Fermat小定理的逆命题不成立。虽然这样的数不多,但不能忽视它们的存在。于是,人们把所有能整除2^(n-1)-1的合数n叫做伪素数(pseudoprime),意思就是告诉人们这个素数是假的。
    不满足2^(n-1) mod n = 1的n一定不是素数;如果满足的话则多半是素数。这样,一个比试除法效率更高的素性判断方法出现了:制作一张伪素数表,记录某个范围内的所有伪素数,那么所有满足2^(n-1) mod n = 1且不在伪素数表中的n就是素数。之所以这种方法更快,是因为我们可以使用二分法快速计算2^(n-1) mod n 的值,这在计算机的帮助下变得非常容易;在计算机中也可以用二分查找有序数列、Hash表开散列、构建Trie树等方法使得查找伪素数表效率更高。
    有人自然会关心这样一个问题:伪素数的个数到底有多少?换句话说,如果我只计算2^(n-1) mod n的值,事先不准备伪素数表,那么素性判断出错的概率有多少?研究这个问题是很有价值的,毕竟我们是OIer,不可能背一个长度上千的常量数组带上考场。统计表明,在前10亿个自然数中共有50847534个素数,而满足2^(n-1) mod n = 1的合数n有5597个。这样算下来,算法出错的可能性约为0.00011。这个概率太高了,如果想免去建立伪素数表的工作,我们需要改进素性判断的算法。

    最简单的想法就是,我们刚才只考虑了a=2的情况。对于式子a^(n-1) mod n,取不同的a可能导致不同的结果。一个合数可能在a=2时通过了测试,但a=3时的计算结果却排除了素数的可能。于是,人们扩展了伪素数的定义,称满足a^(n-1) mod n = 1的合数n叫做以a为底的伪素数(pseudoprime to base a)。前10亿个自然数中同时以2和3为底的伪素数只有1272个,这个数目不到刚才的1/4。这告诉我们如果同时验证a=2和a=3两种情况,算法出错的概率降到了0.000025。容易想到,选择用来测试的a越多,算法越准确。通常我们的做法是,随机选择若干个小于待测数的正整数作为底数a进行若干次测试,只要有一次没有通过测试就立即把
这个数扔回合数的世界。这就是Fermat素性测试。
    人们自然会想,如果考虑了所有小于n的底数a,出错的概率是否就可以降到0呢?没想到的是,居然就有这样的合数,它可以通过所有a的测试(这个说法不准确,详见我在地核楼层的回复)。Carmichael第一个发现这样极端的伪素数,他把它们称作Carmichael数。你一定会以为这样的数一定很大。错。第一个Carmichael数小得惊人,仅仅是一个三位数,561。前10亿个自然数中Carmichael数也有600个之多。Carmichael数的存在说明,我们还需要继续加强素性判断的算法。

    Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步,建立了传说中的Miller-Rabin素性测试算法。新的测试基于下面的定理:如果p是素数,x是小于p的正整数,且x^2 mod p = 1,那么要么x=1,要么x=p-1。这是显然的,因为x^2 mod p = 1相当于p能整除x^2-1,也即p能整除(x+1)(x-1)。由于p是素数,那么只可能是x-1能被p整除(此时x=1)或x+1能被p整除(此时x=p-1)。
    我们下面来演示一下上面的定理如何应用在Fermat素性测试上。前面说过341可以通过以2为底的Fermat测试,因为2^340 mod 341=1。如果341真是素数的话,那么2^170 mod 341只可能是1或340;当算得2^170 mod 341确实等于1时,我们可以继续查看2^85除以341的结果。我们发现,2^85 mod 341=32,这一结果摘掉了341头上的素数皇冠,面具后面真实的嘴脸显现了出来,想假扮素数和我的素MM交往的企图暴露了出来。
    这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2,把n-1表示成d*2^r(其中d是一个奇数)。那么我们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是,a^(d * 2^(r-1))要么等于1,要么等于n-1。如果a^(d * 2^(r-1))等于1,定理继续适用于a^(d * 2^(r-2)),这样不断开方开下去,直到对于某个i满足a^(d * 2^i) mod n = n-1或者最后指数中的2用完了得到的a^d mod n=1或n-1。这样,Fermat小定理加强为如下形式:
    尽可能提取因子2,把n-1表示成d*2^r,如果n是一个素数,那么或者a^d mod n=1,或者存在某个i使得a^(d*2^i) mod n=n-1 ( 0<=i<r ) (注意i可以等于0,这就把a^d mod n=n-1的情况统一到后面去了)
    Miller-Rabin素性测试同样是不确定算法,我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数(strong pseudoprime)。第一个以2为底的强伪素数为2047。第一个以2和3为底的强伪素数则大到1 373 653。
    Miller-Rabin算法的代码也非常简单:计算d和r的值(可以用位运算加速),然后二分计算a^d mod n的值,最后把它平方r次。程序的代码比想像中的更简单,我写一份放在下边。虽然我已经转C了,但我相信还有很多人看不懂C语言。我再写一次Pascal吧。函数IsPrime返回对于特定的底数a,n是否是能通过测试。如果函数返回False,那说明n不是素数;如果函数返回True,那么n极有可能是素数。注意这个代码的数据范围限制在longint,你很可能需要把它们改成int64或高精度计算。
function pow( a, d, n:longint ):longint;
begin
   if d=0 then exit(1)
   else if d=1 then exit(a)
   else if d and 1=0 then exit( pow( a*a mod n, d div 2, n) mod n)
   else exit( (pow( a*a mod n, d div 2, n) * a) mod n);
end;

function IsPrime( a,n:longint ):boolean;
var
   d,t:longint;
begin
   if n=2 then exit(true);
   if (n=1) or (n and 1=0) then exit(false);
   d:=n-1;
   while d and 1=0 do d:=d shr 1;
   t:=pow( a, d, n );
   while ( d<>n-1 ) and ( t<>1 ) and ( t<>n-1 ) do
   begin
      t:=(t * t)mod n;
      d:=d shl 1;
   end;
   exit( (t=n-1) or (d and 1=1) );
end;

    对于大数的素性判断,目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取,但当待测数不太大时,选择测试底数就有一些技巧了。比如,如果被测数小于4 759 123 141,那么只需要测试三个底数2, 7和61就足够了。当然,你测试的越多,正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试,所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数,那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为,Miller-Rabin素性测试的正确率可以令人接受,随机选取k个底数进行测试算法的失误率大概为4^(-k)。

    Miller-Rabin算法是一个RP算法。RP是时间复杂度的一种,主要针对判定性问题。一个算法是RP算法表明它可以在多项式的时间里完成,对于答案为否定的情形能够准确做出判断,但同时它也有可能把对的判成错的(错误概率不能超过1/2)。RP算法是基于随机化的,因此多次运行该算法可以降低错误率。还有其它的素性测试算法也是概率型的,比如Solovay-Strassen算法。另外一些素性测试算法则需要预先知道一些辅助信息(比如n-1的质因子),或者需要待测数满足一些条件(比如待测数必须是2^n-1的形式)。前几年AKS算法轰动世界,它是第一个多项式的、确定的、无需其它条件的素性判断算法。当时一篇论文发表出来,题目就叫PRIMES is in P,然后整个世界都疯了,我们班有几个MM那天还来了初潮。算法主要基于下面的事实:n是一个素数当且仅当(x-a)^n≡(x^n-a) (mod n)。注意这个x是多项式中的未知数,等式两边各是一个多项式。举个例子来说,当a=1时命题等价于如下结论:当n是素数时,杨辉三角的第n+1行除两头的1以外其它的数都能被n整除。

Matrix67原创
转贴请注明出处

C语言速成手册(五):其它运算符、文件操作、其它函数

条件运算符
    条件运算符的格式如下:
表达式1 ? 表达式2 : 表达式3
    它表示:若表达式1为真(非0),则返回表达式2,否则返回表达式3。

    下面的函数返回两个数中较小的一个:
long min( long a, long b)
{
   return (a<b)?a:b;
}

    很多地方都可能用到条件运算符。再比如求平均数时你可能会这样写:
average = (n>0) ? sum/n : 0;

自加、自减
    a=a+1可以写成a++或++a,a=a-1可以写成a–或–a 。例如,你会经常看到这样的写法:
for ( i=1; i<=10; i++ )
{
}

    如果自加自减不是单独成句,而是放在其它语句中的话,那么a++和++a是有区别的。a++表示“用了后再加”,++a表示“加了后再用”。a–和–a的区别同理。下面的代码输出0 1 1 1。
int a=0;
printf("%d ",a++);
printf("%d ",a);

int b=0;
printf("%d ",++b);
printf("%d",b);

其它运算符
    下面所有的a和b均为整型,则:
C语言  |  Pascal语言
——-+————-
a & b  |  a and b
a | b  |  a or b
a ^ b  |  a xor b
a << b |  a shl b
a >> b |  a shr b

  简写 |    含义
——-+————-
a += b |  a = a + b
a -= b |  a = a – b
a *= b |  a = a * b
a /= b |  a = a / b
a %= b |  a = a % b
a &= b |  a = a & b
a |= b |  a = a | b
a ^= b |  a = a ^ b
a <<= b|  a = a << b
a >>= b|  a = a >> b

各种标准输入输出函数
    下列函数都是stdio.h提供的。stdio.h还提供了一个EOF常量(其实就是-1),用来标识输入数据结束。
         函数                |                    用途
—————————–+———————————————————-
int scanf(str,arg1,…,argn) | 按指定格式读入数据,返回成功被赋值的变量个数。如果已无输入或出错则返回EOF
int printf(str,arg1,…,argn)| 按指定格式输出数据,返回成功输出的字符个数。
int getchar()                | 返回标准输入的下一个字符,如果已无输入或出错则返回EOF。
int putchar(c)               | 向屏幕输出一个字符c,同时返回这个字符,如果出错则返回EOF。
char *gets(str)              | 把这一行输入数据存入字符串str并返回该字符串,如果已无输入或出错则返回NULL
int puts(str)                | 输出字符串并自动输出一个换行符,如果出错则返回EOF。

内存输入输出操作
    stdio.h中提供的sscanf和sprintf两个函数可以把一个字符串当作输入输出对象,其用法与scanf和printf差不多,只不过要多一个参数。你需要把目标字符数组作为函数的第一个参数。
    使用sscanf和sprintf可以方便地进行数字和字符串互转,并实现各种字符串操作。看下面的程序代码:
#include <stdio.h>
int main()
{
    char st[80]="5:43:04";
    int h,m,s;
    
    sscanf(st, "%d:%d:%d", &h, &m, &s);
    printf("Hour:%d Minute:%d Second:%dn", h, m, s);
    
    sprintf(st, "My birthday is %d-%d-%d", 1988, 5, 16);
    printf("%s",st);
    
    return 0;
}

    输出为:
Hour:5 Minute:43 Second:4
My birthday is 1988-5-16

文件输入输出操作
    stdio.h还提供了FILE类型,用于定义文件指针。例如,下面的语句定义了两个待操作的文件:
FILE *in, *out;
    打开一个文件使用fopen函数,该函数的参数为两个字符串。前一个参数指定文件名,后一个参数指定打开模式("r"=读, "w"=写, "a"=在已有文件后继续写 )。函数返回一个文件指针作为此文件的标识供以后使用。

    和文件操作相关的函数有:
         函数                      |                    用途
———————————–+———————————————————-
int fscanf(file,str,arg1,…,argn) | 从file指针对应的文件中读入数据,具体行为同scanf
int fprintf(file,str,arg1,…,argn)| 向file指针对应的文件中输出数据,具体行为同printf
int fgetc(file)                    | 从file指针对应的文件中读入数据,具体行为同getchar
int fputc(c,file)                  | 向file指针对应的文件中输出数据,具体行为同putchar
char *fgets(str,n,file)            | 从file指针对应的文件中读入数据到str字符串,读到第n个字符为止
int fputs(str,file)                | 向file指针对应的文件中输出数据,具体行为同puts
int fflush(file)                   | 立即写入文件,同Pascal中的flush
int feof(file)                     | 文件是否结束,同Pascal中的eof
int fclose(file)                   | 关闭文件,同Pascal中的close

    下面的程序是文件操作版A+B问题,你可以看到文件操作具体的实现方法。
#include <stdio.h>
int main()
{
    FILE *in, *out;
    long a, b;
    
    in = fopen("test.in","r");
    fscanf(in, "%d%d", &a, &b);
    fclose(in);
    
    out = fopen("test.out","w");
    fprintf(out, "%d", a+b);
    fclose(out);
    
    return 0;
}

整型上下限
    Pascal可以用maxlongint来表示longint类型的最大值。C语言中也有类似的定义可以直接使用。使用C语言中的相关定义需要在程序代码前加上#include <limits.h>。

   定义    |    表示
———–+—————————–
CHAR_MAX   | char类型大小上限
CHAR_MIN   | char类型大小下限
SHRT_MAX   | short类型的大小上限
SHRT_MIN   | short类型的大小下限
USHRT_MAX  | unsigned short类型的大小上限
INT_MAX    | int类型的大小上限
INT_MIN    | int类型的大小下限
UINT_MAX   | unsigned int类型的大小上限
LONG_MAX   | long类型的大小上限
LONG_MIN   | long类型的大小下限
ULONG_MAX  | unsigned long类型的大小上限
LLONG_MAX  | long long类型的大小上限
LLONG_MIN  | long long类型的大小下限
ULLONG_MAX | unsigned long long类型的大小上限

常用数学函数
    使用下面的函数需要在程序代码前加上#include <math.h>。

   函数             |     用途
——————–+—————–
double sin(x)       |  正弦
double cos(x)       |  余弦
double tan(x)       |  正切
double asin(x)      |  反正弦
double acos(x)      |  反余弦
double atan(x)      |  反正切
double sqrt(x)      |  开平方
double pow(x,y)     |  x的y次方
double exp(x)       |  e的x次方
double exp2(x)      |  2的x次方
double log(x)       |  以e为底的对数
double log2(x)      |  以2为底的对数
double log10(x)     |  以10为底的对数
double fabs(x)      |  x的绝对值
double fmod(x,y)    |  小数版的mod
double floor(x)     |  小于等于x的最大整数
double ceil(x)      |  大于等于x的最小整数
double trunc(x)     |  舍弃小数部分
double round(x)     |  小数部分四舍五入
long lround(x)      |  小数部分四舍五入,返回long
long long llround(x)|  小数部分四舍五入,返回long long

常用字符串函数
    使用以下函数需要在程序代码前加上#include <string.h>。
    参数s1和s2总是两个字符串,参数c总是一个字符。

    函数               |        用途
———————–+—————————–
int strlen(s1)         | 返回s1的长度
char *strcpy(s1,s2)    | 把s2赋值给s1,返回s1
char *strcat(s1,s2)    | 将s2连接到s1后面,返回s1
int strcmp(s1,s2)      | 比较两字符串,s1小则返回负数,相等返回0,s1大返回正数
char *strchr(s1,c)     | 寻找s1第一次出现c的位置,找到则返回指向该位置的指针,没找到则返回NULL
char *strstr(s1,s2)    | 寻找s2第一次出现在s1的位置,找到则返回指向该位置的指针,没找到则返回NULL
char *strpbrk(s1,s2)   | 寻找s2中的任意字符第一次出现在s1的位置,找到则返回指向该位置的指针,没找到则返回NULL

观察下面的程序:
#include <stdio.h>
#include <string.h>
int main()
{
    char st[80]="matrix67";
    strcat(st,".com");
    printf( "%sn", st );
    printf( "%dn", strlen(st) );
    printf( "%dn", strcmp(st,"my blog") );
    printf( "%cn", *strchr(st,'i') );
    printf( "%sn", strpbrk(st,"3.1415927") );
    printf( "%dn", strstr(st,"x6")-st );

    return 0;
}

输出为:
matrix67.com
12
-1
i
7.com
5

内存操作函数
    下面的一些函数主要用于字符串操作,因此属于string.h 。假设m1和m2都是void *类型。

         函数                |            用途
—————————–+———————————–
int memcmp (m1, m2, n)     |  比较m1和m2的头n个字节,相同返回0,m1小返回负数,m2小返回正数
void *memmove (m1, m2, n)    |  把m2的前n个字节复制到m1的位置,相当于Pascal中的move
void *memset (m1, c, n)      |  把m1的前n个字节全部设为c,相当于Pascal中的fillchar

    下面这段代码的结果是把st字符串变成了"Matrix67, I love UUUUUUUUUUUU…"。
char st[80]="Matrix67, I love someone else...";
memset(st+17,'U',12);

    当然memset更常用的是初始化数组。例如动态规划前初始化f数组:
long f[1000][1000];
memset( f, 0, sizeof(f) );

stdlib.h提供的其它函数
    函数                 |                        用途
————————-+————————————————-
int abs(n)               |  取绝对值,适用于int
long labs(n)             |  取绝对值,适用于long
long long llabs(n)       |  取绝对值,适用于long long
double atof(str)         |  把字符串str转化为数字,返回double类型
int atoi(str)       &n
bsp;    |  把字符串str转化为数字,返回int类型
long atol(str)           |  把字符串str转化为数字,返回long类型
long long atoll(str)     |  把字符串str转化为数字,返回long long类型
void exit(n)             |  退出程序,返回的错误代码为n(0=正常),相当于Pascal的halt
int rand()               |  产生一个随机数,范围在stdlib.h中指定(通常最小为0,最大为int的上限)
void srand(n)            |  设置随机数发生器的种子为n
void qsort(arr,n,size,fn)|  快排,四个参数分别为数组,长度,类型大小,比较函数。

    比较函数的格式应该为
int 函数名(const void *参数1, const void *参数2)
    如果参数1小于参数2,则该函数返回负数,等于则返回0,大于则正数。因此,你可以自己给“大小”下定义。
    下面的程序合法地调用了qsort函数。注意随机函数后的取余运算,这是生成某个范围内的随机数的常用手段。
#include <stdlib.h>
int comp(const void *i, const void *j)
{
    return *(long *)i - *(long *)j;
}

int main()
{
    long n=1000, i, a[n];
    for (i=0; i<n; i++) a[i]=rand()%10000;
    qsort(a, n, sizeof(long), comp);
    return 0;
}

利用assert帮助调试
    assert可以在程序不满足某个条件时输出错误信息并立即终止运行,这对调试很有帮助。使用assert语句需要包含头文件assert.h。观察下面的程序代码:
#include <stdio.h>
#include <assert.h>

int main()
{
    int n;
    scanf("%d",&n);
    assert(n!=0);
    printf("%f",1.0/n);
    return 0;
}

    当读入的数是0时,程序执行printf前就会提前终止,并且输出错误信息。这可以保证后面的语句正常执行,避免异常错误。这显然比用if语句排除异常错误更好一些。在每一个潜在的异常错误前加上assert,当程序出错时你可以很快确定是哪里的问题。

Matrix67原创
转贴请注明出处