C++の
順列を最後の10個まで求めているのでダブりを防ぐ処理のために遅くなっていますが、ダブりを許せば半分の0.15[sec]ぐらいで求めます。
/* * SendMoreMoney.cpp * * SEND * +MORE * ----- * MONEY * */ #include <stdio.h> #include <string.h> /* memcpy()等で必要 */ #include <time.h> /* clock() */ #include <algorithm> /* next_permutation() */ using namespace std; #define Horner(p,q,r,s,t) (10*(10*(10*(10*(p)+(q))+(r))+(s))+(t)) /* ホーナー法 */ #define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0])) /* 配列の要素数を求めるマクロ */ int main(void) { int pm[]={0,1,2,3,4,5,6,7,8,9}; int sz=ARRAY_SIZE(pm); /* 配列の大きさ */ int bk[8]; /* バックアップ用 */ int s,e,n,d,m,o,r,y; int t1,t2,t3,t4; clock_t st,dt; st=clock(); /* タイマースタート */ memset(bk,0,sizeof(int)*8); do{ /* 先頭8つが前と同じならスキップ */ if(!memcmp(pm,bk,sizeof(int)*8)) continue; s=pm[0],e=pm[1],n=pm[2],d=pm[3],m=pm[4],o=pm[5],r=pm[6],y=pm[7]; if(!(s*m)) continue; /* (s==0||m==0)ならスキップ */ t1=Horner(0,s,e,n,d); t2=Horner(0,m,o,r,e); t3=Horner(m,o,n,e,y); t4=t1+t2; memcpy(bk,pm,sizeof(int)*8); if(t3!=t4) continue; /* チェックを潜り抜けたものだけを出力 */ printf(" %d\n",t1); printf("+%d\n",t2); printf("-----\n"); printf("%d\n",t3); printf("\n"); }while (next_permutation(pm,pm+sz)); dt=clock()-st; /* タイマーストップ */ printf("Runtime : %ld.%03ld [sec]\n",dt/1000,dt%1000); return(0); }
●出力結果
9567 +1085 ----- 10652 Runtime : 0.312 [sec]
参考URL
●BohYoh.com−C/C++ FAQ 順列の生成方法を教えてください。
●SEND MORE MONEY C言語プログラム - rscの日記
●SEND MORE MONEY(3) C言語プログラム - rscの日記
●SEND MORE MONEY JavaScriptプログラム - 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の日記