2005年06月30日
テンプレートで
覆面算の計算で各桁をテンプレートで生成してやることにした．これでソースは見やすくなった．しかも，全部を展開してあった前のコードより若干速いらしい．ちなみに，関数テンプレートの部分特化(Partial Specialization)は禁止されているようなので，部分的にインスタンス化するため仕方なくクラスを使う羽目になった．ま，次は答えをテンプレートで生成だな．
#include <iostream> using namespace std; template<const int m, const int l> class Calc{ public: inline void calc(unsigned int &x, unsigned int &y, unsigned int (&digits)[m]) { const int n = m/4*3 - l*3; unsigned int d0 = digits[n]; for(int i0 = n; i0 < m; i0++){ digits[n] = digits[i0]; digits[i0] = d0; x = (digits[n]<<(4*(n/3))) | (x&((1<<(4*(n/3)))-1)); unsigned int d1 = digits[n+1]; for(int j0 = n+1; j0 < m; j0++){ digits[n+1] = digits[j0]; digits[j0] = d1; y = (digits[n+1]<<(4*(n/3))) | (y&((1<<(4*(n/3)))-1)); if(n==0 && y >= x) { // omit symmetric pattern digits[j0] = digits[n+1]; continue; } unsigned int z1 = ((x * y) >> (4*(n/3)))& 0xf; int k1 = n+2; for(; k1 < m; k1++) if (digits[k1]==z1) break; if(k1 >= m) { digits[j0] = digits[n+1]; continue; } digits[k1] = digits[n+2]; digits[n+2] = z1; Calc<m,l-1>().calc(x, y, digits); digits[n+2] = digits[k1]; digits[k1] = z1; digits[j0] = digits[n+1]; } digits[n+1] = d1; digits[i0] = digits[n]; } x &=((1<<(4*(n/3)))-1); digits[n] = d0; } }; template<const int m> class Calc<m,0>{ public: inline void calc(unsigned int &x, unsigned int &y, unsigned int (&digits)[m]) { const int n = m/4*3; unsigned int z4 = ((x * y) >> (4*(n/3))); unsigned int ds[m-n]; for(int i = 0; i < (m-n); i++){ ds[i] = digits[i+n]; } int i = 0; for(; i < m-n; i++){ int k4 = i; unsigned int z5 = z4&0xf; z4>>=4; for(; k4 < m-n; k4++) if (ds[k4]==z5) break; if(k4 >= m-n) break; ds[k4] = ds[i]; } if(i >=m-n && ds[m-n-1]!=0){ cout << x << " * " << y << " = " << x*y << endl; cout << y << " * " << x << " = " << x*y << endl; } } }; int main(int argc, char *argv[]) { const int m = 16; cout << hex; unsigned int digits[m]; for(int i = 0; i < m; i++){ digits[i] = i; } unsigned int x = 0; unsigned int y = 0; Calc<m,m/4>().calc(x,y,digits); return 0; }
- Comments: 0
- TrackBack (Close): -
覆面算１秒
ということで，１６進の覆面算プログラムを作業の合間に組んでみた．８重の for ループでぶん回す．裏で別のプログラムが走ってるけど Pen4 2.6C で0.8秒ぐらい．ま，こんなもんか．
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
cout << hex;
unsigned int digits[16];
for(int i = 0; i < 16; i++){
digits[i] = i;
}
unsigned int x = 0;
unsigned int y = 0;
unsigned int d0 = digits[0];
for(int i0 = 0; i0 < 16; i0++){
digits[0] = digits[i0];
digits[i0] = d0;
x = digits[0];
unsigned int d1 = digits[1];
for(int j0 = 1; j0 < 16; j0++){
digits[1] = digits[j0];
digits[j0] = d1;
y = digits[1];
if(y >= x) { // omit symmetric pattern
digits[j0] = digits[1];
continue;
}
unsigned int z1 = (x * y) & 0xf;
int k1 = 2;
for(; k1 < 16; k1++) if (digits[k1]==z1) break;
if(k1 >= 16) {
digits[j0] = digits[1];
continue;
}
digits[k1] = digits[2];
digits[2] = z1;
unsigned int d3 = digits[3];
for(int i1 = 3; i1 < 16; i1++){
digits[3] = digits[i1];
digits[i1] = d3;
x = (digits[3]<<4) | (x&0xf);
unsigned int d4 = digits[4];
for(int j1 = 4; j1 < 16; j1++){
digits[4] = digits[j1];
digits[j1] = d4;
y = (digits[4]<<4) | (y&0xf);
unsigned int z2 = ((x * y)>>4) & 0xf;
int k2 = 5;
for(; k2 < 16; k2++) if (digits[k2]==z2) break;
if(k2 >= 16) {
digits[j1] = digits[4];
continue;
}
digits[k2] = digits[5];
digits[5] = z2;
unsigned int d6 = digits[6];
for(int i2 = 6; i2 < 16; i2++){
digits[6] = digits[i2];
digits[i2] = d6;
x = (digits[6]<<8) | (x&0xff);
unsigned int d7 = digits[7];
for(int j2 = 7; j2 < 16; j2++){
digits[7] = digits[j2];
digits[j2] = d7;
y = (digits[7]<<8) | (y&0xff);
unsigned int z3 = ((x * y)>>8)&0xf;
int k3 = 8;
for(; k3 < 16; k3++) if (digits[k3]==z3) break;
if(k3 >= 16) {
digits[j2] = digits[7];
continue;
}
digits[k3] = digits[8];
digits[8] = z3;
unsigned int d9 = digits[9];
for(int i3 = 9; i3 < 16; i3++){
digits[9] = digits[i3];
digits[i3] = d9;
x = (digits[9]<<12) | (x&0xfff);
unsigned int d10 = digits[10];
for(int j3 = 10; j3 < 16; j3++){
digits[10] = digits[j3];
digits[j3] = d10;
y = (digits[10]<<12) | (y&0xfff);
unsigned int z4 = ((x * y) >>12)&0xfffff;
unsigned int ds[5];
for(int i = 0; i < 5; i++){
ds[i] = digits[i+11];
}
int i = 0;
for(; i < 5; i++){
int k4 = i;
unsigned int z5 = z4&0xf;
z4>>=4;
for(; k4 < 5; k4++) if (ds[k4]==z5) break;
if(k4 >= 5) break;
ds[k4] = ds[i];
}
if(i >= 5 && ds[4]!=0){
cout << x << " * " << y << " = " << x*y << endl;
cout << y << " * " << x << " = " << x*y << endl;
}
digits[j3] = digits[10];
}
digits[10] = d10;
digits[i3] = digits[9];
}
x &=0xfff;
digits[9] = d9;
digits[8] = digits[k3];
digits[k3] = z3;
digits[j2] = digits[7];
}
digits[7] = d7;
digits[i2] = digits[6];
}
x &=0xff;
digits[6] = d6;
digits[5] = digits[k2];
digits[k2] = z2;
digits[j1] = digits[4];
}
digits[4] = d4;
digits[i1] = digits[3];
}
x &=0xf;
digits[3] = d3;
digits[2] = digits[k1];
digits[k1] = z1;
digits[j0] = digits[1];
}
digits[1] = d1;
digits[i0] = digits[0];
}
}
なげぇなぁ．
- Comments: 0
- TrackBack (Close): -