No Such Blog or Diary
テンプレートで
覆面算の計算で各桁をテンプレートで生成してやることにした.これでソースは見やすくなった.しかも,全部を展開してあった前のコードより若干速いらしい.ちなみに,関数テンプレートの部分特化(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): -
覆面算1秒
ということで,16進の覆面算プログラムを作業の合間に組んでみた.8重の 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): -
今度の課題は覆面算
- 2005-06-29 (Wed)
- 一般
今週の課題は YYYY×ZZZZ=WWWWWWWW となるように,十六進の数字を重なり無く割り振れと.下から作れば簡単なような...
- Comments: 0
- TrackBack (Close): -
Bitonic Sort in Haskell
比較の仕方がデータによらないソートである Bitonic Sort を Haskell で書いてみた.要素数 2^n 限定.だけ.
import System.Random randInt :: IO (Int) randInt = getStdRandom (randomR (0,1000)) randInts n = randInts' n [] where randInts' n xs = if n == 0 then return xs else randInt >>= (\x -> randInts' (n-1) (x:xs)) bimerge xs ys 1 dir = unzip (zipWith (\x y -> if (x < y) == dir then (x,y) else (y,x)) xs ys) bimerge xs ys n dir = (xxs++xys, yxs++yys) where (xs', ys') = unzip (zipWith (\x y -> if (x < y) == dir then (x,y) else (y,x)) xs ys) n2 = (n `div` 2) (xxs, xys) = bimerge (take n2 xs') (drop n2 xs') n2 dir (yxs, yys) = bimerge (take n2 ys') (drop n2 ys') n2 dir bisort xs = bisort' xs (length xs) True where bisort' zs 1 dir = zs bisort' zs n dir = xs'' ++ ys'' where n2 = (n `div` 2) xs' = bisort' (take n2 zs) n2 dir ys' = bisort' (drop n2 zs) n2 (not dir) (xs'', ys'') = bimerge xs' ys' n2 dir -- randInts 1024 >>= (\x -> print (bisort x)) -- randInts 1024 >>= (\xs -> print (snd (foldl (\(x, f) y -> (y, and [f, (x <= y)])) (-1, True) (bisort xs))))
- Comments: 0
- TrackBack (Close): -
四捨五入できない
- 2005-06-27 (Mon)
- 一般
ふと気が付けば今日は誕生日.四捨五入すると30歳になってしまう歳になってしまった.しゃーねーからケーキでも焼くか.
- Comments: 0
- TrackBack (Close): -