有没有一段代码，让你觉得人类的智慧也可以璀璨无比？
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/
0 评论 :
发表评论