找回密码
 欢迎注册
楼主: mathe

[擂台] 马踏棋盘回路计数问题

[复制链接]
 楼主| 发表于 2011-6-13 22:06:59 | 显示全部楼层
找出问题了,上面代码里面还有两个ans[j]+=,也需要修改成模运算才行。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-6-14 06:12:17 | 显示全部楼层
7*2n的结果,最后一列是最终结果,前面各列分别是模$2^64,2^64-1,2^64-3,2^64-5$的结果。
Fans可以将这个结果提交到OEIS了


6
10676381067638106763810676381067638
83452443231634524432316345244323163452443231634524432316
1012500632799388541250063279938854125006327993885412500632799388541250063279938854
12145693905777556685214569390577755668541456939057775566858145693905777556686238350427205194670084
1429870647765498058542987064776549873884298706477655000994429870647765501460041254934986399237346242334
161223122820450387008012231228206680827326122312282110347418181223122821538865631040157773188600794694366079616
18167623536156227280441676242371761030533616762563921585459920167627041255606145041293153423896688571314211086231916
201237167913364369129814625501770971316139686402971917014208519404824657226389241575689378315795601749194654016984354
22317226597053124870696655742479568214844205446729098439001171920632839496395651337089200028352592236847382536061361269314
241249224303784737725641757712388325224815989571715270554676780337219271950704342999788628764634321214619690049903477212927336
264604173191890994212648472841434166611710245863241851656139140070305795065077771382828630306694429956487028847972161026298271630372
285613305735301450756820033976627477892314158532971566662385271548229427596374044470659956622341145074375059366780515913192965443308548
3044146438106312485025448769774434539919756891798319045225636093465422422958401430135955277162748437831538388102565349465829924427386415734
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-6-14 06:13:17 | 显示全部楼层
7*2n的结果,最后一列是最终结果,前面各列分别是模$2^64,2^64-1,2^64-3,2^64-5$的结果。
Fans可以将这个结果提交到OEIS了


6
10676381067638106763810676381067638
83452443231634524432316345244323163452443231634524432316
1012500632799388541250063279938854125006327993885412500632799388541250063279938854
12145693905777556685214569390577755668541456939057775566858145693905777556686238350427205194670084
1429870647765498058542987064776549873884298706477655000994429870647765501460041254934986399237346242334
161223122820450387008012231228206680827326122312282110347418181223122821538865631040157773188600794694366079616
18167623536156227280441676242371761030533616762563921585459920167627041255606145041293153423896688571314211086231916
201237167913364369129814625501770971316139686402971917014208519404824657226389241575689378315795601749194654016984354
22317226597053124870696655742479568214844205446729098439001171920632839496395651337089200028352592236847382536061361269314
241249224303784737725641757712388325224815989571715270554676780337219271950704342999788628764634321214619690049903477212927336
264604173191890994212648472841434166611710245863241851656139140070305795065077771382828630306694429956487028847972161026298271630372
285613305735301450756820033976627477892314158532971566662385271548229427596374044470659956622341145074375059366780515913192965443308548
3044146438106312485025448769774434539919756891798319045225636093465422422958401430135955277162748437831538388102565349465829924427386415734
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-6-14 06:14:21 | 显示全部楼层
7*2n的结果,最后一列是最终结果,前面各列分别是模$2^64,2^64-1,2^64-3,2^64-5$的结果。
Fans可以将这个结果提交到OEIS了


6
10676381067638106763810676381067638
83452443231634524432316345244323163452443231634524432316
1012500632799388541250063279938854125006327993885412500632799388541250063279938854
12145693905777556685214569390577755668541456939057775566858145693905777556686238350427205194670084
1429870647765498058542987064776549873884298706477655000994429870647765501460041254934986399237346242334
161223122820450387008012231228206680827326122312282110347418181223122821538865631040157773188600794694366079616
18167623536156227280441676242371761030533616762563921585459920167627041255606145041293153423896688571314211086231916
201237167913364369129814625501770971316139686402971917014208519404824657226389241575689378315795601749194654016984354
22317226597053124870696655742479568214844205446729098439001171920632839496395651337089200028352592236847382536061361269314
241249224303784737725641757712388325224815989571715270554676780337219271950704342999788628764634321214619690049903477212927336
264604173191890994212648472841434166611710245863241851656139140070305795065077771382828630306694429956487028847972161026298271630372
285613305735301450756820033976627477892314158532971566662385271548229427596374044470659956622341145074375059366780515913192965443308548
3044146438106312485025448769774434539919756891798319045225636093465422422958401430135955277162748437831538388102565349465829924427386415734
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-6-14 06:15:06 | 显示全部楼层
表格太大了,最后一列看不到,再贴一下:
1067638
34524432316
1250063279938854
38350427205194670084
1254934986399237346242334
40157773188600794694366079616
1293153423896688571314211086231916
41575689378315795601749194654016984354
1337089200028352592236847382536061361269314
42999788628764634321214619690049903477212927336
1382828630306694429956487028847972161026298271630372
44470659956622341145074375059366780515913192965443308548
1430135955277162748437831538388102565349465829924427386415734
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-6-23 14:19:52 | 显示全部楼层
5*8~20*8的计算结果如下:
模$2^64$
44202
55488142
34524432316
13267364410532
7112881119092574
4235482818156697040
1504665377347155052
17980416878068033778
752244656655620712
7602272457316264568
13841467888904518702
8176313932395293354
1098358518885749032
18375149731352769846
1269613588780643810
5123704852959061782

模$2^64-1$
44202
55488142
34524432316
13267364410532
7112881119092574
4235482818156697040
1504665377347155167
17980416878068093702
752244656687432291
7602272474205470849
13841476709057854190
8180966127838009444
3548335122579354054
17618458916660214172
5521631948259473027
4917386807421398577

模$2^64-3$
44202
55488142
34524432316
13267364410532
7112881119092574
4235482818156697040
1504665377347155397
17980416878068213550
752244656751055449
7602272507983883411
13841494349364525166
8190270518723441624
8448288329966564098
16105077287275103244
14025668667217352237
4504750716462361977

最后结果
44202
55488142
34524432316
13267364410532
7112881119092574
4235482818156697040
2122880233853945590892
1105420672289849239070962
586820057145837880942582376
311550865881297158579957164664
162703111270636640083076205067310
85817858712661625199875539483994794
45194091394912063206992882137111564584
23805807202664132087276366105171802289462
12521108409117325721222292833589744938481122
6595228628791806972129208326334327625595610902
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-7-16 08:50:26 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-7-20 13:50:49 | 显示全部楼层
由于无法同时开启1万个文件,计算$9$*$10$棋盘的回路数需要对原来的代码进行修改。

方案如下:

在硬盘中新建$16384$个文件夹。

在内存中开$16384$个读写块,暂时把数据写在这里。

当某个块达到$32$KB($2048$个数据)时,把它写成一个$32$KB的文件,存在对应的文件夹中,然后该块就可以清空重复利用了。

于是每块的大小均不超过$32$KB,一共占用$16384$*$32$KB=$512$MB的内存。

最后我们会得到很多个(大概$33554432$个)$32$KB的文件,分放在$16384$个文件夹中。

平均每个文件夹含有$2048$个文件,$2048$*$2048$=$4194304$个数据。

接下来对于每个文件夹,把里面的$4194304$个数据($64$MB)读入内存,排序并合并相同状态的计数,就完成一轮迭代了。

mathe觉得该方案如何?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-7-22 08:27:18 | 显示全部楼层
看起来不错,就是不知道这样估计要运行多长时间。
另外根据你这个估计,需要1T的硬盘空间了?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-7-22 18:29:30 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2011-7-22 19:02 编辑

这是往最坏的情况估计。

wayne新电脑的硬盘肯定够用。

新的程序还需要多读入几个参数:fc、fd、fe、ff、fg

表示C盘、D盘、E盘、F盘、G盘的可用空间数,以GB为单位。

我们要根据这些参数决定往每个硬盘分配的文件/文件夹数目。

#####

计算$9$*$10$棋盘的回路数,我们需要把不超过1TB的数据来回倒$72$遍,即144TB的读写量。

假设每秒可以读/写$10$MB数据,则一共需要$175$天,也就是前面说过的$6$个月时间。

不过这是以我台式机来算的。wayne的机器可能快不少。

#####

另外,不知道32KB有没有达到wayne电脑中一个文件的最小占用空间。如果还没有达到,可能要改成64KB或更大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 11:59 , Processed in 0.060719 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表