砌砖墙的趣题

yigo

原来2层有简单递推公式，那就容易反过来找思路了，以下是W（n,2）的思路：
端头只能是2和3，2后面可能接2或者3，所以分类2种情况，
情况1为接2，那么如上图位置画虚线等价于W（n-1,2）
情况2为接3，那么3后面只能接3，等价于W（n-3,2），所以W（n,2）=W（n-1,2）+W（n-3,2）

wayne

宽为20的时候,有114个状态. 邻接关系图是


宽为30的时候,有1897个状态. 邻接关系图是

aimisiyou

yigo 发表于 2025-3-1 11:44
原来2层有简单递推公式，那就容易反过来找思路了，以下是W（n,2）的思路：
端头只能是2和3，2后面可能接2或 ...

你这不对吧？

yigo

W(n,3):

aimisiyou

yigo 发表于 2025-3-1 13:55
W(n,3):

各符号代表啥意思？

王守恩

W(12,n)的来一串数？谢谢！

已知W(12,3)=32, W(12,8)=502, W(12,18)=161464, W(12,28)=53632488。

mathe

切换算法后的代码调通了，比如上面就是输出宽度为9的图，对应结果为

1. Total find 5 nodes 6 edges
   
2. W(9,1)=5
   
3. W(9,2)=6
   
4. W(9,3)=8
   
5. W(9,4)=10
   
6. W(9,5)=14
   
7. W(9,6)=18
   
8. W(9,7)=26
   
9. W(9,8)=34
   
10. W(9,9)=50
    
11. W(9,10)=66
    
12. W(9,11)=98
    
13. W(9,12)=130
    
14. W(9,13)=194
    
15. W(9,14)=258
    
16. W(9,15)=386
    
17. W(9,16)=514
    
18. W(9,17)=770
    
19. W(9,18)=1026
    
20. W(9,19)=1538
    
21. W(9,20)=2050
    
22. W(9,21)=3074
    
23. W(9,22)=4098
    
24. W(9,23)=6146
    
25. W(9,24)=8194
    
26. W(9,25)=12290
    
27. W(9,26)=16386
    
28. W(9,27)=24578
    
29. W(9,28)=32770
    
30. W(9,29)=49154
    
31. W(9,30)=65538
    
32. W(9,31)=98306
    
33. W(9,32)=131074
    
34. W(9,33)=196610
    
35. W(9,34)=262146
    
36. W(9,35)=393218
    
37. W(9,36)=524290
    
38. W(9,37)=786434
    
39. W(9,38)=1048578
    
40. W(9,39)=1572866
    
41. W(9,40)=2097154
    
42. W(9,41)=3145730
    
43. W(9,42)=4194306
    
44. W(9,43)=6291458
    
45. W(9,44)=8388610
    
46. W(9,45)=12582914
    
47. W(9,46)=16777218
    
48. W(9,47)=25165826
    
49. W(9,48)=33554434
    
50. W(9,49)=50331650
    
51. W(9,50)=67108866
    
52. W(9,51)=100663298
    
53. W(9,52)=134217730
    
54. W(9,53)=201326594
    
55. W(9,54)=268435458
    
56. W(9,55)=402653186
    
57. W(9,56)=536870914
    
58. W(9,57)=805306370
    
59. W(9,58)=1073741826
    
60. W(9,59)=1610612738
    
61. W(9,60)=2147483650
    

复制代码

然后试验了一下宽度为50的，大概半分钟结果就出来了

1. Total find 525456 nodes 36118748 edges
   
2. W(50,1)=525456
   
3. W(50,2)=36118748
   
4. W(50,3)=4158614872
   
5. W(50,4)=561974711196
   
6. W(50,5)=90818438239672
   
7. W(50,6)=15146305307894794
   
8. W(50,7)=2767903739371438342
   
9. W(50,8)=501497183406137667130
   
10. W(50,9)=96744526305661206934928
    
11. W(50,10)=18227606734584417013535032
    
12. W(50,11)=3616536318093828576516664524
    
13. W(50,12)=695912794683508385975818305846
    
14. W(50,13)=140353780239426782888599031097394
    
15. W(50,14)=27345438357654983307752018783347620
    
16. W(50,15)=5571958907600482642354725857210143474
    
17. W(50,16)=1094046191970957625893761831942616532334
    
18. W(50,17)=224429063701533460516944941371373100438340
    
19. W(50,18)=44287260736887525475771105217030907833969830
    
20. W(50,19)=9126208891267053354801241187554611930739872378
    
21. W(50,20)=1806833239251705220276461168943398510185048830368
    
22. W(50,21)=373490269330061524408203677493720813050087795477220
    
23. W(50,22)=74106228198110474773007545782789423680928345956200496
    
24. W(50,23)=15351583977615145104919261872535218290575684812158563146
    
25. W(50,24)=3050419670297343602785090868513215567360165489370802219862
    
26. W(50,25)=632872673061946442338604915309930287321305010570841847326946
    
27. W(50,26)=125875723572449583862346515008299722898530826430508765671279676
    
28. W(50,27)=26143678083171299555523050049593039383175416687983279134541186204
    
29. W(50,28)=5203180021279721351423895535693462044036635417396213483340785846686
    
30. W(50,29)=1081511346735203334889381945859023116902128526720877837430077327865746
    
31. W(50,30)=215334233879219014118161761737477961481189988432896327655260165490720604
    
32. W(50,31)=44784028731807084979612980818199009833471319088227768964491181234990053758
    
33. W(50,32)=8919063120143409521478387615083376696594246633860089273652997129359732747736
    
34. W(50,33)=1855732559473403338682846302782831183781411411160166892467157250980998234789900
    
35. W(50,34)=369641488527781448587799861073560600362027970202364822553998892560035630688499686
    
36. W(50,35)=76934348182993947012788953466738102951221738618324885841781032608088876853623795484
    
37. W(50,36)=15325837745010910118449910283375162059230490537688964564156194443291266145562078788780
    
38. W(50,37)=3190639253157725542863907568175378053269334449465895827523442512908482546087541647929210
    
39. W(50,38)=635622599488734080004947472270896798994984842879128759603207192038039631968409739944621396
    
40. W(50,39)=132356801422527117005120827587219417545059609517020829981567306686017696018475742907266383806
    
41. W(50,40)=26367639138037655750965006765682168102129284822511812994482720385652427351040940360420725202170
    
42. W(50,41)=5491581122755097058157069131903053085661105853306973445026773424978084835347184618837745596822444
    
43. W(50,42)=1093996541993411183015731500520016995875293300636199308632531786171862636505031305716209191611605820
    
44. W(50,43)=227882720937784765047199357453506839674277791301449069869359030025683825975535757820183126161702988082
    
45. W(50,44)=45395919739817603274722705904858863956419067696510495219202491246194854764120612204280256162875032645186
    
46. W(50,45)=9457461573370782738935123468434559941300136442174150185847036304013818282744121306245413332047313578046854
    
47. W(50,46)=1883919484154336237846109144762851661031626252763450642668476877734109326702937645441146276109502345184086522
    
48. W(50,47)=392534195300008410786593378344548035202688659070215495154439704951860668231051649611634453546666655751550606538
    
49. W(50,48)=78188791508226524597287433272548949879796020887487045039746228845437396722023256857573355185698158600020725243052
    
50. W(50,49)=16293468168254877518880953542781431275982745302835683161450103788275144469999871497440194171997824002154675994986342
    
51. W(50,50)=3245321532066536902837294149071064079926634046451233069231499823634762812245184565630185223375421460657706534087928604
    
52. W(50,51)=676360295424744728606088497382167338070719367458304727893173010137968128696524443508819080069606603584473718863633660470
    
53. W(50,52)=134709470132766668695512260384336394100096412369715014157236550244538104853620533424034702713543271172578761291933561713124
    
54. W(50,53)=28078116662664456213324042050230741469203138088097083723240232423634322121422442968253918693206428720358476869008446002739464
    
55. W(50,54)=5591945716672834710598067234426337282972672727106762641202630078139398777167144449459049864295820329654075519737883809987908214
    
56. W(50,55)=1165684080205158054410320332728208930227863423364451565859515268643770271033035026817383663884787176701840349089165110986703094130
    
57. W(50,56)=232140141571399213865425994349970424633485532324218313377985828261728288201300106084539448397770611408363096365657562709113895702818
    
58. W(50,57)=48396633967071551344757015719499968693500241807451424865777300220202400817143089895324745466631552350509657477573616624662298056195022
    
59. W(50,58)=9637372211829331221093503490721636812144730685855109962029266277909366145543581290207985374404228296314965477643038851184592956752721832
    
60. W(50,59)=2009415195494631099987362614595024499693517884025375254555497302514286396597448483473960299429027323993065620317252066385165326367751642032
    
61. W(50,60)=400117091314112567121663072472401041492098395728393776837183734535945077810622400366761337426763246579412637727738756368397793329389772321246
    

复制代码

四来

\(W\left( n{,}2\right)=2^{\left\lfloor \frac{n}{3}\right\rfloor}\)
2的\(^{\left\lfloor \frac{n}{3}\right\rfloor}\)次幂.
对不对？来串数验证下。

mathe

W(60,30)=5096310237016542764798233826584550661905954279950628274390676893931034315128456775671704

mathe

1. Total find 8745217 nodes 1651208832 edges
   
2. W(60,1)=8745217
   
3. W(60,2)=1651208832
   
4. W(60,3)=570055242266
   
5. W(60,4)=242201274148024
   
6. W(60,5)=126374376975666006
   
7. W(60,6)=69135571991719781054
   
8. W(60,7)=41814023888294060554390
   
9. W(60,8)=25262653717513938123110956
   
10. W(60,9)=16283983431461310207805555518
    
11. W(60,10)=10315571746626053013208159332316
    
12. W(60,11)=6866822860969226074292872336394926
    
13. W(60,12)=4466323898447364563643292268555995766
    
14. W(60,13)=3027787509574208651553825703397740023490
    
15. W(60,14)=2002041979160276078853343521142878979565446
    
16. W(60,15)=1372409206997379258661788608125706091853392956
    
17. W(60,16)=917659125122296103669188348394571328518472468768
    
18. W(60,17)=633591692685390450050974454760557667512864953843462
    
19. W(60,18)=427079373506467512260261098948203976177678273099187618
    
20. W(60,19)=296300762714118624377999323277114854229284861885626797520
    
21. W(60,20)=200951354626580212151677642786055557761538373851619893556248
    
22. W(60,21)=139887377723295238083392490499771751903170779780330942622013714
    
23. W(60,22)=95333189848866516184904772979531064643391127052030853165249667516
    
24. W(60,23)=66526193233112443852018498991393144382622892438862933772210862951602
    
25. W(60,24)=45518729870356544494612888006989199049648426809877027778217220561876006
    
26. W(60,25)=31822791147855960112846151569569592856387144094167160732911921694275130038
    
27. W(60,26)=21847529894298065699885568388110490384023553055723011703801843400504712042228
    
28. W(60,27)=15295964676133874466316230938898892364807645699912958920367940952693162266383336
    
29. W(60,28)=10532050771648076850685340824028328214218797064370197247812838811839556388801219736
    
30. W(60,29)=7382380148914619014162685895074401251100586471999322712854516703551908960158289460936
    
31. W(60,30)=5096310237016542764798233826584550661905954279950628274390676893931034315128456775671704
    
32. W(60,31)=3575742525909599047557661940558888508673306701387714029592348423721145541250658661545284108
    
33. W(60,32)=2474177719600974740439433260929230046897332663817753571449114242480890675804874036872571498984
    
34. W(60,33)=1737436243517270870444911258101919520660668787874804629963645899167575547405698122271172536484602
    
35. W(60,34)=1204706050668417540590722192855485742239514806507261126656039019852838079556665614588011056354869432
    
36. W(60,35)=846607279022186510046902932361278418974093967418678146480228141771632579387387684984610956067851647858
    
37. W(60,36)=588136836300369881232095809534218736103441503153706366950066550392583780634337642379933929004795971915584
    
38. W(60,37)=413587189008715287037881072272483828176547866068043551124409519364629427844609479781411676404566732858093332
    
39. W(60,38)=287815688532174094673183084437519246737366803692931123109155405425684687466431479167483606650426157606344011290
    
40. W(60,39)=202517318409327900304659410154694919316747171372550790871428306941364155507760721049435637193104594233200967892696
    
41. W(60,40)=141154609621270971519571336506218259892724890022247059671222924463463485485917780811017778308949794323192140751420734
    
42. W(60,41)=99375044447833329862555359711342981887234695878891272846423592852189157869842438400971975677603756469939083435237585358
    
43. W(60,42)=69364347110250419359555025948538824222921304844349194822746308708063594492244886821592289739207240437701142377017477011080
    
44. W(60,43)=48857560588529686392216466478628567791378721273411719325848116665387995999209002619379361753384137852669573341609584886780526
    
45. W(60,44)=34147772516007567939948792213544798221998629183326706690381120564486450108734004894791458694536779259750640752550996152716641396
    
46. W(60,45)=24063123448243787373583163739931402196997494670016731762926047908321013815039799456011207779471636624906791705333591629491524762486
    
47. W(60,46)=16838527956131528176579786167130794217058201890679016341149746955383423390385404543034874550559142303626636490225386840976410243753764
    
48. W(60,47)=11870544148123690001450407541731336875510814998077184494200915288560064620377078755018564154197517533594472709729312720409607049831814042
    
49. W(60,48)=8315685029880504337820331696300491710385730258821002180350862461547029918852531100813949636729759631095955336298927289893189306542330046262
    
50. W(60,49)=5864428012330794556834143682056434236505601821257046444062739052252093738078500914030904038915781129702466079898936766962519570473803769267758
    
51. W(60,50)=4112308097543362171232785418221818939037328047292621238770186511740402680977889551272694743114339009695825434359985451317229598561590660168649556
    
52. W(60,51)=2901081477472014473085016388739527369973400667507255169026333550227303522502427695053024790696508173726276517876941955134082565730888432209145167664
    
53. W(60,52)=2036165569296604449815997556126569887494406286214031243595819862243504237038672017847410247200847856326413533693138686320660292834381459579932263139894
    
54. W(60,53)=1436880699108640941011710325059521302660074818691011833704791325188227550933832323568348638236459153585277557524738387439479658898437633079937312499239948
    
55. W(60,54)=1009324322603967499166279437603431192070763101440040144816702884609975671609887887537218864240958248388009599752440912657638161793434882310795714592641129910
    
56. W(60,55)=712458295743612923421887845990477105623066545346611805903037995575014600317764594776067447931713447246933412099023626116792491351852629699758576379388765976228
    
57. W(60,56)=500832998133066433372101653823438713441148337676623944556130023597291858343387601890409152148768625162533979862132195956170284964693102600089877157571868115759752
    
58. W(60,57)=353615636418534805641615634070623133991206892421517042246424843941417827736695579202958281083302580878196968750777065023636892462499076447917299029393290466998057028
    
59. W(60,58)=248746936848170464233002851510862539959237928585978357103194202966737114253419011816004874784732397117008685825262588507128788699883644200977502376823980800669887340134
    
60. W(60,59)=175669243906310084180034772492885773142775334210965362372827036805066600503837571902736503119017650087639638526965171143316713746970170154872525396068820588334658208742954
    
61. W(60,60)=123647890861006078109774803344509934199662290903306385611816872854556521507277999032042769251438974199032701979310113700296170538148165209467232246957990109180234818150141000
    

复制代码