以前、Cで作ったSEND MORE MONEY のプログラムをJavaScriptに翻訳してみました。順列生成アルゴリズムの genperm.js は、元のCのプログラムの関数の定義と変数宣言をちょっと変更するだけでそのまま使えるようです。
でも、よく考えたら、そもそも、速いCから遅いJavaScriptに翻訳する意味があるのかな。(^_^;
ちなみに、ホーナー法(?)もどきは別に使わなくてもよかったのですが、send more moneyをソース中に並べたかっただけです。(^_^;
●genperm.js
function rev_sort(p, from, to) { var i, j, tmp; // 以下は、Cと同じ } function next_perm(p, n, r) { var i, j, k, tmp; // 以下は、Cと同じ }
以上2つの関数を1つにまとめると、以下の通りです。
function next_perm(p, n, r) { var i, j, k, tmp; if(r<=0 || n<r) return(false); for(i=r+1; i<=n-1; i++) for(j=i; j>=r+1 && p[j-1]< p[j]; j--) tmp=p[j], p[j]=p[j-1], p[j-1]=tmp; for(i=n-1; i> 0 && p[i-1]>=p[i]; i--); if(!i) return(false); for(j=n-1; j> i && p[i-1]>=p[j]; j--); tmp=p[i-1], p[i-1]=p[j], p[j]=tmp; for(k=0; k<=(n-i-1)/2; k++) tmp=p[i+k], p[i+k]=p[n-k-1], p[n-k-1]=tmp; return(true); }
●SendMoreMoney.html
<!-- /* * SendMoreMoney.html * * SEND * +MORE * ----- * MONEY * */ //--> <html> <head> <title>SendMoreMoney.html</title> <script type="text/javascript" src="genperm.js"></script> <script type="text/javascript"> function Hn(p,q,r,s,t) { // 10000*p+1000*q+100*r+10*s+t return (10*(10*(10*(10*p+q)+r)+s)+t); } </script> </head> <body> <script type="text/javascript"> var p=[0,1,2,3,4,5,6,7,8,9]; var s,e,n,d,m,o,r,y; var send,more,money; var dt=(new Date()).getTime(); // タイマースタート do{ s=p[0],e=p[1],n=p[2],d=p[3],m=p[4],o=p[5],r=p[6],y=p[7]; if(!(s*m)) continue; // (s==0||m==0)ならスキップ send =Hn(0,s,e,n,d); more =Hn(0,m,o,r,e); money=Hn(m,o,n,e,y); if(send+more!=money) continue; // チェックを潜り抜けたものだけを出力 document.write("<pre>"); document.write(" ",send,"<br />"); // 半角スペース document.write("+",more,"<br />"); document.write("-----<br />"); document.write(money,"<br />"); document.write("</pre>"); }while (next_perm(p,10,8) ); dt=(new Date()).getTime()-dt; // タイマーストップ document.write("Runtime : ",dt/1000.0, "[sec]<br />"); </script> </body> </html>
●実行結果
9567 +1085 ----- 10652 Runtime : 0.769[sec]
※参考URL
http://d.hatena.ne.jp/rsc96074/20110422/1303424364
●よしいずの雑記帳 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
ちなみに、Hn()関数を次のものに変えると、ちょっと遅くなります。(^_^;
function Hn(coeff,x) // Horner method { var len=coeff.length; var res=0; for(var i=0; i<len; i++) res=res*x+coeff[i]; return(res); } …(略)… h1=Hn( [s,e,n,d],10); h2=Hn( [m,o,r,e],10); h3=Hn([m,o,n,e,y],10); …(略)…
●実行結果
9567 +1085 ------- 10652 Runtime : 1.637[sec]
※参考URL
●SEND MORE MONEY C言語プログラム - rscの日記
●SEND MORE MONEY(2) C++ - rscの日記
●SEND MORE MONEY(3) C言語プログラム - rscの日記
●SEND MORE MONEY in Java - rscの日記
●SEND MORE MONEY in Python - rscの日記
●SEND MORE MONEY in Ruby - rscの日記
●SEND MORE MONEY in Python(2) - rscの日記
●SEND MORE MONEY in Ruby(2) - rscの日記
●SEND MORE MONEY in Python(3) - rscの日記