论坛 › 编程擂台 › 马踏棋盘回路计数问题

mathe 发表于 2011-6-3 14:03:09

将数据用hash散列到文件可能不如选择固定几个连续位置的值作为文件名更加好
由于每次添加一个格子仅改变少量位置取值，这样可以保证每个文件数据仅产生出少量文件的数据，可以改善数据缓存的效率（另外每个文件数据 ...
mathe 发表于 2011-6-2 22:08 http://bbs.emath.ac.cn/images/common/back.gif
采用固定位置作为文件编号还有一个好处。由于我们知道每次添加格子仅仅改变少量位置取值，所以对于每个文件，经过变换后产生的数据只会写入少量几个文件。同样，我们可以将输入文件分组，使得每组内部的文件经过变换后产生的数据都只会写入少量几个文件。而这时，如果文件数目足够大，那么这几个少量文件数据总量不会太大，所以这时，排序合并之前的数据我们更本没有必要写入文件，直接放在内存即可，等到数据排序合并处理以后一下子写入文件中即可。而由于排序合并之前的文件是最大的，这样应该可以大量减少对磁盘的访问

mathe 发表于 2011-6-3 15:46:16

8*9和8*10都出来了
7112881119092574
4235482818156697040
不过9*2n就不敢运行了，怕磁盘空间不够，把机器运行死了

KeyTo9_Fans 发表于 2011-6-3 16:26:46

看来台式机的运行速度比笔记本电脑快不少。

不能直接运行9*10棋盘，因为数组和文件数量都不够大。

9*10棋盘需要重新写一个程序。

分500个文件写是不够的。

估计要写10000个文件以上。

列一下8*6到8*10的答案。（目前仅缺8*8棋盘的答案没有公布）

还有中间状态数的峰值。

我根据这些数据再估计一下运行9*10棋盘所消耗的资源。

mathe 发表于 2011-6-3 17:23:28

8*8的数据oeis上有的，所以我就没有抄写下来。
13267364410532
至于文件数目，我试着在我机器上修改到2000个以上程序就出问题了（可能是同时打开文件数目达到上限了）。

mathe 发表于 2011-6-4 08:15:51

Fans还可以计算一下7*(2n)每个结果模2^64-1的结果（也就是每次相加时判断，如果结果会大于2^64-1,把和再加1即可）。然后我们使用中国剩余定理就可以求出对应的结果了。
我现在重新计算8*n,并且分别计算模2^64和模2^64-1的结果。

xbtianlang 发表于 2011-6-4 13:04:48

a=x mod (2^64-1)
b=x mod (2^64)
y=(2^128-2^64+a*2^64-b*(2^64-1)) mod (2^128-2^64)
x=y当x<2^128-2^64 时。

mathe 发表于 2011-6-10 10:13:27

由于机器出现问题,没有在预期时间全部达到结果,现在已经有部分8*n的结果，可以先贴出

n$mod(2^64)$$mod(2^64-1)$$mod(2^64-3)$result
544202442024420244202
655488142554881425548814255488142
734524432316345244323163452443231634524432316
813267364410532132673644105321326736441053213267364410532
97112881119092574711288111909257471128811190925747112881119092574
104235482818156697040423548281815669704042354828181566970404235482818156697040
111504665377347155052150466537734715516515046653773471553912085986745706526487660
121798041687806803377817980416878068093701179804168780682135471105402225545775529519346
13752244656655620712752244656687432289752244656751055443586820020252349733523479144
14760227245731626456876022724742054708477602272507983883405311550865844403670432538061432
15138414678889045187021384147670905785418813841494349364525160162703111270599746594928785964078
168176313932395293354819027051872344162185817858712661606753131465774443178
171098358518885749032844828832996656409245194091394912063170099393989692461352
181837514973135276984616105077287275103238326323885119378112085100727490253780278
19126961358878064381014025668667217352234
2051237048529590617824504750716462361971

mathe 发表于 2011-6-13 06:38:29

昨天试着运行了一下6*2n问题的模$2^64-1$结果的前30项，结果得到后面若干项结果同网上公布结果不匹配，有点奇怪，不知道是我的代码有问题还是什么（比如网上数据有误？），代码中我仅修改了:
if(k<t&&u]==u])vi+=v];
最后这里加法改成模加

xbtianlang 发表于 2011-6-13 08:37:18

本帖最后由 xbtianlang 于 2011-6-13 08:39 编辑

我以为直接模加，可能先模$2^64$了，先判断$2^64-1-vi$与$v]$的大小，再加或减。

mathe 发表于 2011-6-13 21:00:43

Fans有空查看一下，估计是我代码改的有问题，6×n的结果模$2^64$没有问题，同网络上的一致
#include<cstdio>
#include<memory>
#include<algorithm>
#include <string.h>
using namespace std;
#define __int64 long long
const unsigned int pm=503,pn=8388608;
char fn;
unsigned char a,b;
unsigned int c,h,i,j,k,l,m,n,t;
unsigned long long o;
unsigned __int64 ui,vi,ans,u,v;
FILE *ou,*in;
#ifndef MODR
#define MODR 0
#endif

unsigned __int64 add(unsigned __int64 x, unsigned __int64 y)
{
    if(MODR==0)return x+y;
    if((-MODR)-x>y)return x+y;
    return x+y+MODR;
}

void pr(unsigned int f,unsigned __int64 v)
{
      fwrite(&v,sizeof(unsigned __int64),1,ou);
}

void pri(unsigned __int64 v)
{
      fwrite(&v,sizeof(unsigned __int64),1,in);
}

void sc(unsigned int f,unsigned __int64 &v)
{
      if(fread(&v,sizeof(unsigned __int64),1,ou)!=1)v=0ull;
}

void sci(unsigned __int64 &v)
{
      if(fread(&v,sizeof(unsigned __int64),1,in)!=1)v=0ull;
}

unsigned __int64 id(unsigned char a[])
{
        unsigned char c,i,j;
        unsigned __int64 s;
        memset(c,0,16);
        for(i=0;i<l;i++)
        {
                j=a;
                if(j>1)
                        if(c)
                        {
                                a-1]=i-c+2;
                                a=0;
                        }
                        else c=i+1;
        }
        s=0;
        for(i=0;i<l;i++)
                s=s*(l+1-i)+a;
        return s;
}

void ar(unsigned __int64 x)
{
        unsigned char i,j,k;
        k=2;
        for(i=l+1;i;)
        {
                i--;
                j=l-i+1;
                a=char(x%j);
                x/=j;
                if(a>1)
                {
                        a-1]=k;
                        a=k++;
                }
        }
}

void ad(unsigned __int64 x)
{
        unsigned __int64 s;
        s=id(b);
        pr(s%pm,s);
        pr(s%pm,x);
        o++;
}

unsigned int d(unsigned int x)
{
        unsigned int i;
        for(i=1;;i++)
                if(i!=x&&a==a)return i;
}

void c1(unsigned int x)
{
        unsigned int i,j;
        if(a==1)return;
        memcpy(b,&a,l);
        if(a==a)
        {
                j=h/m+2;
                b=1;
                for(i=0;i<l;i++)
                        if(h+i+1<j*m&&b!=1||h+i+2>j*m&&b!=0)break;
                if(i>=l)ans=add(ans,vi);
                return;
        }
        if(!a)b=a;
        else
        {
                b=1;
                b=a;
        }
        ad(vi);
}

void c2(unsigned int x,unsigned int y)
{
        unsigned int i,j;
        if(a==1||a==1)return;
        memcpy(b,&a,l);
        if(a&&a==a)
        {
                j=h/m+2;
                b=1;
                b=1;
                for(i=0;i<l;i++)
                        if(h+i+1<j*m&&b!=1||h+i+2>j*m&&b!=0)break;
                if(i>=l)ans=add(ans,vi);
                return;
        }
        if(a)
        {
                b=1;
                b=1;
                if(a)b=a;
                else b=a;
        }
        else
                if(a)
                {
                        b=a;
                        b=1;
                }
                else
                {
                        b=15;
                        b=15;
                }
        ad(vi);
}

bool cmp(unsigned int i,unsigned int j)
{
        return u<u;
}

int main()
{
        scanf("%d%d",&n,&m);
        //n=10;
        //m=8;
        l=m+m+1;
        b=2;
        b=2;
        vi=id(b);
        for(i=0;i<pm;i++)
        {
                sprintf(fn,"sa/%04d.dat",i);
                ou=fopen(fn,"wb");
                if(vi%pm==i)
                {
                        pr(i,vi);
                        pr(i,1);
                }
                fclose(ou);
        }
        for(h=1;h<n*m-m;h++)
        {
                o=0;
                j=h%m;
                for(i=0;i<pm;i++)
                {
                        sprintf(fn,"sb/%04d.dat",i);
                        ou=fopen(fn,"wb");
                }
                for(i=0;i<pm;i++)
                {
                        sprintf(fn,"sa/%04d.dat",i);
                        in=fopen(fn,"rb");
                        while(1)
                        {
                                sci(ui);
                                if(!ui)break;
                                sci(vi);
                                ar(ui);
                                if(a==1)
                                {
                                        memcpy(b,&a,l);
                                        ad(vi);
                                        continue;
                                }
                                if(a>1)
                                {
                                        if(j>1)c1(m-2);
                                        if(j&&h/m<n-2)c1(m+m-1);
                                        if(j<m-1&&h/m<n-2)c1(m+m+1);
                                        if(j<m-2)c1(m+2);
                                        continue;
                                }
                                if(j>1)
                                {
                                        if(h/m<n-2)c2(m-2,m+m-1);
                                        if(j<m-1&&h/m<n-2)c2(m-2,m+m+1);
                                        if(j<m-2)c2(m-2,m+2);
                                }
                                if(j&&h/m<n-2)
                                {
                                        if(j<m-1)c2(m+m-1,m+m+1);
                                        if(j<m-2)c2(m+m-1,m+2);
                                }
                                if(j<m-2&&h/m<n-2)c2(m+m+1,m+2);
                        }
                        fclose(in);
                        in=fopen(fn,"wb");
                        fclose(in);
//                        printf("%c%c%c%d",8,8,8,i);
                }
//                printf(" ");
                for(i=0;i<pm;i++)
                {
                        fclose(ou);
                }
                for(i=0;i<pm;i++)
                {
                        sprintf(fn,"sb/%04d.dat",i);
                        ou=fopen(fn,"rb");
                        t=0;
                        while(1)
                        {
                                sc(i,ui);
                                if(!ui)break;
                                u=ui;
                                sc(i,v);
                                c=t++;
                        }
                        fclose(ou);
                        sprintf(fn,"sb/%04d.dat",i);
                        ou=fopen(fn,"wb");
                        fclose(ou);
                        sort(c,c+t,cmp);
                        sprintf(fn,"sa/%04d.dat",i);
                        in=fopen(fn,"wb");
                        vi=v];
                        for(k=1;k<=t;k++)
                                if(k<t&&u]==u])vi=add(vi,v]);
                                else
                                {
                                        pri(u]);
                                        pri(vi);
                                        if(k<t)vi=v];
                                }
                        fclose(in);
                //        printf("%03d%c%c%c",i,8,8,8);
                }
//                printf("%c%d %d: %llu\n",13,h/m,j,o);
                if(j>m-2){printf("%llu\n",ans);fflush(stdout);}
        }
//        scanf("%d",&h);
        return 0;
}

查看完整版本: 马踏棋盘回路计数问题