2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение23.11.2014, 04:14 


22/11/14

43
whitefox в сообщении #934218 писал(а):
Все числа $\Phi(m),\gcd(ab)$ являются константами и вычислены заранее.

Хочется также отметить, что и индексные множества, по которым ведется суммирование, тоже вычисляются заранее.

-- 23.11.2014, 04:20 --

whitefox в сообщении #934630 писал(а):
Также должно быть:$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение23.11.2014, 19:35 


22/11/14

43
whitefox в сообщении #934218 писал(а):
Если поменять местами числа $a$ и $b$, то изменение числа Делакорта вычисляется по формуле:$$\Delta D=A-B-2C_x-2C_y$$

Поменяем местами два числа: тогда левая часть поменяет знак, а в правой не изменит знак только $B$. Сложим почленно 2 уравнения и получим:$$\/0=-2*B$. Впечатляет.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение23.11.2014, 19:57 


16/08/05
1146
Помогите найти ошибку на примере случайного квадрата $5\times 5$

(квадрат)

Код:
X=
(1,20,6,23,2),(18,21,24,11,16),(7,10,17,3,9),(4,13,5,22,19),(25,14,12,15,8)

DN= 4697

PsiX=
[75, 72, 150, 152, 300, 168, 420, 352, 324, 240, 880, 384, 468, 252, 360, 512, 1088, 432, 1368, 640, 1260, 1100, 2530, 960, 2500]

PsiY=
[75, 72, 138, 152, 500, 120, 294, 256, 378, 400, 330, 288, 468, 336, 600, 128, 544, 324, 1368, 800, 252, 440, 1518, 768, 2500]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

dDNmin[11,16]= -117
dDNmax[1,25]= 15232
?
? dDN
%28 =
[    0    -4   60   90  1536   112  510  462  742 1292  1620  826  952  748 2020   942 2410 1008 5682 3450  3712 3308  9580 4150 15232]

[   -4     0    9   24   927    88  383  340  423  880  1681  632  595  480 1341  1140 2223  824 4127 2556  3999 3200  8187 3400 11947]

[   60     9    0   23   592    93  368  251  216  565  2056  447  352  189  864  1431 2396  657 3100 1843  4800 3337  7664 2919  9648]

[   90    24   23    0   221   164  625  376  153  268  2879  512  449   56  419  2088 3129  676 2697 1376  5853 3928  8081 2688  8105]

[ 1536   927  592  221     0  1531 1844  973  316  -65  5320 1361 1120   35   40  4025 5136 1231 3000 1005  8896 5775 10000 2905  7680]

[  112    88   93  164  1531     0  103  120  567 1280   549  372  503  584 1881   344 1063  576 4051 2856  2079 1864  6131 3132 11967]

[  510   383  368  625  1844   103    0   61  496 1467   628   61  108  511 1672   577  832  299 2712 2469  2716 1863  4948 2581  9468]

[  462   340  251  376   973   120   61    0  145  776  1047  -24  -87   68  783   960 1021   88 1489 1376  3085 1876  4197 1824  6513]

[  742   423  216  153   316   567  496  145    0  279  2340  321  164  -45  312  2013 2200  495 1264  881  5076 3023  5084 1809  5220]

[ 1292   880  565  268   -65  1280 1467  776  279    0  4177 1036  915  128   25  3400 3931  992 1655  600  7095 4416  6735 1940  4515]

[ 1620  1681 2056 2879  5320   549  628 1047 2340 4177     0  267  976 1869 4176  -117  272  625 4240 4647   888 1045  4232 3387 11960]

[  826   632  447  512  1361   372   61  -24  321 1036   267    0   37  248 1179   408  149  -12 1469 1552  1413  760  2269 1440  6333]

[  952   595  352  449  1120   503  108  -87  164  915   976   37    0  215 1000  1285  800  235  936 1425  3008 1715  2512 1565  4960]

[  748   480  189   56    35   584  511   68  -45  128  1869  248  215    0  177  1860 1635  328  395  428  4095 2176  2775  968  2735]

[ 2020  1341  864  419    40  1881 1672  783  312   25  4176 1179 1000  177    0  3723 3620 1005  860  255  6840 3965  4720 1395  2360]

[  942  1140 1431 2088  4025   344  577  960 2013 3400  -117  408 1285 1860 3723     0  369  824 3933 4160   345  628  2985 2960 10013]

[ 2410  2223 2396 3129  5136  1063  832 1021 2200 3931   272  149  800 1635 3620   369    0  347 2320 3573   976  455  1480 2125  7320]

[ 1008   824  657  676  1231   576  299   88  495  992   625  -12  235  328 1005   824  347    0  415  936  1635  584   575  540  2835]

[ 5682  4127 3100 2697  3000  4051 2712 1489 1264 1655  4240 1469  936  395  860  3933 2320  415    0  465  5560 2615  1616  493  1600]

[ 3450  2556 1843 1376  1005  2856 2469 1376  881  600  4647 1552 1425  428  255  4160 3573  936  465    0  6341 3420  3125  632   625]

[ 3712  3999 4800 5853  8896  2079 2716 3085 5076 7095   888 1413 3008 4095 6840   345  976 1635 5560 6341     0  431  2864 3645 11328]

[ 3308  3200 3337 3928  5775  1864 1863 1876 3023 4416  1045  760 1715 2176 3965   628  455  584 2615 3420   431    0   683 1480  6075]

[ 9580  8187 7664 8081 10000  6131 4948 4197 5084 6735  4232 2269 2512 2775 4720  2985 1480  575 1616 3125  2864  683     0  653  3840]

[ 4150  3400 2919 2688  2905  3132 2581 1824 1809 1940  3387 1440 1565  968 1395  2960 2125  540  493  632  3645 1480   653    0   645]

[15232 11947 9648 8105  7680 11967 9468 6513 5220 4515 11960 6333 4960 2735 2360 10013 7320 2835 1600  625 11328 6075  3840  645     0]

(код)

Код:
PsiX=PsiY=Phi= vector(N);
for(k=1, N,
  Xk=Yk=Px=Py=F= 0;
  for(i=1, N, a= X[i]; if(!(a%k), ia= a\n; ja= a%n; if(ja, ia++, ja= n); Xk+= ia; Yk+= ja));
  for(i=1, k, Px+= eulerphi(k)*Xk; Py+= eulerphi(k)*Yk; F+= eulerphi(k)*(N\k));
  PsiX[k]= Px; PsiY[k]= Py; Phi[k]= F
);

print("PsiX="); print(PsiX); print(); print("PsiY="); print(PsiY); print(); print("Phi="); print(Phi); print();

dDN= matrix(N, N);
for(a=1, N,
  xa= a\n; ya= a%n; if(ya, xa++, ya= n);
  for(b=1, N,
   xb= b\n; yb= b%n; if(yb, xb++, yb= n);
   A= (xb^2-xa^2+yb^2-ya^2)*(Phi[a]-Phi[b]);
   B= ((xb-xa)^2+(yb-ya)^2)*(a+b-2*gcd(a,b));
   Cx= (xb-xa)*(PsiX[a]-PsiX[b]);
   Cy= (yb-ya)*(PsiY[a]-PsiY[b]);
   d= A-B-2*(Cx+Cy); dDN[a,b]= d;
   if(d<Dmin, Dmin= d; amin= a; bmin= b); if(d>Dmax, Dmax= d; amax= a; bmax= b)
));

print("dDNmin[",amin,",",bmin,"]= ",Dmin);
print("dDNmax[",amax,",",bmax,"]= ",Dmax);

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение23.11.2014, 20:02 


22/11/14

43
dmd

Вы прочитали мое последнее сообщение? Полагаю, что сначала ошибку должен исправить автор формул.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 00:14 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dmd в сообщении #935201 писал(а):
Помогите найти ошибку на примере случайного квадрата $5\times 5$

(квадрат)

Код:
X=
(1,20,6,23,2),(18,21,24,11,16),(7,10,17,3,9),(4,13,5,22,19),(25,14,12,15,8)

DN= 4697

PsiX=
[75, 72, 150, 152, 300, 168, 420, 352, 324, 240, 880, 384, 468, 252, 360, 512, 1088, 432, 1368, 640, 1260, 1100, 2530, 960, 2500]

PsiY=
[75, 72, 138, 152, 500, 120, 294, 256, 378, 400, 330, 288, 468, 336, 600, 128, 544, 324, 1368, 800, 252, 440, 1518, 768, 2500]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

dDNmin[11,16]= -117
dDNmax[1,25]= 15232
?
? dDN
%28 =
[    0    -4   60   90  1536   112  510  462  742 1292  1620  826  952  748 2020   942 2410 1008 5682 3450  3712 3308  9580 4150 15232]

[   -4     0    9   24   927    88  383  340  423  880  1681  632  595  480 1341  1140 2223  824 4127 2556  3999 3200  8187 3400 11947]

[   60     9    0   23   592    93  368  251  216  565  2056  447  352  189  864  1431 2396  657 3100 1843  4800 3337  7664 2919  9648]

[   90    24   23    0   221   164  625  376  153  268  2879  512  449   56  419  2088 3129  676 2697 1376  5853 3928  8081 2688  8105]

[ 1536   927  592  221     0  1531 1844  973  316  -65  5320 1361 1120   35   40  4025 5136 1231 3000 1005  8896 5775 10000 2905  7680]

[  112    88   93  164  1531     0  103  120  567 1280   549  372  503  584 1881   344 1063  576 4051 2856  2079 1864  6131 3132 11967]

[  510   383  368  625  1844   103    0   61  496 1467   628   61  108  511 1672   577  832  299 2712 2469  2716 1863  4948 2581  9468]

[  462   340  251  376   973   120   61    0  145  776  1047  -24  -87   68  783   960 1021   88 1489 1376  3085 1876  4197 1824  6513]

[  742   423  216  153   316   567  496  145    0  279  2340  321  164  -45  312  2013 2200  495 1264  881  5076 3023  5084 1809  5220]

[ 1292   880  565  268   -65  1280 1467  776  279    0  4177 1036  915  128   25  3400 3931  992 1655  600  7095 4416  6735 1940  4515]

[ 1620  1681 2056 2879  5320   549  628 1047 2340 4177     0  267  976 1869 4176  -117  272  625 4240 4647   888 1045  4232 3387 11960]

[  826   632  447  512  1361   372   61  -24  321 1036   267    0   37  248 1179   408  149  -12 1469 1552  1413  760  2269 1440  6333]

[  952   595  352  449  1120   503  108  -87  164  915   976   37    0  215 1000  1285  800  235  936 1425  3008 1715  2512 1565  4960]

[  748   480  189   56    35   584  511   68  -45  128  1869  248  215    0  177  1860 1635  328  395  428  4095 2176  2775  968  2735]

[ 2020  1341  864  419    40  1881 1672  783  312   25  4176 1179 1000  177    0  3723 3620 1005  860  255  6840 3965  4720 1395  2360]

[  942  1140 1431 2088  4025   344  577  960 2013 3400  -117  408 1285 1860 3723     0  369  824 3933 4160   345  628  2985 2960 10013]

[ 2410  2223 2396 3129  5136  1063  832 1021 2200 3931   272  149  800 1635 3620   369    0  347 2320 3573   976  455  1480 2125  7320]

[ 1008   824  657  676  1231   576  299   88  495  992   625  -12  235  328 1005   824  347    0  415  936  1635  584   575  540  2835]

[ 5682  4127 3100 2697  3000  4051 2712 1489 1264 1655  4240 1469  936  395  860  3933 2320  415    0  465  5560 2615  1616  493  1600]

[ 3450  2556 1843 1376  1005  2856 2469 1376  881  600  4647 1552 1425  428  255  4160 3573  936  465    0  6341 3420  3125  632   625]

[ 3712  3999 4800 5853  8896  2079 2716 3085 5076 7095   888 1413 3008 4095 6840   345  976 1635 5560 6341     0  431  2864 3645 11328]

[ 3308  3200 3337 3928  5775  1864 1863 1876 3023 4416  1045  760 1715 2176 3965   628  455  584 2615 3420   431    0   683 1480  6075]

[ 9580  8187 7664 8081 10000  6131 4948 4197 5084 6735  4232 2269 2512 2775 4720  2985 1480  575 1616 3125  2864  683     0  653  3840]

[ 4150  3400 2919 2688  2905  3132 2581 1824 1809 1940  3387 1440 1565  968 1395  2960 2125  540  493  632  3645 1480   653    0   645]

[15232 11947 9648 8105  7680 11967 9468 6513 5220 4515 11960 6333 4960 2735 2360 10013 7320 2835 1600  625 11328 6075  3840  645     0]

(код)

Код:
PsiX=PsiY=Phi= vector(N);
for(k=1, N,
  Xk=Yk=Px=Py=F= 0;
  for(i=1, N, a= X[i]; if(!(a%k), ia= a\n; ja= a%n; if(ja, ia++, ja= n); Xk+= ia; Yk+= ja));
  for(i=1, k, Px+= eulerphi(k)*Xk; Py+= eulerphi(k)*Yk; F+= eulerphi(k)*(N\k));
  PsiX[k]= Px; PsiY[k]= Py; Phi[k]= F
);

print("PsiX="); print(PsiX); print(); print("PsiY="); print(PsiY); print(); print("Phi="); print(Phi); print();

dDN= matrix(N, N);
for(a=1, N,
  xa= a\n; ya= a%n; if(ya, xa++, ya= n);
  for(b=1, N,
   xb= b\n; yb= b%n; if(yb, xb++, yb= n);
   A= (xb^2-xa^2+yb^2-ya^2)*(Phi[a]-Phi[b]);
   B= ((xb-xa)^2+(yb-ya)^2)*(a+b-2*gcd(a,b));
   Cx= (xb-xa)*(PsiX[a]-PsiX[b]);
   Cy= (yb-ya)*(PsiY[a]-PsiY[b]);
   d= A-B-2*(Cx+Cy); dDN[a,b]= d;
   if(d<Dmin, Dmin= d; amin= a; bmin= b); if(d>Dmax, Dmax= d; amax= a; bmax= b)
));

print("dDNmin[",amin,",",bmin,"]= ",Dmin);
print("dDNmax[",amax,",",bmax,"]= ",Dmax);


Надо N*N/k, а у вас N/k. Суммировать надо от 2 до N*N/2. Еще мне кажется оригинальная формула не совсем работает, особенно B.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 05:37 


22/11/14

43
dimkadimon в сообщении #935306 писал(а):
Еще мне кажется оригинальная формула не совсем работает, особенно B.

B принципиально правильно работать не может, что я выше и показал. Остальные члены правильно себя ведут, вопрос только в том, насколько правильно.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 08:43 


16/08/05
1146
dimkadimon в сообщении #935306 писал(а):
Надо N*N/k, а у вас N/k.

Извиняюсь, забыл скопировать первую строчку. У меня несколько другие обозначения, $N$ это 25 (квадрат 5х5). Т.е. там вначале еще строчка
Код:
n=5;N=n^2;


dimkadimon в сообщении #935306 писал(а):
Суммировать надо от 2 до N*N/2.

Вот в этом месте больше всего непонятно. Формула для $\Delta D$ содержит $a$ и $b$, которые должны меняться от 1 до 25 (квадрат 5х5), они не могут меняться от 2 до 12. Впрочем первая формула для $D$, в которой соответствующую сумму я правильно посчитал от от 2 до 12, тоже не дала (в моём изложении) нужного значения.

-- Пн ноя 24, 2014 10:54:44 --

Еще у меня для любого случайного квадрата по этим формулам получаются абсолютно одинаковые значения. Склонен считать, что ошибка где-то у меня, но я её в упор не вижу.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 10:16 


16/08/05
1146
Ага, я нашёл свою ошибку и теперь первая формула для полного $D$ у меня правильно считается. Но формула для $\Delta D$ под вопросом.

Давайте сверим для случайного квадрата векторы $\Psi_x$, $\Psi_y$, $\Phi$:

Код:
X=
(18,1,13,23,4),(8,5,10,25,2),(3,12,7,20,17),(15,19,21,22,6),(16,11,24,14,9)

DN= 4715

PsiX=
[75, 74, 174, 152, 260, 156, 504, 384, 324, 200, 990, 384, 156, 420, 480, 640, 816, 108, 1368, 480, 1008, 880, 506, 960, 1000]

PsiY=
[75, 76, 126, 128, 280, 132, 420, 160, 324, 280, 660, 240, 468, 336, 120, 128, 1360, 108, 684, 640, 756, 880, 2024, 576, 2000]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 10:53 


22/11/14

43
dmd
Я ведь указал на явную ошибку в исходных формулах whitefox'а: для чего тогда что-то с чем-то сверять и отнимать у людей время?

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 14:58 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dmd в сообщении #934795 писал(а):
Почему при перестановке двух чисел в квадрате оказалось не нужным полностью пересчитать таблицы $\Psi_x$ и $\Psi_y$, а достаточно только в них пересчитать по паре чисел формулами

$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)(a-\gcd(a,b))$

$\Psi'_y(a)=\Psi_y(a)+(y_b-y_a)(a-\gcd(a,b))$

$\Psi'_x(b)=\Psi_x(b)+(x_a-x_b)(b-\gcd(a,b))$

$\Psi'_y(b)=\Psi_y(b)+(y_a-y_b)(b-\gcd(a,b))$


Ну т.е. хорошо если это так. Но на первый взгляд выглядит неправдоподобно легко.

Herbert Kociemba в сообщении #934646 писал(а):
The reason is that I think it is not sufficient to update only $\Psi_x()$ and $\Psi_y()$ for a and b but also you have to update it for all divisors of a and b.

Вы совершенно правы. Обновления $\Psi_x,\Psi_y$ только для $a$ и $b$ совершенно не достаточно. Нужно обновлять эти значения для всех $m$ таких, что $\gcd(m,a)\ne\gcd(m,b)$ по следующим формулам: $$\Psi'_x(m)=\Psi_x(m)+(x_b-x_a)(\gcd(m,a)-\gcd(m,b))$$ $$\Psi'_y(m)=\Psi_y(m)+(y_b-y_a)(\gcd(m,a)-\gcd(m,b))$$Но выполнять эти вычисления нужно только при фактическом выполнении обмена $a\leftrightarrow b.$ Сложность обновления составит $O(n^2).$ При этом оценка $O(1)$ остаётся справедливой для вычисления $\Delta D.$ То есть данный метод "зеркален" второму методу dimkadimon. Там сложность вычисления $\Delta D$ есть $O(n^2)$, а сложность обмена $a\leftrightarrow b$ есть $O(1).$ При предложенном подходе ускорение достигается за счёт того, что обмены $a\leftrightarrow b$ производятся значительно реже чем вычисление $\Delta D.$

-- 24 ноя 2014, 15:22 --

sevir в сообщении #935198 писал(а):
Поменяем местами два числа: тогда левая часть поменяет знак, а в правой не изменит знак только $B$. Сложим почленно 2 уравнения и получим: $0=-2B$. Впечатляет.

Обратите внимание, что формула для $\Delta D$ симметрична по $a$ и $b.$ Вот, что получится при замене в формуле $a\leftrightarrow b:$ $$A=\left(x^2_a-x^2_b+y^2_a-y^2_b\right)\left(\Phi(b)-\Phi(a)\right)=\left(x^2_b-x^2_a+y^2_b-y^2_a\right)\left(\Phi(a)-\Phi(b)\right)$$ $$C_x=(x_a-x_b)\left(\Psi_x(b)-\Psi_x(a)\right)=(x_b-x_a)\left(\Psi_x(a)-\Psi_x(b)\right)$$ $$C_y=(y_a-y_b)\left(\Psi_y(b)-\Psi_y(a)\right)=(y_b-y_a)\left(\Psi_y(a)-\Psi_y(b)\right)$$Как видите, знак не меняется у всех компонент $\Delta D.$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 16:00 
Заслуженный участник
Аватара пользователя


19/12/10
1546
sevir в сообщении #934968 писал(а):
А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

Порядок матрицы в эту формулу не входит, поэтому она работает на матрицах второго порядка точно также как и на матрицах любого другого порядка. Например, $a=3,b=1$ тогда $B=2((x_3-x_1)^2+(y_3-y_1)^2).$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 16:04 


22/11/14

43
whitefox в сообщении #935494 писал(а):
Обратите внимание, что формула для $\Delta D$ симметрична по $a$ и $b.$

Я не про это: если бы она не была симметрична в том смысле, о котором Вы пишете, то ваши формулы вообще потеряли бы всякий смысл. Я говорил о том, что мы рассматриваем две разные матрицы, которые отличаются только перестановкой двух элементов. И к этим элементам применяем ваше преобразование как в первой матрице, так и во второй. Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

-- 24.11.2014, 16:17 --

whitefox в сообщении #935517 писал(а):
sevir в сообщении #934968 писал(а):
А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

Порядок матрицы в эту формулу не входит, поэтому она работает на матрицах второго порядка точно также как и на матрицах любого другого порядка. Например, $a=3,b=1$ тогда $B=2((x_3-x_1)^2+(y_3-y_1)^2).$

Я говорил о 3-ке, привязанной именно к матрице второго порядка, т.к. она только в ней лежит за "экватором": поменяв местами тройку и единицу, мы ничего не изменим, но для пары $a=3,b=2$ $B$ будет одно, а для пары $a=1,b=2$ $B$ будет другим.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 16:18 
Заслуженный участник
Аватара пользователя


19/12/10
1546
sevir в сообщении #935518 писал(а):
Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

Вы не учли, что эти матрицы имеют различные значения $\Psi_x,\Psi_y$. Как результат -- их $\Delta D$ различаются только знаком.

-- 24 ноя 2014, 16:22 --

sevir в сообщении #935518 писал(а):
поменяв местами тройку и единицу, мы ничего не изменим, но для пары $a=3,b=2$ $B$ будет одно, а для пары $a=1,b=2$ $B$ будет другим.

А $\Delta D$ тоже будет разным?

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 16:23 


22/11/14

43
whitefox в сообщении #935521 писал(а):
sevir в сообщении #935518 писал(а):
Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

Вы не учли, что эти матрицы имеют различные значения $\Psi_x,\Psi_y$. Как результат -- их $\Delta D$ различаются только знаком.

Прямой расчет показывает (хотя это и так понятно), что они будут отличаться только знаками: могу привести его для матрицы второго порядка.

-- 24.11.2014, 16:32 --

whitefox в сообщении #935521 писал(а):
А $\Delta D$ тоже будет разным?

Естественно: ведь я беру новую матрицу с переставленными тройкой и единицей, хотя $\Delta D$ не должно меняться.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 16:52 
Заслуженный участник
Аватара пользователя


19/12/10
1546
sevir в сообщении #935523 писал(а):
Естественно: ведь я беру новую матрицу с переставленными тройкой и единицей, хотя $\Delta D$ не должно меняться.

Пример приведите, пожалуйста.

-- 24 ноя 2014, 16:57 --

Herbert Kociemba в сообщении #934878 писал(а):
But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.
jcmeyrignac в сообщении #934965 писал(а):
In fact, Whitefox' algorithm is O(1) for computing the score of swapping a pair.

But the swapping requires to update at most 29+23 products, for example when swapping 720 and 672 on a 27x27 grid.
So the algorithm is indeed O(1+log(n))

Можно $\Psi_x,\Psi_y$ не хранить, а вычислять в процессе вычисления $\Delta D.$ При этом хранить $X_k,Y_k$ и обновлять их при фактическом выполнении обмена $a\leftrightarrow b.$ В этом случае сложность вычисления $\Delta D$ и сложность пересчёта $X_k,Y_k$ будет пропорциональна числу делителей $a$ и $b,$ то есть в среднем $O(\log n).$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 373 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12 ... 25  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group