牛B的正则表达式:素数判定与线性方程求解

    今天又学到一个牛B东西。你相信吗?正则表达式竟然可以用来判定素数,甚至可以用来解方程!下面这段正则表达式可以用来判断,一个字符串的长度是否为合数(假设这个字符串里全是字符'1'):
^1?$|^(11+?)1+$
    不信的话,把下面这段代码复制到你浏览器的地址栏里运行一下,True表示这个数为合数,False表示这个数为素数:

javascript:var st="1";for(var i=2;i<100;i++)document.write(i," ",/^1?$|^(11+?)1+$/.test(st=st+"1"),"<br/>");document.close();

    其实,它的原理很简单。加号表示匹配一次或多次(加上一个问号表示非贪婪模式),1表示引用括号里的内容,头尾的^和$则避免了部分匹配的情况。这样,^(11+?)相当于枚举除数大小,而1+$则用于检验整个字符串是否能按此大小恰好分完。如果除得尽,则匹配成功,字符串长度为合数。另外,前面的^1?$只是为了处理n=0或n=1时的特殊情况,而符号|则表示“或者”的意思。

    采用同样的方法,我们还可以想出正则表达式其它一些类似的用途。比如,我们可以用这个正则表达式检查方程11x + 2y + 5z = 115是否有自然数解:
^(.*)1{10}(.*)2{1}(.*)3{4}$
    正则表达式中,{x}表示和前面的内容匹配x次。只要用这个表达式去检测一个有115个字符的字符串,匹配成功则表示有自然数解。它的原理和上面的基本一样,我就不再重复了。

参考资料:http://blog.stevenlevithan.com/archives/algebra-with-regexes

趣题:量子计算机、另类编程语言和幂函数的解释

    很久没有更新和信息学有关的东西了。今天和大家分享一个非常有趣的题目,我已经很久没看见如此精彩有趣的题目了。为了引入这个问题,我们先来介绍一个假想的编程语言QCPL。就像LISP一样,它是一个基于函数的语言:没有变量,没有for循环,一切东西都是用函数来表示的。另外,就像FORTRAN一样,QCPL语言不支持递归,也就是说一个函数不能递归地调用自己。QCPL的另一个有趣的特点是,所有的函数都只能返回一个Boolean值。比如说,下面这个函数的作用就是判断x+2和y+2的乘积是否等于z:
MULT_PLUS_TWO(x,y,z): (x+2)*(y+2)=z

    QCPL也有逻辑运算符。事实上,QCPL里的合法运算符一共只有8个,其中6个分别如下:

运算符 |  作用  |     输入      |     输出
——-+——–+—————+—————
  +    |  相加  |  两个自然数   |  一个自然数
  *    |  相乘  |  两个自然数   |  一个自然数
  =    |  等于  |  两个自然数   | 一个Boolean值
  &    | 逻辑和 | 两个Boolean值 | 一个Boolean值
  |    | 逻辑或 | 两个Boolean值 | 一个Boolean值
  !    | 逻辑非 | 一个Boolean值 | 一个Boolean值

    另外两个运算符就要重点介绍了。这是QCPL语言真正牛B的地方——它是专门为量子计算机设计的!你可以让这台计算机平行地穷尽完某些变量所有可能的取值,这一切仅仅在一瞬间内就可以完成。这两个特殊的运算符(以后我们管它们叫做“定量运算符”)就是专门用来干这件牛B事的:"Ex"是“存在性定量运算符”,表示让计算机找出是否存在一个满足表达式的自然数x;"Ax"是“通用性定量运算符”,用于询问计算机该表达式是否对所有的自然数x均成立。比如,运用定量运算符,我们可以立即写出素数/合数判断函数:
COMPOSITE(n): Ex,Ey,MULT_PLUS_TWO(x,y,n)
PRIME(n): !(COMPOSITE(n)|n=0|n=1)

    其中,Ex,Ey,MULT_PLUS_TWO(x,y,n)的意思就是说,是否存在某一对x和y,使得MULT_PLUS_TWO(x,y,n)为真。只要(某一个平行世界里的)计算机找到了任何一对满足条件的x和y,整个COMPOSITE(n)立即返回True。如果对于所有的自然数x和y,MULT_PLUS_TWO(x,y,n)都不可能为真时,整个函数才返回False。别忘了这是一台量子计算机,穷举的过程可以在一瞬间内完成。

    好了,下面我们再给出几个基本的函数。函数SUM用于计算x加y是否等于z,而函数PRODUCT则用于检验x乘以y是否等于z:
SUM(x,y,z): x+y=z
PRODUCT(x,y,z): x*y=z

    现在,你的任务就是写出一个函数POWER(x,y,z),当且仅当x的y次方等于z时函数才返回True。相信我,这道题没有那么容易。
Read more…

codepad.org:分享程序代码的最佳去处

    codepad是一个新的在线小工具,它的界面很清爽,使用方法非常简便,你甚至根本不用注册。你可以随时用它来保存、分享程序代码,提交后系统会给你一个形如codepad.org/xxxxxxxx的地址。它支持纯文本、C、C++、Python、Perl、Ruby等各种格式(不支持Pascal),并且提供了自动语法高亮功能方便大家阅读。最神奇的是,它可以显示你的程序代码的运行结果!因此这绝对是你保存和分享程序代码的最佳去处。
    我在http://codepad.org/my2f2wEP分享了一个IOCCC的代码。
    难以置信的是,这么好的东西居然在那个伟大的建筑之外!?反正我裸着是连不上的。

    顺便帮忙八卦:)

有趣的C语言问题 测试你对C语言的熟悉程度

下面这个程序输出什么?
enum {false,true};
int main()
{
        int i=1;
        do
        {
                printf("%dn",i);
                i++;
                if(i < 15)
                        continue;
        }while(false);
        return 0;
}

你相信么?下面这个程序输出的两行东西不一样!
  #include <stdio.h>
  #define f(a,b) a##b
  #define g(a)   #a
  #define h(a) g(a)

  int main()
  {
          printf("%sn",h(f(1,2)));
          printf("%sn",g(f(1,2)));
          return 0;
  }

下面的程序看似完全正确。你能看出它为什么通不过编译吗?
看出问题前不要去试着编译,不然你会后悔你没看出来这个低级的语法错误。
#include<stdio.h>

void OS_Solaris_print()
{
        printf("Solaris - Sun Microsystemsn");
}

void OS_Windows_print()
{
        printf("Windows - Microsoftn");

}
void OS_HP-UX_print()
{
        printf("HP-UX - Hewlett Packardn");
}

int main()
{
        int num;
        printf("Enter the number (1-3):n");
        scanf("%d",&num);
        switch(num)
        {
                case 1:
                        OS_Solaris_print();
                        break;
                case 2:
                        OS_Windows_print();
                        break;
                case 3:
                        OS_HP-UX_print();
                        break;
                default:
                        printf("Hmm! only 1-3 :-)n");
                        break;
        }

        return 0;
}

为什么下面这个程序的输出不是NONE?看你多久才能看出来。
  #include<stdio.h>
  int main()
  {
          int a=10;
          switch(a)
          {
                  case '1':
                      printf("ONEn");
                      break;
                  case '2':
                      printf("TWOn");
                      break;
                  defa1ut:
                      printf("NONEn");
          }
          return 0;
  }

下面这个程序输出什么?
#include <stdio.h>
int main()
{
        int i=43;
        printf("%dn",printf("%d",printf("%d",i)));
        return 0;
}

下面这个程序输出什么?
  #include<stdio.h>
  int main()
  {
      int a=1;
      switch(a)
      {   int b=20;
          case 1: printf("b is %dn",b);
                  break;
          default:printf("b is %dn",b);
                  break;
      }
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
      int i;
      i = 10;
      printf("i : %dn",i);
      printf("sizeof(i++) is: %dn",sizeof(i++));
      printf("i : %dn",i);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  #include <stdlib.h>

  #define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))

  #define PrintInt(expr) printf("%s:%dn",#expr,(expr))
  int mai
n()
  {
      /* The powers of 10 */
      int pot[] = {
          0001,
          0010,
          0100,
          1000
      };
      int i;

      for(i=0;i<SIZEOF(pot);i++)
          PrintInt(pot[i]);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
    int a=3, b = 5;

    printf(&a["Ya!Hello! how is this? %sn"], &b["junk/super"]);
    printf(&a["WHAT%c%c%c  %c%c  %c !n"], 1["this"],
       2["beauty"],0["tool"],0["is"],3["sensitive"],4["CCCCCC"]);
    return 0;
  }

下面这个程序输出什么?
#include <stdio.h>
int main()
{
        int i=23;
        printf("%d %dn",i++,i++);
        return 0;
}

为什么下面这个程序的输出不是10?我故意取消了语法高亮:)
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %dn",#expr,(expr))
  int main()
  {
      int y = 100;
      int *p;
      p = malloc(sizeof(int));
      *p = 10;
      y = y/*p; /*dividing y by *p */;
      PrintInt(y);
      return 0;
  }

下面这个程序输出什么?
  #include <stdio.h>
  int main()
  {
      int i = 6;
      if( ((++i < 7) && ( i++/6)) || (++i <= 9))
          ;
      printf("%dn",i);
      return 0;
  }

下面这段代码是否合法?
  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %dn",#expr,(expr))
  int max(int x, int y)
  {
      (x > y) ? return x : return y;
  }

  int main()
  {
      int a = 10, b = 20;
      PrintInt(a);
      PrintInt(b);
      PrintInt(max(a,b));
  }

这是什么意思?有什么潜在的问题?
  #define SWAP(a,b) ((a) ^= (b) ^= (a) ^= (b))

这是什么意思?
  #define ROUNDUP(x,n) ((x+n-1)&(~(n-1)))

一些C语言的教材上会给出一个很经典的宏定义
  #define isupper(c) (((c) >= 'A') && ((c) <= 'Z'))
但这种宏定义的方法存在不足之处,一旦遇到下面这种情况就出问题了:
  char c;
  /* ... */
  if(isupper(c++))
  {
      /* ... */
  }

为了避免这种问题,应该怎样来定义isupper?

怎样用printf函数打印"I can print %"?别忘了百分号是用于格式化输出的。
不用任何比较运算符,写一个程序找出三个数中的最小数。
不用+号,(用位运算)实现加法运算。

最有趣的一个问题:不用分号,写一个Hello World程序。
这是有可能的,而且办法非常简单,只用到了最基本的语法规则。
实在想不出来再看答案吧(白色的):
#include <stdio.h>
int main()
{
    if (printf("Hello World")){}
}

查看更多:http://www.gowrikumar.com/c/

计算阶乘的另一些有趣的算法

    一个正整数n的阶乘就是前n个正整数的乘积,我们通常需要n-1次乘法操作来算出精确的值。不像等差数列求和、a的n次幂之类的东西,目前求阶乘还没有什么巨牛无比的高效算法,我们所能做的仅仅是做一些小的优化。

更少的乘法运算次数?
    在高精度运算中,乘法计算的速度远远慢于加减法,因此我们有必要减少乘法运算的次数。下面我将做一个非常简单的变换,使得计算阶乘只需要n/2次乘法。继续看下去之前,你能自己想到这个算法来吗?

    我们可以把一个数的阶乘转换为若干个平方差的积。例如,假如我想求9!,我可以把前9个正整数的乘积写成这个样子:
   1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9
= (5-4) * (5-3) * (5-2) * (5-1) * 5 * (5+1) * (5+2) * (5+3) * (5+4)
= (5-1) * (5+1) * (5-2) * (5+2) * (5-3) * (5+3) * (5-4) * (5+4) * 5
= (5^2 – 1^2) * (5^2 – 2^2) * (5^2 – 3^2) * (5^2 – 4^2) * 5
    注意到一个有趣的事实:上面的四个平方差算出来分别是24, 21, 16, 9,它们之间的差正好是连续的奇数(因为n^2等于前n个正奇数的和)。因此,我们可以用初始数(n/2)^2不断减去一个个的正奇数,求出所有n/2个平方差,再用n/2次乘法把它们乘起来。这种算法实现起来非常简单,并且(当n不大时)同样只需要单精度乘高精度,但需要的乘法次数大大减少了。假设我们已经有了一个高精度类,求n!只需要下面几句话:
long h=n/2, q=h*h;
long r = (n&1)==1 ? 2*q*n : 2*q;
f = LargeInteger.create(r);
for(int d=1; d<n-2; d+=2)
   f = f.multiply(q-=d);

更少的总运算次数?
    尽量提取阶乘中的因子2,我们可以得到另一种阶乘运算的优化方法。这很可能是不需要分解质因数的阶乘算法中最快的一种。
    假如我们需要计算20!,我们可以把20拆成若干组正奇数的乘积:

  1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 2 * 4 * 6 * 8 * 10 * 12 * 14 * 16 * 18 * 20
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 2^10
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 2 * 4 * 6 * 8 * 10 * 2^10
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 2 * 3 * 4 * 5 * 2^15
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 2 * 4 * 2^15
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 1 * 2 * 2^17
= 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 * 1 * 3 * 5 * 7 * 9 * 1 * 3 * 5 * 1 * 2^18

    只需要一次累乘就可以求到每一组奇数的乘积,最后再花费log(n)次乘法把它们全部乘起来。最后的那个2^18也可以二分计算出来。真正的代码还有很多细节上的优化,另外还借用了递归使得操作变得更加简便。你可以在本文最后附的那个链接里去找Split-Recursive算法。

还能再快一点么?
    继续扩展上面的算法,我们可以想到,如果把每个数的质因数都分解出来,并且统计每种质因子有多少个,我们就可以多次使用二分求幂,再把它们的结果乘起来。注意这里并不是真的要老老实实地去分解每个数的质因子。对于每个质数x,我们可以很快算出前n个正整数一共包含有多少个质因子x(记得如何求n!末尾有多少个0么)。这种算法的效率相当高,已经能够满足大多数人的需要了。

另一种诡异的阶乘算法:
    这个算法可能是所有有名字的阶乘算法中最慢的一个了(Additive Moessner算法),它对一个数列进行重复的累加操作,一次次地计算前缀和,总共将花费O(n^3)次加法操作。但是,令人费解的是,这个简单的程序为什么可以输出前n个正整数的阶乘呢?
a[0]:=1;
for i:=1 to n do
begin
   a[i]:=0;
   for j:=n downto 1 do
   begin
      for k:=1 to j do
         a[k]:=a[k]+a[k-1]
      write(a[i],' ');
   end;
end;

    我在网上搜索相关的东西时找到了另一个有趣的东西。对一个初始时全为1的数列反复进行这两个操作:累加求前缀和,然后以1,2,3,…的间隔划掉其中一部分数(即划去所有位置编号为三角形数的数)形成新的序列。类似的数列操作方法最先由Alfred Moessner提出的,我们这里不妨把它叫做Moessner数列。你会发现,第n轮操作开始前,数列的第一个数恰好是n! 。看看下面的例子吧:

1 1 1 1 1 1 1 1 1  1  1  1  1  1  1 …
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …
x 2 x 4 5 x 7 8 9  x 11 12 13 14  x …

2 4  5  7  8  9 11 12 13 14 …
2 6 11 18 26 35 46 58 71 85 …
x 6  x 18 26  x 46 58 71  x …

6 18 26 46  58  71 …
6 24 50 96 154 225 …
x 24  x 96 154   x …

24  96 154 …
24 120 274 …
x 120  x  …

120 …
…..

    当然,发现前面O(n^3)的程序和这个Moessner数列的关联时我很是吃了一惊:在前面的程序里,如果你输出每一次i循环末所得到的数列,你会发现输出的这些数正好就是后面这个问题里被我们划掉的数,而它们其实就是第一类Stirling数!
    这到底是为什么呢?是什么东西把阶乘、第一类Stirling数、Moessner数列和那个O(n^3)的程序联系在一起的呢?昨天,我想这个问题想了一天,最后终于想通了。如果把Moessner数列排列成这个样子,一切就恍然大悟了:

  
    仔细观察上图,我们会发现:
    1. 按照Moessner数列的定义,每个数都应该等于它左边的数和左上角的数的和(这个“左边”可以跳过若干空格)。例如,35 = 9 + 26,46 = 11 + 35。排成一系列三角形后,每个三角形最右边一列的数就是被划去的数,它永远不能参与它下面的那些行的运算。
    2. 设a[n,i,j]表示左起第n个三角形阵列中的第i行右起第j列上的数,则a[n,i,j]=a[n-1,i-1,j]*n + a[n-1,i,j],例如274=50*5+24。如果递推时遇到空白位置而它左边隔若干空格的地方还有数的话,则需要用左边的数来补,例如18=4*4+2。对于每个三角形的最后一列来说,这个性质实际上就是第一类Stirling数的递推关系,因此Moessner数列中才会出现第一类Stirling数。
    3. 在第一类Stirling数中,s(n,1)=n! ,也即左起第n个三角形最底端的那个数等于n!。从上面的第二个性质来看,这也是显然的。
    4. O(n^3)的算法实际上就是在绘制上面这个图。每一次j循环末,我们得到
的序列是第i个三角形中每一行左起第j个数组成的序列。例如,计算第5个三角形内的数时,程序首先累加出1, 11, 46, 96, 120, 120,这样便算出了a[5]=120,数列的前5个数再次累加即得到1, 12, 58, 154, 274,由此算出a[4]=274。
    第二个性质可以利用第一个性质进行数学归纳法证明,证明很简单,我就不多说了。现在我尽可能少写一些繁琐的细节,节约一些时间用来复习古代汉语。

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

查看更多:
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
http://www.luschny.de/math/factorial/index.html <—- 巨牛,20多种阶乘算法的代码!