有没有一段代码,让你觉得人类的智慧也可以璀璨无比?

Broadcasted at April 7, 2016 at 10:01AM:
Amazing~~~

网友在知乎的一个提问帖:

有没有一段代码,让你觉得人类的智慧也可以璀璨无比?

不一定要是完整算法,就是那种看着看着就觉得嗨爆了,惊为天人的结构或语句。

下面是【烧茄子】引用了知名博主 Matrix67 的一篇博文:

用三段 140 字符以内的代码生成一张 1024×1024 的图片

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推这么长的代码来生成一张图片。

具体地说,参赛者需要用 C++ 语言编写 RD 、 GR 、 BL 三个函数,每个函数都不能超过 140 个字符。每个函数都会接到 i 和 j 两个整型参数(0 ≤ i, j ≤ 1023),然后需要返回一个 0 到 255 之间的整数,表示位于 (i, j) 的像素点的颜色值。举个例子,如果 RD(0, 0) 和 GR(0, 0) 返回的都是 0 ,但 BL(0, 0) 返回的是 255 ,那么图像的最左上角那个像素就是蓝色。

参赛者编写的代码会被插进下面这段程序当中(我做了一些细微的改动),最终会生成一个大小为 1024×1024 的图片。

// NOTE: compile with g++ filename.cpp -std=c++11
 

 
#include <iostream>
 
#include <cmath>
 
#include <cstdlib>
 
#define DIM 1024
 
#define DM1 (DIM-1)
 
#define _sq(x) ((x)*(x)) // square
 
#define _cb(x) abs((x)*(x)*(x)) // absolute value of cube
 
#define _cr(x) (unsigned char)(pow((x),1.0/3.0)) // cube root
 

 
unsigned char GR(int,int);
 
unsigned char BL(int,int);
 

 
unsigned char RD(int i,int j){
 
   // YOUR CODE HERE
 
}
 
unsigned char GR(int i,int j){
 
   // YOUR CODE HERE
 
}
 
unsigned char BL(int i,int j){
 
   // YOUR CODE HERE
 
}
 

 
void pixel_write(int,int);
 
FILE *fp;
 
int main(){
 
    fp = fopen("MathPic.ppm","wb");
 
    fprintf(fp, "P6\n%d %d\n255\n", DIM, DIM);
 
    for(int j=0;j<DIM;j++)
 
        for(int i=0;i<DIM;i++)
 
            pixel_write(i,j);
 
    fclose(fp);
 
    return 0;
 
}
 
void pixel_write(int i, int j){
 
    static unsigned char color[3];
 
    color[0] = RD(i,j)&255;
 
    color[1] = GR(i,j)&255;
 
    color[2] = BL(i,j)&255;
 
    fwrite(color, 1, 3, fp);
 
}

我选了一些自己比较喜欢的作品,放在下面和大家分享。

首先是一个来自 Martin Büttner 的作品:

它的代码如下:

unsigned char RD(int i,int j){
 
return (char)(_sq(cos(atan2(j-512,i-512)/2))*255);
 
}
 

 
unsigned char GR(int i,int j){
 
return (char)(_sq(cos(atan2(j-512,i-512)/2-2*acos(-1)/3))*255);
 
}
 

 
unsigned char BL(int i,int j){
 
return (char)(_sq(cos(atan2(j-512,i-512)/2+2*acos(-1)/3))*255);
 
}

同样是来自 Martin Büttner 的作品:

这是目前暂时排名第一的作品。它的代码如下:

unsigned char RD(int i,int j){
 
#define r(n)(rand()%n)
 
static char c[1024][1024];return!c[i][j]?c[i][j]=!r(999)?r(256):RD((i+r(2))%1024,(j+r(2))%1024):c[i][j];
 
}
 

 
unsigned char GR(int i,int j){
 
static char c[1024][1024];return!c[i][j]?c[i][j]=!r(999)?r(256):GR((i+r(2))%1024,(j+r(2))%1024):c[i][j];
 
}
 

 
unsigned char BL(int i,int j){
 
static char c[1024][1024];return!c[i][j]?c[i][j]=!r(999)?r(256):BL((i+r(2))%1024,(j+r(2))%1024):c[i][j];
 
}

下面这张图片仍然出自 Martin Büttner 之手:

难以想象, Mandelbrot 分形图形居然可以只用这么一点代码画出:

unsigned char RD(int i,int j){
 
float x=0,y=0;int k;for(k=0;k++<256;){float a=x*x-y*y+(i-768.0)/512;y=2*x*y+(j-512.0)/512;x=a;if(x*x+y*y>4)break;}return log(k)*47;
 
}
 

 
unsigned char GR(int i,int j){
 
float x=0,y=0;int k;for(k=0;k++<256;){float a=x*x-y*y+(i-768.0)/512;y=2*x*y+(j-512.0)/512;x=a;if(x*x+y*y>4)break;}return log(k)*47;
 
}
 

 
unsigned char BL(int i,int j){
 
float x=0,y=0;int k;for(k=0;k++<256;){float a=x*x-y*y+(i-768.0)/512;y=2*x*y+(j-512.0)/512;x=a;if(x*x+y*y>4)break;}return 128-log(k)*23;
 
}

Manuel Kasten 也制作了一个 Mandelbrot 集的图片,与刚才不同的是,该图描绘的是 Mandelbrot 集在某处局部放大后的结果:

它的代码如下:

unsigned char RD(int i,int j){
 
double a=0,b=0,c,d,n=0;
 
while((c=a*a)+(d=b*b)<4&&n++<880)
 
{b=2*a*b+j*8e-9-.645411;a=c-d+i*8e-9+.356888;}
 
return 255*pow((n-80)/800,3.);
 
}
 

 
unsigned char GR(int i,int j){
 
double a=0,b=0,c,d,n=0;
 
while((c=a*a)+(d=b*b)<4&&n++<880)
 
{b=2*a*b+j*8e-9-.645411;a=c-d+i*8e-9+.356888;}
 
return 255*pow((n-80)/800,.7);
 
}
 

 
unsigned char BL(int i,int j){
 
double a=0,b=0,c,d,n=0;
 
while((c=a*a)+(d=b*b)<4&&n++<880)
 
{b=2*a*b+j*8e-9-.645411;a=c-d+i*8e-9+.356888;}
 
return 255*pow((n-80)/800,.5);
 
}

这是 Manuel Kasten 的另一作品:

生成这张图片的代码很有意思:函数依靠 static 变量来控制绘画的进程,完全没有用到 i 和 j 这两个参数!

unsigned char RD(int i,int j){
 
static double k;k+=rand()/1./RAND_MAX;int l=k;l%=512;return l>255?511-l:l;
 
}
 

 
unsigned char GR(int i,int j){
 
static double k;k+=rand()/1./RAND_MAX;int l=k;l%=512;return l>255?511-l:l;
 
}
 

 
unsigned char BL(int i,int j){
 
static double k;k+=rand()/1./RAND_MAX;int l=k;l%=512;return l>255?511-l:l;
 
}

这是来自 githubphagocyte 的作品:

它的代码如下:

unsigned char RD(int i,int j){
 
float s=3./(j+99);
 
float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
 
return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;
 
}
 

 
unsigned char GR(int i,int j){
 
float s=3./(j+99);
 
float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
 
return (int(5*((i+DIM)*s+y))%2+int(5*((DIM*2-i)*s+y))%2)*127;
 
}
 

 
unsigned char BL(int i,int j){
 
float s=3./(j+99);
 
float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
 
return (int(29*((i+DIM)*s+y))%2+int(29*((DIM*2-i)*s+y))%2)*127;
 
}

这是来自 githubphagocyte 的另一个作品:

这是一张使用 diffusion-limited aggregation 模型得到的图片,程序运行起来要耗费不少时间。代码很有意思:巧妙地利用宏定义,打破了函数与函数之间的界限,三段代码的字数限制便能合在一起使用了。

unsigned char RD(int i,int j){
 
#define D DIM
 
#define M m[(x+D+(d==0)-(d==2))%D][(y+D+(d==1)-(d==3))%D]
 
#define R rand()%D
 
#define B m[x][y]
 
return(i+j)?256-(BL(i,j))/2:0;
 
}
 

 
unsigned char GR(int i,int j){
 
#define A static int m[D][D],e,x,y,d,c[4],f,n;if(i+j<1){for(d=D*D;d;d--){m[d%D][d/D]=d%6?0:rand()%2000?1:255;}for(n=1
 
return RD(i,j);
 
}
 

 
unsigned char BL(int i,int j){
 
A;n;n++){x=R;y=R;if(B==1){f=1;for(d=0;d<4;d++){c[d]=M;f=f<c[d]?c[d]:f;}if(f>2){B=f-1;}else{++e%=4;d=e;if(!c[e]){B=0;M=1;}}}}}return m[i][j];
 
}

最后这张图来自 Eric Tressler :

这是由 logistic 映射得到的 Feigenbaum 分岔图。和刚才一样,对应的代码也巧妙地利用了宏定义来节省字符:

unsigned char RD(int i,int j){
 
#define A float a=0,b,k,r,x
 
#define B int e,o
 
#define C(x) x>255?255:x
 
#define R return
 
#define D DIM
 
R BL(i,j)*(D-i)/D;
 
}
 

 
unsigned char GR(int i,int j){
 
#define E DM1
 
#define F static float
 
#define G for(
 
#define H r=a*1.6/D+2.4;x=1.0001*b/D
 
R BL(i,j)*(D-j/2)/D;
 
}
 

 
unsigned char BL(int i,int j){
 
F c[D][D];if(i+j<1){A;B;G;a<D;a+=0.1){G b=0;b<D;b++){H;G k=0;k<D;k++){x=r*x*(1-x);if(k>D/2){e=a;o=(E*x);c[e][o]+=0.01;}}}}}R C(c[j][i])*i/D;
 
}

下面是 高城 的分享,伯乐在线已征得许可

我在这里提供我见识到的三个精彩算法的解析,强烈地推荐给初学的算法爱好者,它们可能会令你眼界大开,同时坚定你在算法大道上勇往直前的信念。

#3. 二进制是人类的好朋友,在线的树的最近公共祖先(LCA)算法:

利用数的二进制表示可以产生很多加速算法,online-LCA是其中之一。许多算法的加速是对数率的,就是利用了数的二进制表示。
首先定义二维数组:prede[N+1][B+1], N表示树的结点的数量,结点以数字1到N代指,B满足条件:2^(B)>=N
令fa[i]表示结点i的父结点,那么prede[i][b]的含义是:

prede[i][0] = fa[i];
 
prede[i][b] = prede[prede[i][b-1]][b-1]; // b >= 1

也就是说,prede[i][b]指的是从结点i往上走2^(b)步,所到达的结点。如果走到了尽头,就令prede[i][b]为0。
我们只需要O(NlogN)的复杂度,就可以完成prede的初始化。此外,我们还需要预处理出所有结点的高度,也就是depth[i],定义为:

depth[root] = 0;
 
depth[i] = depth[fa[i]] + 1;

当遇到询问LCA(x, y),我们只需要采取如下行动,就可以O(logN)的代价获得答案:

int lca(int x, int y) {
 
     if (depth[x] > depth[y]) swap(x, y);
 
     for(int i = B; i >= 0; i --){
 
         //令x和y高度一致
 
         if (depth[prede[y][i]] >= depth[x]) y = prede[y][i];
 
     }
 
     //注意此时有可能出现x == y,那么LCA(x,y) == x,下方的for
 
     //就不起作用了。
 
     for(int i = B; i >= 0; i --){
 
        //如果prede[x][i]和prede[y][i]不相同,说明这两者的高度
 
        //都大于所求的LCA(x,y),也就是在LCA(x,y)的下方,此时令
 
        //x和y一同往根部以2^(i)的步数爬升
 
        if (prede[x][i] != prede[y][i]) x = prede[x][i], y = prede[y][i];
 
     }
 
     if (x == y) return x;   //此时LCA(x,y) = x
 
     return prede[x][0];     //此时x和y有共同的父结点
 
}

上述代码的精髓在于两个for(int i = B; i >= 0; i –),这里利用了数的二进制表示。可以证明,对于任何严格小于2^(B+1)的非负整数t,下面的代码运行之后可以令a == t,

int a = 0;   
 
for(int i = B; i >= 0; i --){
 
     if(a + (1<<i) <= t) a += (1<<i);
 
}

#2. 集合之交,树状数组,动态更改、查询数组前缀和算法。

实现树状数组所需的代码极为简易,实际上它是一棵残缺的线段树,它可以实现一部分线段树的功能(但凡可以化为区间求和的问题基本上都能解决),但是毕竟不如线段树功能完整,有兴趣的读者应该学习一下线段树的知识。

问题描述:利用预处理的前缀和数组pre[N + 1],我们可以O(1)的代价对静态的数组A[N + 1]求取区间和:

pre[i] = A[0] + A[1] + A[2] + … + A[i];

A[a] + A[a+1] + A[a+2] + … + A[b] = pre[b] – pre[a-1];

但是当需要对数组A进行动态的更改时,上述代码就失效了。我们需要一种算法,可以动态地更改以及查询前缀和数组pre[N+1]。下面首先展示树状数组的代码,然后解释其数学原理,它的插入和查询的代价都是O(logN):

int Count[BiggestN+1], N; //使用前令Count所有元素为0,规定A[0]没有数
 
                          //据,也就是说数据从A[1]开始存,pre[0]总为零
 

 
//实现功能A[i] += add
 
void insert(int i, int add)
 
{
 
    while( i <= N )
 
    {
 
        Count[i] += add;
 
        i += i&(-i);
 
    }
 
}
 
//返回pre[i]的值
 
int query(int i)
 
{
 
    int num = 0;
 
    while( i > 0 )
 
    {
 
        num += Count[i];
 
        i -= i&(-i);
 
    }
 
    return num;
 
}

算法中最关键的语句是位操作i&(-i),读者在稿纸上算一算就可以知道:

i -= i&(-i)的功能是令i的最低的非0位变为0;

i += i&(-i)的功能是令i的最低的非0位变为0,并往更高一位进一。
理解树状数组的行为,需要构造两个集合:

Define lowbit(i) = i&(-i);

up(a) = {a, a1, a2, …}, ai = a(i-1) + lowbit(a(i-1));

down(a) = {a, a1, a2, …, 0}, ai = a(i-1) – lowbit(a(i-1));

可以证明,对于任何a <= b的正整数对(a,b),up(a)和down(b)的交集都有且仅有一个元素。对这个定理进行含糊的说明是很容易的,a == b的情况不必考虑,a < b时,总有一个最大的i,使得b的第i位大于a的第i位(也就是b的第i位是1,而a的第i位是0),那么对b产生down(b),对a产生up(a),它们的唯一交集就是(1<<i)。注意这里讨论的第i位的i是从0开始索引的。读者可以在稿纸上找若干数对进行实验来加深印象。
有了上述定理,我们就不难意会insert函数和query函数的作用了。

#1. 机器浮点数的秘密,”巧夺天工”的完美实例,基于标准浮点数的快速开平方倒数算法
这是一个公开的秘密,这是一个所有程序员得以欣赏的智慧之美。她在许多程序员的心目中高居“最美代码”的第一位,所有溢美之词都无法表达他们所感受到的震撼。
一定会有许多人想在这里贴这段代码,少年,来我这里,我帮你揭开她神秘的面纱。

公式太多,贴图讲解。


有没有一段代码,让你觉得人类的智慧也可以璀璨无比?,首发于博客 - 伯乐在线


以上内容由IFTTT自动发布,原文地址:http://blog.jobbole.com/98471/

Related Articles

Quote Of The Day