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

加入极市 专业CV交流群,与 6000+来自腾讯,华为,百度,北大,清华,中科院 等名企名校视觉开发者互动交流!更有机会与 李开复老师 等大牛群内互动!

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流。 关注  极市平台  公众号  , 回复  加群, 立刻申请入群~

本文来自知乎问答,回答均已获作者授权,禁止二次转载

问题:有没有一段代码,让你觉得人类的智慧璀璨无比?

https://www.zhihu.com/question/30262900

知乎高质量回答

一、作者:烧茄子

https://www.zhihu.com/question/30262900/answer/48741026

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 的图片。

  • Tweetable Mathematical Art 链接: https://codegolf.stackexchange.com/questions/35569/t

    weetable-mathematical-art

// 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;

}

二、作者:张博航

https://www.zhihu.com/question/30262900/answer/253192946

分享几个第一次看到就被它的优美深深震撼到的代码:

1、线性求逆元:

for (int i = 2; i < MAXN; i++)

inv[i] = mul(inv[mod%i], mod - mod / i, mod);

仅仅两行代码,就实现了在$O(n)$的时间内求出1到n对模m的逆元有木有!?

2、求最大公因数:

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}

第一次接触到这样的代码时,我的内心是这样的:

wtf???黑人问号.jpg

3、树状数组

对于单点修改区间求和,树状数组可谓达到了时空复杂度的极限,甚至不多用额外一字节存储空间。来看看它的实现:

修改:

void add(int i, int x){

for (;i <= n; i += i & -i)tree[i] += x;

}

查询:

int sum(int i){

int ret = 0;

for(; i; i -= i & -i)ret +=tree[i];

return ret;

}

表示记性不好的我看完一遍也记住了呢。

4、zkw线段树

对于单点修改区间查询的线段树,zkw大神实力教你如何1分钟内码出代码:

修改:

void set(int x, int value){

val[x += treeLen] = value;

while (x >>= 1)pushUp(x);

}

查询:

int query(int l,int r){

int ret = 0;

for (l += treeLen - 1, r += treeLen +1; l ^ r ^ 1; l >>= 1, r >>= 1){

if (~l & 1)ret = min(ret, val[l^1]);

if (r & 1)ret = min(ret, val[r ^ 1]);

}

return ret;

}

以上都是一些十分基础但真的让你赞不绝口的算法和数据结构。还有一些稍微复杂一些的栗子,由于手机码代码太不方便了,就以后再更吧。(如果有笔误打错的地方欢迎指正哈)

5、后缀数组的DC3算法,反正学完它的一瞬间我是明白了,天才和普通人的智商差距简直比人和狗还大啊。。。

6、快速傅里叶变换的数论版本(即NTT):学完后有种想去数学系的冲动(还好后来冷静下来了)。费马素数群的性质居然和复数完美吻合,不得不说是一种奇迹啊。

7、主席树:这是fotile巨佬考场上发明这种数据结构,用于在$O(log n)$的时间复杂度内解决序列区间第k大问题,以及区间内元素的排名。个人感觉他比划分树的设计巧妙多了,有一种自然的美感。

8、Pollard因数分解算法:如果你真的把关于时间复杂度的证明一步步看完后,相信你会有一种豁然开朗的感觉。这个算法真正高的地方在于把生日悖论和递推式循环节巧妙的结合在一起,最后运用递推方程主定理的理论,使得时间复杂度达到了看似不可能的期望$n^0.25$的数量级。

其实现在感觉一切和数据结构或数学有关的算法都是非常优美的,前者在于设计的精巧性,后者在于证明的环环相扣,达到引人入胜的效果。

-End-

CV细分方向交流群

添加极市小助手微信 (ID : cv-mart) ,备注: 研究方向-姓名-学校/公司-城市 (如:目标检测-小极-北大-深圳),即可申请加入 目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割等极市技术交流群 (已经添加小助手的好友直接私信) ,更有每月 大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流 一起来让思想之光照的更远吧~

△长按添加极市小助手

△长按关注极市平台

觉得有用麻烦给个在看啦~   

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章