你見過最美的程序是什麼？

01-22

程序語言不限，程序作用不限。可以是程序運行結果的美；可以是程序本身的邏輯優美；可以是程序所引發的現實生活中的優美。注意：不一定是自己寫過的，見過的即可！期待在這裡看到最美的程序：）

安利一下我大 Shadertoy！上面都是搞 GE、Shader 和演算法的大神們！

200 行代碼模擬出海平面：https://www.shadertoy.com/view/Ms2SD1

130 行代碼模擬出雲層：https://www.shadertoy.com/view/XslGRr

300 行代碼模擬出複雜的雪山：https://www.shadertoy.com/view/MdX3Rr

對顯卡性能有信心的可以點開上面的鏈接測試 fps ：）

裡面很多還是可以轉化為產品的（OpenGL，WebGL，OpenGL ES）

跳動的心：Shadertoy BETA

例如上面這個我把它移植到 OpenGL ES 了

float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F;

x2 = number * 0.5F; y = number; i = * ( long * ) y;// evil floating point bit level hacking（對浮點數的邪惡位級hack） i = 0x5f3759df - ( i &>&> 1 );// what the fuck?（這他媽的是怎麼回事？） y = * ( float * ) i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration （第一次牛頓迭代） // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed（第二次迭代，可以刪除） return y; }

平方根倒數速演算法

以及下面是xkcd的提到它的漫畫以及科學松鼠會對它的解釋

0x5f375a86來自一個傳奇演算法，出自John Carmack開發的《雷神之錘3》的3D引擎。這個引擎的源代碼里包括一個反平方倒數的演算法，其速度要比標準的牛頓迭代法快上幾十倍，而其中的關鍵是一行神秘的代碼和一個莫名其妙的數字：[ i = 0x5f3759df - ( i &>&> 1 ); // what the fuck? ] 。沒有人知道Carmack是怎麼發現這個數字的。普度大學的數學家Lomont覺得很好玩，於是自己從理論推導出了一個可能的最佳值0x5f375a86，和Carmack的接近但略微好一丁點，他很懷疑Carmack其實是用試錯法找到原來的數的……（答者注，其實這傢伙先用理論推導出來一個0x5f37642f，結果試了一下發現還不如原本的0x5f3759df精確，怒，暴力窮舉出來的0x5f375a86……）於是Lomont寫了一篇文章發表了這個演算法，稱之為「Fast inverse square root」。天知道還有多少這樣的神奇演算法藏在各種商業軟體里，不為人知。

—— O. Danvy A. Filinski, Representing Control: A Study on the CPS Transformation, 1992

—— Eugene Kohibecker, Daniel P. Friedman, Matthias Felleisen, Bruce Dubs, Hygienic Macro Expansion, LFP "86 Proceedings of the 1986 ACM conference on LISP and functional programming, pp. 151-161

Andrew Kensler寫了一個可列印在名片背後的程序：

#include & // card &> aek.ppm #include & #include & typedef int i;typedef float f;struct v{ f x,y,z;v operator+(v r){return v(x+r.x ,y+r.y,z+r.z);}v operator*(f r){return v(x*r,y*r,z*r);}f operator%(v r){return x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r ){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r. y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v operator!(){return*this*(1/sqrt(*this%* this));}};i G[]={247570,280596,280600, 249748,18578,18577,231184,16,16};f R(){ return(f)rand()/RAND_MAX;}i T(v o,v d,f t,vn){t=1e9;i m=0;f p=-o.z/d.z;if(.01 &0 ){f s=-b-sqrt(q);if(s&.01)t=s,n=!( p+d*t),m=2;}}return m;}v S(v o,v d){f t ;v n;i m=T(o,d,t,n);if(!m)return v(.7, .6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R( ),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l% n;if(b&<0||T(h,l,t,n))b=0;f p=pow(l%r*(b &>0),99);if(m1){h=h*.2;return((i)(ceil( h.x)+ceil(h.y))1?v(3,1,1):v(3,3,3))*(b *.2+.1);}return v(p,p,p)+S(h,r)*.5;}i main(){printf("P6 512 512 255 ");v g=!v (-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a )*.002,c=(a+b)*-256+g;for(i y=512;y--;) for(i x=512;x--;){v p(13,13,13);for(i r =64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)* 99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b *(y+R())+c)*16))*3.5+p;}printf("%c%c%c" ,(i)p.x,(i)p.y,(i)p.z);}}

g++ -O3 -o card card.cpp ./card &> card.ppm

就會輸出一個card.ppm的圖像文件，aek是作者的名字縮寫：

出處：Code

解讀：Raytracing

N皇后問題，互不相同解個數：（c++ 11）

int totalNQueens(int n) { int upperlim = (1 &<&< n) - 1, sum = 0; std::function& dfs = [](int row, int l, int r) { if (row == upperlim) { ++sum; return; } for (int cur = upperlim (~(row|l|r)), pos = 0; cur; dfs(row+pos, (l+pos)&<&<1, (r+pos)&>&>1)) { pos = cur (-cur); cur -= pos; } }; dfs(0, 0, 0); return sum; }

Ken Thompson，UNIX的鼻祖、C語言的創始人之一，他寫過一個自已複製自已的C程序，堪稱是歷史上最好的C語言程序。

#include & char s[] = { " ", "0", " ", "}", ";", " ", " ", "m", "a", "i", "n", "(", ")", " ", "{", " ", " ", "i", "n", "t", " ", "i", ";", " ", " ", " ", "p", "r", "i", "n", "t", "f", "(", ""","c", "h", "a", "r", " ", "\", "t", "s", "[", "]", " ", "=", " ", "{", "\", "n", """, ")",";", " ", " ", "f", "o", "r", "(", "i", "=", "0", ";", "s", "[", "i", "]", ";", "i", "+","+", ")", " ", " ", " ", "p", "r", "i", "n", "t", "f", "(", """, "\", "r", "%", "d",",", "\", "n", """, ",", "s", "[", "i", "]", ")", ";", " ", " ", "p", "r", "i", "n", "t","f", "(", """, "%", "s", """, ",", "s", ")", ";", " ", "}", 0 }; main() { int i; printf("char s[] = { "); for(i=0; s[i]; i++) printf(" %d, ",s[i]); printf("%s",s); }

自己列印自己的函數：

C語言版：

#include & char* recurse="#include &%cchar* recurse=%c%s%c;%cint main(){printf(recurse,10,34,recurse,34,10,10);}%c"; int main(){printf(recurse,10,34,recurse,34,10,10);}

Python版：

print (lambda s: s.replace(chr(042),chr(047))%s)("print (lambda s: s.replace(chr(042), chr(047))%%s)("%s")")

剛才用Python寫了一個CRT（中國剩餘定理），簡直把自己美哭了（要不要這麼矯情）……

Never calculate, just define. Think functional.

ruby on rails and erlang

在C語言三劍客中得一本書看到了IOCCC這個賽事。中文名字叫C語言代碼混亂大賽。關於如何混亂的，不妨先看看下面的獲獎作品：（來源於第21屆比賽）

最佳短程序獎：韓國 Seonghoon Kang

最具隱蔽性獎：美國 Don Yang

最有用混亂代碼獎：中國侯啟明（候大神也是20屆IOCCC的獲獎者之一）

銅獎作品最佳Cocoa應用：美國 Daniel Vik

看完這些，相信你也懂了一些。然後，最關鍵的是：你還覺得你會C語言么？？？

代碼詳見 The International Obfuscated C Code Contest 圖片來源於網路，如有版權問題請聯繫我。

我可以說我見過最牛逼的是我的世界Minecraft 裡面有人用在遊戲里的紅石系統做的計算器么？

http://m.ku6.com/show/YIElC-0UADEI7eF5awPTPA...html

雖然不是用代碼寫出來的，但是我覺得很震撼了。

正經的代碼我倒是沒有,但有一個跟 Dynamic Programming 相關的演算法思維我覺得很美,我也不知道國內怎麼翻譯的,但我們課上叫 "Pruning Method". 往常寫 Dynamic Programming 都是先寫一個遞歸(Recursion),然後再保留核心部分並改寫外環為循環模式. 比較典型的就是每本書都會教的 Fibonacci Binomial Coefficient. 但在實際應用中,有很多題目用遞歸推 Dynamic 並不是那麼容易,比如 LIS (The Longest Increasing Sub-sequence), 這題說實話寫遞歸都有些困難(對我來說),因為你要不斷 strengthen your induction (我們教授經常說的,直白點說就是不斷試錯再不斷提出新的假設).

Pruning Method 的魅力在於你並不需要依賴遞歸,而且在問題多樣化的 Dynamic Programming 應用領域,它能給你一個相對來說按部就班的解決方案:

1. 首先確定你 output 的表達形式.

2. 基於你 output 的表達形式用二叉樹(n叉樹都是可以的,但二叉樹可以說能涵蓋大多數問題了)列舉出所有可能的答案.

3. 在樹結構的每一層,根據你的觀察(我知道你可能想吐槽這句),去除掉那些不可能成為最終最優解的node. 在大多數情況下,在第 n 層, $2^{n}$ 個nodes可以被減少到 n 或者 2n 個,這效率的提升就非常可觀了.

4. Traverse 最後一層找出最優解.

我給道我們作業里的一道題吧:

在 x-y 平面上的原點處有兩個郵遞員,另有 n 個點 $p_1 p_2 p_3 ... p_n$ 散布在平面的其他位置,而且一個點一個坐標,沒有重疊. 兩位郵遞員要合作把郵件送到每一個點,並且若任意一個郵遞員到 $p_j$ 前先到的 $p_i$ 則 $i<j$ . 請給出一個O( $n^2$ )的演算法找出能讓他們加一起走最少路的路徑.