@王守恩 {2, 2, 2, 4, 6, 8, 12, 18, 26, 38, 56, 82, 120, 176, 258, 378, 554, 812, 1190, 1744, 2556, 3746, 5490, 8046, 11792, 17282, 25328, 37120}
对应的\(n\)是啥？
mathe 发表于 2025-3-1 17:10
这道题是怎么分析到节点和边上去了的？能不能举例 W（9，n）是怎么弄到 5个节点和6条边上
mathe这么快就给出了答案，我又慢了一步, 我就给一个Mathematica版本的实现，内存占用也是极小。
先建图,并打印顶点和边的个数。这个过程的时间复杂度是顶点的平方,空间复杂度是边的个数.
w=20;offset=Ceiling;
states=Map]&,Flatten,ConstantArray}],{offset+c}],{c,0,Floor-offset}],1]];
len=Length;weights=ConstantArray[{},len];
Do],states[]],AppendTo],j];AppendTo],i]],{i,1,len},{j,i+1,len}];
Print["vertex count = "<>ToString<>", edge count ="<>ToString@Length]];
然后线性的迭代一下就可以了，这一步最快,时间复杂度是顶点的个数，比如计算的高度是h=60；
h=60;Transpose[{Range,Total/@NestList]]]],{i,len}]&,ConstantArray,h-1]}]
现在唯一可以优化的地方就是 收集每个顶点的邻接点的集合, 目前我是 二层循环,每个循环是顶点个数,所以时间复杂度是 顶点个数的平方.
但我发现很多的顶点是有局部相似的排列特征的.这个应该利用起来, 批量跳过
发现一个奇怪的现象，我们如果对于墙的每一行结构，如果最边上有长度为3的砖块，去除，那么余下长度为3的砖块数目就代表了墙关系图中连同分支的编号。
比如长度为16的墙，
中间长度为3的砖块数目为0的连通分支，只有两个节点的线性图
中间长度为3的砖块数目为1的连通分支，有较多节点的线性图
中间长度为3的砖块数目为2的连通分支
中间长度为3的砖块数目为3的连通分支
中间长度为3的砖块数目为4的连通分支
又比如长度为18的墙
中间长度为3的砖块数目为0的连通分支，只有两个节点的线性图
中间长度为3的砖块数目为1的连通分支，有较多节点的线性图
中间长度为3的砖块数目为2的连通分支
中间长度为3的砖块数目为3的连通分支
中间长度为3的砖块数目为4的连通分支
发现规律后，得出长度为3的对应关系不难，这些对应的3正好有两格重叠。通过这个规律，可以非常容易得出给定宽度的墙的连同分支数目。另外由于不同的连通分支可以独立计算，理论上还可以将它们独立计算，增加并行度或降低内存复杂度。
按照mathe的顶点命名风格，我也画了一个图
w=16;
offset=Ceiling;perm=Flatten,ConstantArray}],{offset+c}],{c,0,Floor-offset}],1];names=Table["N"<>ToString]<>"_"<>ToString],{p,perm}];
states=Map]&,perm];len=Length;assoc={};
weights=ConstantArray[{},len];
Do],states[]],AppendTo],names[]]];AppendTo],j];AppendTo],i]],{i,1,len},{j,i+1,len}];Print["vertex count = "<>ToString<>", edge count ="<>ToString@Length]];
Graph
宽16的图:
https://nestwhile.com/res/dump/16.png
宽18的图:
https://nestwhile.com/res/dump/18.png
根本看不懂。
本帖最后由 yigo 于 2025-3-1 23:58 编辑
yigo 发表于 2025-3-1 13:55
W(n,3):
根据这个递推方程组算出来的
\(W(n,3)=W(n-1,3)+W(n-2,3)+3W(n-3,3)-3W(n-4,3)-7W(n-6,3)+3W(n-7,3)-W(n-8,3)+4W(n-9,3)-W(n-10,3)-W(n-12,3)\)
与19#的公式不太一样，但是验证了数据是对的，估计我这个递推式的特征方程还能因式分解。
验证了下，特征方程可分解为：
\((-1 - x^2 + x^3) (-1 + 3 x^3 - x^4 - 3 x^6 - x^7 + x^9)\)
后面\(x^9\)的多项式与19#的递推式相同，
是不是我前面那个图分类太细了，还可以简化分类。
搞懂了，实际上\(X(n,3),Y(n,3),Z(n,3)\)的递推式都与19#相同，而\(W(n,3)=X(n,3)+Y(n,3)\)是他们的线性叠加，所以特征方程是一样的，只是初始值不一样。
我的跟mathe最新的数据是一致的.
RecurrenceTable[{a==a-3 a+a+3 a+a,a==0,a==0,a==2,a==2,a==2,a==4,a==8,a==12,a==18},a,{n,60}]
谢谢mathe！有您这4个数垫底。答案错不了！
已知W(12,3)=32, W(12,8)=502, W(12,18)=161464, W(12,28)=53632488。
W(12,1)=12,
W(12,2)=18,
W(12,3)=32,
W(12,4)=52,
W(12,5)=96,
W(12,6)=160,
W(12,7)=298,
W(12,8)=502,
W(12,9)=936,
W(12,10)=1586,
W(12,11)=2954,
W(12,12)=5026,
W(12,13)=9346,
W(12,14)=15956,
W(12,15)=29620,
W(12,16)=50726,
W(12,17)=94008,
W(12,18)=161464,
{12, 18, 32, 52, 96, 160, 298, 502, 936, 1586, 2954, 5026, 9346, 15956, 29620, 50726, 94008, 161464, 298752, 514548, 950586, 1641562, 3028184, 5242622, 9657426, 16760190, 30832418, 53632488, 98537132, 171781042}
2 LinearRecurrence[{2, 4, -9, -2, 9, -3}, {4, 6, 9, 16, 26, 48}, 30]