iseemu2009 发表于 2025-2-26 00:20:25

砌砖墙趣题 ProjectEuler#215

如图用2×1和3×1两种规格的砖砌一面墙，要求墙面内相邻两层没有竖向通缝。
所以图中左图是合格的，右图是不合格的。
记砌一面长宽=m×n的墙的合格图案数为W(m,n), 例如 W(9,3)=8. 求W(60,30).

mathe 发表于 2025-2-26 07:51:46

这个题目中墙高比较重要，30稍微大了一些，对计算资源要求太高了，稍微小一点计算压力就不会那么大了。
我们可以看纵向第一部分对应砖头排放方案，从上到下，只有2323...或3232...两种情况。
对于上面两种排列方案，我们都可以先去掉前面两列，余下0101...和1010...
任何时候，我们假设每个中间状态每行余下长度都是012之一。我们对上一个状态中所有余下长度为0的位置补上砖头，于是0变为2或3，原先的1或2保持不变(当然除了最后一步变换过程不允许出现相邻等高)，这样012变为123，所以我们同样可以长度全部减1变为012。
由于所有的0不能相邻，最多一半行为0，每个0可以变换为2或3(但是如果相邻位置有2的就不可以选择2)，所以每个状态最多可以到达2^15个状态，数目还可以接受。
而总体状态数目，第一行有012三种选择，但是下面每一行都不能和上一行相同，所以只能有两种选择，所以共3*2^29个状态，共1.5G个状态。
我们需要为这1.5G个状态都保留一个计数器，然后每次迭代产生一个新的1.5G个状态，使用双缓冲区需要3G个计数器。关键这些数字到后面可能会比较大，用8字节甚至16字节整数表示预计都会溢出。但是使用更大的整数很可能计算机内存空间会不够。
而一种可行结果就是选择一批接近2^64互素的数作为模，进行模运算，最后将不同模下计算结果使用中国剩余定理进行恢复。

iseemu2009 发表于 2025-2-26 08:02:45

改求W(28,8）看看

yigo 发表于 2025-2-26 12:02:29

长度为 n 的墙，一层的铺设方案数记为`F_n`, 则\(F_n=F_{n-2}+F_{n-3},F_2=1,F_3=1,F_4=1\),
例如\(F_9=5\), 5种铺设方案分别为(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2),(3,3,3),分别记为\(A_1,A_2,A_3,A_4,A_5\),
相邻两层的可邻方案：\(A_1 ↔ A_4, A_2 ↔ A_5 ↔ A_3\),
设第m层为\(A_i\)的方案数为\(a_{i,m}\),则\(W(9,m)=a_{1,m}+a_{2,m}+a_{3,m}+a_{4,m}+a_{5,m}\)，
\( \begin{pmatrix}
a_{1,m}\\
a_{2,m}\\
a_{3,m}\\
a_{4,m}\\
a_{5,m}\\
\end{pmatrix}
=\begin{pmatrix}
0&0&0&1&0\\
0&0&0&0&1\\
0&0&0&0&1\\
1&0&0&0&0\\
0&1&1&0&0\\
\end{pmatrix}\begin{pmatrix}
a_{1,m-1}\\
a_{2,m-1}\\
a_{3,m-1}\\
a_{4,m-1}\\
a_{5,m-1}\\
\end{pmatrix}\)
求得\(W(9,m)=2^{\lfloor\frac{m+1}{2}\rfloor}+2^{\lfloor\frac{m}{2}\rfloor}+2\)

mathe 发表于 2025-2-27 14:19:45

W(5,3)=2
W(6,3)=2
W(7,3)=2
W(8,3)=4
W(9,3)=8
W(10,3)=12
W(11,3)=18
W(12,3)=32
W(13,3)=52
W(14,3)=84
W(15,3)=138
W(16,3)=224
W(17,3)=372
W(18,3)=602
W(19,3)=984
W(20,3)=1622
W(21,3)=2632
W(22,3)=4326
W(23,3)=7068
W(24,3)=11538
W(25,3)=18940
W(26,3)=30880
W(27,3)=50586
W(28,3)=82774
W(29,3)=135182
W(30,3)=221490
W(31,3)=361890
W(32,3)=592050
W(33,3)=968914
W(34,3)=1583520
W(35,3)=2591888
W(36,3)=4238268
W(37,3)=6931602
W(38,3)=11341878
W(39,3)=18544674
W(40,3)=30339902
W(41,3)=49624962
W(42,3)=81159636
W(43,3)=132775260
W(44,3)=217145450
W(45,3)=355198316
W(46,3)=581008088
W(47,3)=950261294
W(48,3)=1554444062
W(49,3)=2542445130
W(50,3)=4158614872
W(51,3)=6802350092
W(52,3)=11125962552
W(53,3)=18199000338
W(54,3)=29767324088
W(55,3)=48689175564
W(56,3)=79641091872
W(57,3)=130264504166
W(58,3)=213072176376
W(59,3)=348516717728
W(60,3)=570055242266


W(5,8)=2
W(6,8)=2
W(7,8)=2
W(8,8)=4
W(9,8)=34
W(10,8)=112
W(11,8)=220
W(12,8)=502
W(13,8)=2052
W(14,8)=6932
W(15,8)=17878
W(16,8)=46328
W(17,8)=148544
W(18,8)=479942
W(19,8)=1359910
W(20,8)=3772878
W(21,8)=11374294
W(22,8)=34936064
W(23,8)=102506218
W(24,8)=294713000
W(25,8)=870875826
W(26,8)=2617507202
W(27,8)=7735113546
W(28,8)=22595322040
W(29,8)=66606869850
W(30,8)=197913291570
W(31,8)=585572397094
W(32,8)=1722438038790
W(33,8)=5076737233760
W(34,8)=15024950202434
W(35,8)=44422134336212
W(36,8)=130997964852956
W(37,8)=386430031644840
W(38,8)=1141753533955872
W(39,8)=3373655221138906
W(40,8)=9958030701259110
W(41,8)=29388419608058736
W(42,8)=86790080054425448
W(43,8)=256347413786406926
W(44,8)=756865913979599708
W(45,8)=2234335001007116852
W(46,8)=6597394609869990208
W(47,8)=19482781302086490892
W(48,8)=57527219555110524796
W(49,8)=169845776954810922238
W(50,8)=501497183406137667130
W(51,8)=1480846685491495250274
W(52,8)=4372556574225491530904
W(53,8)=12910451514299199510894
W(54,8)=38120159791430188843994
W(55,8)=112559393309682925845140
W(56,8)=332357486816328885460062
W(57,8)=981341246588125270846010
W(58,8)=2897583308869358196767578
W(59,8)=8555737874645973139378696
W(60,8)=25262653717513938123110956


W(5,18)=2
W(6,18)=2
W(7,18)=2
W(8,18)=4
W(9,18)=1026
W(10,18)=13532
W(11,18)=52492
W(12,18)=161464
W(13,18)=5419032
W(14,18)=94385908
W(15,18)=653517380
W(16,18)=3031190318
W(17,18)=41406122054
W(18,18)=722866878568
W(19,18)=6618416976764
W(20,18)=41147857059630
W(21,18)=395581870108610
W(22,18)=5880148170906870
W(23,18)=62785147255739698
W(24,18)=475301752397698704
W(25,18)=4102137937682820450
W(26,18)=51558909858908089200
W(27,18)=579717342760207477970
W(28,18)=5038564721563370586652
W(29,18)=43335854641959711701112
W(30,18)=477225542588996664792450
W(31,18)=5374914492777019452357536
W(32,18)=50814096418169751478577742
W(33,18)=451324282765571437728703648
W(34,18)=4605683113917978510340534032
W(35,18)=50346139607250165592418539490
W(36,18)=500237770489503326151466359462
W(37,18)=4611673539765950943937650815126
W(38,18)=45330920260731412140309463316352
W(39,18)=479562216882260809527500921211400
W(40,18)=4865240038369072163277257175600278
W(41,18)=46340256614459864765726248030688152
W(42,18)=450042920053408629096741426573049106
W(43,18)=4625916170729336922256835121732515528
W(44,18)=47207673819942095644942272593941149860
W(45,18)=460022568646740914527728914872766757058
W(46,18)=4469410533939318034830785156262625971442
W(47,18)=45081124614042764494919428058617125029174
W(48,18)=458416482768409541045937507725207061446792
W(49,18)=4533281680380514932787533841337631178013828
W(50,18)=44287260736887525475771105217030907833969830
W(51,18)=441729646004470591046937635052632405977905452
W(52,18)=4465500153827428400183714220522111060717270822
W(53,18)=44488622858101663650391264696028756535633287084
W(54,18)=437450592776497990440353676911692105793611352808
W(55,18)=4341376907281848300805188372285741876352314385160
W(56,18)=43617315620821797608032917885803545456708326426170
W(57,18)=435920961309865543462316429763272359417125053044430
W(58,18)=4309401074202423186110600711790782861820825236558024
W(59,18)=42702255899349049481964697674794104257062498315893620
W(60,18)=427079373506467512260261098948203976177678273099187618

mathe 发表于 2025-2-28 08:25:28

W(5,3)=2
W(5,28)=2
W(6,28)=2
W(7,28)=2
W(8,28)=4
W(9,28)=32770
W(10,28)=1664082
W(11,28)=12754588
W(12,28)=53632488
W(13,28)=17172927220
W(14,28)=1396582222520
W(15,28)=25564099775312
W(16,28)=214048909876110
W(17,28)=14033497275877206
W(18,28)=1295322428620005664
W(19,28)=37007961627193010272
W(20,28)=504817263177870686178
W(21,28)=15409404291116782846950
W(22,28)=1258433613107827413793412
W(23,28)=47468150107899962317161314
W(24,28)=907668599318003493336331466
W(25,28)=20770595356595103736440426122
W(26,28)=1302143435795255897467758192504
W(27,28)=57099607501770633656907338658254
W(28,28)=1404574101456107490397212309568276
W(29,28)=30972294402378955108832388432526072
W(30,28)=1436232808487659942960885259827737780
W(31,28)=67163049757097022239786188244342552642
W(32,28)=1975780758706447910863807389219229629322
W(33,28)=46505223330987684037199883038619451472248
W(34,28)=1712346196958214843693410665388009998846898
W(35,28)=78473401101330960664899133408076542756636534
W(36,28)=2626690256664306770183457300751773921380543296
W(37,28)=67812141773566372292501287168582908521275376760
W(38,28)=2171556375003107032620508833012951027976190879500
W(39,28)=92990342309074804636254679307169658558517933591350
W(40,28)=3364399501468350227755374401943826996898981912113860
W(41,28)=95372617006865994123831403953084265571756759240464148
W(42,28)=2871044671389878376834846808687068083025351210371195042
W(43,28)=112501332497411767575773283243345380289510062715430790656
W(44,28)=4231815998480366669679535225149058244061704505469250588320
W(45,28)=129723159150295555402809019353029267417193977390471503054122
W(46,28)=3861456108521620209913777954710887506925282651603861100474946
W(47,28)=139801110474395947811304670713697583882605567933704019723610376
W(48,28)=5278835373910199151476874372162930811037489805583874103473950434
W(49,28)=172070201944364970567915662626290366526741493785825831880250218132
W(50,28)=5203180021279721351423895535693462044036635417396213483340785846686
W(51,28)=177657500737767403760520990212287241418368613126215561714675878713988

上面计算消耗13小时(80G)内存。
由于高度从28到30，无论空间还是时间复杂度都增加四倍以上，预计用这种方法计算W(60,30)，需要至少512G内存的服务器，计算时间会在三天左右。
这个算法的一个问题是主要时间花费在内存访问上，所以CPU计算能力不重要。我试过采用openmp进行多线程计算，发现没有任何好处。
另外一种可行方案就是将中间数据写入SSD磁盘，但是由于磁盘速度远低于内存，整个时间会慢很多倍（比如以月为单位？）。

王守恩 发表于 2025-2-28 08:32:25

换个方向试试 ？

已知W(9,3)=8, W(9,8)=34, W(9,18)=1026。

W(9,1)=5,
W(9,2)=6,
W(9,3)=8,
W(9,4)=10,
W(9,5)=14,
W(9,6)=18,
W(9,7)=26,
W(9,8)=34,
W(9,9)=50,
W(9,10)=66,
W(9,11)=98,
W(9,12)=130,
W(9,13)=194,
W(9,14)=258,
W(9,15)=386,
W(9,16)=514,
W(9,17)=770,
W(9,18)=1026,

{5, 6, 8, 10, 14, 18, 26, 34, 50, 66, 98, 130, 194, 258, 386, 514, 770, 1026, 1538, 2050, 3074, 4098, 6146, 8194, 12290, 16386, 24578, 32770, 49154, 65538}

LinearRecurrence[{1, 2, -2}, {5, 6, 8}, 30]

yigo 发表于 2025-2-28 12:40:47

本帖最后由 yigo 于 2025-2-28 12:56 编辑

n=12,13时的映射关系和矩阵：

或者这样表示映射关系：

aimisiyou 发表于 2025-2-28 16:59:29

难道没有公式吗？

王守恩 发表于 2025-2-28 19:07:10

已知W(10,3)=12, W(10,8)=112, W(10,18)=13532, W(10,28)=1664082。

W(10,1)=7,
W(10,2)=8,
W(10,3)=12,
W(10,4)=18,
W(10,5)=28,
W(10,6)=44,
W(10,7)=70,
W(10,8)=112,
W(10,9)=180,
W(10,10)=290,
W(10,11)=468,
W(10,12)=756,
W(10,13)=1222,
W(10,14)=1976,
W(10,15)=3196,
W(10,16)=5170,
W(10,17)=8364,
W(10,18)=13532,

{6, 8, 12, 18, 28, 44, 70, 112, 180, 290, 468, 756, 1222, 1976, 3196, 5170, 8364, 13532, 21894, 35424, 57316, 92738, 150052, 242788, 392838, 635624, 1028460, 1664082, 2692540, 4356620}

LinearRecurrence[{2, 0, -1}, {6, 8, 12}, 30]
页: [1] 2 3 4 5 6
查看完整版本: 砌砖墙趣题 ProjectEuler#215