- 论坛徽章:
- 7
|
本帖最后由 rubyish 于 2017-09-06 00:36 编辑
回复 19# 523066680
3Q ~~
Bidui zhihou faxian zhiyou yichu chayi
sum( t1*log(t1) ... tn*log(tn) ) / n - f(2*log(2))
- grep { $amount += $_ * log($_) } values %hash;
- if ( exists $ref->{$e} ) { $amount -= 2 * log(2) }
复制代码
gaicheng zhege zhihou keyi dadao AVE = 5.2X
- sum( t1*log(t1) ... tn*log(tn) ) - f(2*log(2))
复制代码
AVE: 5.27
- 1 1
- 2 13
- 3 60
- 4 548
- 5 2440
- 6 1871
- 7 106
- 8 1
- ----------------
- COUNT = 26575
- TEST = 5040
- AVE = 5.272817
- real 1m24.631s
复制代码
AVE: 5.23
- 1 1
- 2 7
- 3 70
- 4 611
- 5 2468
- 6 1782
- 7 100
- 8 1
- ----------------
- COUNT = 26409
- TEST = 5040
- AVE = 5.239881
- real 4m36.666s
复制代码
- // gcc -Wall -march=native -Ofast -o bull bull.c
- # include <stdio.h>
- # include <string.h>
- # include <math.h>
- # define OK 0x40
- # define get_a(A) A >> 4
- # define get_b(A) 0xF & A
- # define copy(A, B) memcpy (A, B, 4)
- # define move1(A) ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
- # define toInt(N) 1000 * N[0] + 100 * N[1] + 10 * N[2] + N[3];
- # define INIT(A, B) for (int i = 0; i < 5040; i++) { A[i] = i; B[i] = 1; }
- # define AB(A, B) XAYB[A][B]
- # define F2log2 1.38629436111989
- # define TEST 5040
- typedef char kar;
- typedef double dub;
- typedef void voi;
- kar XAYB[5040][5040];
- int A_and_B[961]; // LOOK: sub genB
- kar SPLIT[5040][4]; // SPLIT[0] = [ 0, 1, 2, 3 ]
- int TOTO[5040];
- int MAYBE[5040]; // [ 0 .. 5039 ]
- int hasMAYBE[5040];
- int INDES[65]; // 4A: 0x40 == 64
- int COUNT[16]; //
- dub INFO[2000];
- int LEN_MAYBE; // @MAYBE
- voi init (voi);
- voi test (voi);
- voi genTOTO (int);
- voi genIndes (voi);
- voi genB (voi);
- voi genAB (voi);
- voi rehashMaybe (int, int);
- int gimme (int);
- /* ____________________ MAIN ____________________ */
- int main (){
- init ();
- test ();
- }
- /* _____________________ SUB _____________________ */
- voi test () {
- fprintf (stderr, "\rtest ");
- for (int v = 0; v < TEST; v++) {
- if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
- // printf ("%d\n", v + 1);
- INIT (MAYBE, hasMAYBE);
- int ans = v;
- int gue = 0;
- LEN_MAYBE = 5040;
- // printf ("_ [ %04d ]\n", TOTO[ans]);
- int x;
- for (x = 1; x < 9; x++) {
- int ab = AB (ans, gue);
- // int a = get_a (ab);
- // int b = get_b (ab);
- // printf ("%d [ %04d ] AB %d %d\n", x, TOTO[gue], a, b);
- if (ab == OK) break;
- rehashMaybe (gue, ab);
- gue = gimme (x);
- // gue = MAYBE[0]; /* NAIVE: FAST */
- }
- COUNT[x]++;
- }
- int ave = 0;
- int tot = 0;
- puts ("FINISH");
- for (int i = 1; i < 15; i++) {
- if (!COUNT[i]) continue;
- printf ("%d\t%d\n", i, COUNT[i]);
- ave += i * COUNT[i];
- tot += COUNT[i];
- }
- if (tot != TEST) puts ("ERROR");
- puts ("----------------");
- printf ("COUNT = %d\n", ave);
- printf ("TEST = %d\n", TEST);
- printf ("AVE = %f\n", ave / (dub)TEST);
- } /* test */
- voi init () {
- fprintf (stderr, "init..");
- genTOTO (0);
- genB ();
- genAB ();
- genIndes ();
- for (int i = 0; i < 2000; i++) INFO[i] = i * log (i);
- }
- voi genTOTO (int lev){
- static kar num[4];
- static int I = 0;
- static int has[10];
- if (lev == 4) {
- int n = toInt (num);
- TOTO[I] = n;
- copy (SPLIT[I], num);
- I++;
- return;
- }
- for (int i = 0; i <= 9; i++) {
- if (has[i]) continue;
- has[i] = 1;
- num[lev] = i;
- genTOTO (lev + 1);
- has[i] = 0;
- }
- } /* genTOTO */
- voi genB (){
- // 0b1111000000 => bit(1): 9876, val = 960
- // 0123: 0b001111
- // 0153: 0b101011
- // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
- for (int i = 0; i < 961; i++) {
- int count = 0;
- for (int j = 0; j < 10; j++) {
- if (i & (1 << j)) count++;
- if (count > 4) break;
- }
- A_and_B[i] = count > 4 ? 0 : count;
- }
- }
- voi genAB (){
- for (int i = 0; i < 5040; i++) {
- kar *cha = SPLIT[i];
- int C1 = move1 (cha);
- for (int j = 0; j < 5040; j++) {
- kar *cha2 = SPLIT[j];
- int C2 = move1 (cha2);
- int A = 0;
- for (int k = 0; k < 4; k++)
- if (cha[k] == cha2[k]) A++;
- int B = C1 & C2;
- B = A_and_B[B] - A;
- XAYB[i][j] = (A << 4) | B;
- }
- }
- }
- inline
- voi rehashMaybe (int gue, int ab){
- int I = 0;
- for (int i = 0; i < LEN_MAYBE; i++) {
- if (AB (MAYBE[i], gue) == ab)
- MAYBE[I++] = MAYBE[i];
- else hasMAYBE[MAYBE[i]] = 0;
- }
- LEN_MAYBE = I;
- }
- inline
- int gimme (int lev){
- if (LEN_MAYBE == 1) return MAYBE[0];
- int best = 0;
- dub max = 999999999.0; // BIG NUM
- for (int i = 0; i < 5040; i++) {
- int test[14] = { 0 };
- for (int j = 0; j < LEN_MAYBE; j++) {
- int ab = AB (i, MAYBE[j]);
- int pos = INDES[ab];
- test[pos]++;
- }
- dub toto = 0.0;
- for (int i = 0; i < 14; i++)
- if (test[i]) toto += INFO[test[i]];
- if (hasMAYBE[i]) toto -= F2log2;
- if (max > toto) max = toto, best = i;
- }
- return best;
- } /* gimme */
- voi genIndes (){
- int var[] = { 0, 5, 9, 12, 13 };
- // 0x40 = 4A0B = 64
- // INDES[64] = var[4] + 0 = 13
- for (int a = 0; a <= 4; a++) {
- for (int b = 0; b <= 4; b++) {
- if (a + b > 4) continue;
- int ab = (a << 4) | b;
- int i = var[a] + b;
- INDES[ab] = i;
- // if (a == 3) break; /* NO 3A1B */
- }
- }
- }
复制代码
|
|