一个好玩的游戏

aimisiyou

跑了近20分钟，得出无首尾比较规定情况下f (10）
_ (length (ff 9))
8316
_ (length (ff 10))
46768
_$

aimisiyou

王守恩 发表于 2020-3-2 12:47
找这样的 B 也可以，B=首尾没有0，中间必须有0，不去重。
1, 1, 2, 4, 11, 38, 156, 788,.......=B/2+A0 ...

无论添加什么其他限定规则，你都得先找到无其他限制规则情况下的所有结果（即2个1之间有1个数，2个2之间由个数……）。再根据限制规则去掉不符合要求的，剩下的就是符合你所限定规定要求的数目。我在意的是前面的结果。你都能找到1到100，难道还不能找到其中的所有奇数，所有偶数，所有3的倍数……

aimisiyou

猜想f(n)=(1/2)*((2*n+1)!-q(n)* （2*n-1）!+q(n^3)*(2*n-3)！-q(n^5)*(2*n-5)！+…)的形式。
其中q(n^k)表示一个不超过k次的多项式。

aimisiyou

从中午跑到现在，得出f（11）=320208.（无首尾比较规则）。不敢再往下跑了！！！
求f(10) 按30分钟计算，求f(11)所花时间理论上为30分钟*22*23=4.2小时，与实际6小时左右偏差不多。
按此估计求f(12)理论时间6小时*24*25=150天=5个月！！！

王守恩

aimisiyou 发表于 2020-3-2 16:45
从中午跑到现在，得出f（11）=320208.（无首尾比较规则）。不敢再往下跑了！！！
求f(10) 按30分钟计算， ...

小结。
将 0,1,1,2,2,…,n,n 排成一列，要求两个 k 中间有 k 个数（k=1,2,…,n)，有几种排法？
通项不太好找，这串数长得太快了，当然我会找(如同《汉诺塔升级版》)！
我的初衷是每对数找 1 个答案就可以！！尽可能往前走！！！
享受每次找到答案的喜悦，更鼓励自己去寻找下一个答案的冲动。
谢谢 aimisiyou！谢谢 adlpg070！这是论坛共同的财富。

aimisiyou

王守恩 发表于 2020-3-3 12:09
小结。
将 0,1,1,2,2,…,n,n 排成一列，要求两个 k 中间有 k 个数（k=1,2,…,n)，有几种排法？
通项 ...

要找其中一个答案，可以随机选取其中一个分支往下找，每次随机选择一个分支往下。要碰运气，可能碰上死胡同。

aimisiyou

dlpg070 发表于 2020-3-1 09:54
我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,  788,  4158,  23384        ...

检验了下你的猜想，N>5时,0不可能出现在首尾。猜想是错误的。
n= 5时不存在
n= 6时不存在
n= 7时存在0出现在首尾的情况。
("027423564371516" "274235643715160" "072452634753161" "724526347531610" "074151643752362" "741516437523620" "071316435724625" "713164357246250" "071416354732652" "714163547326520" "017125623475364" "171256234753640" "057141653472362" "571416534723620" "073161345726425" "731613457264250" "017126425374635" "171264253746350" "072462354736151" "724623547361510" "024723645317165" "247236453171650" "057236253471614" "572362534716140" "035723625417164" "357236254171640" "057416154372632" "574161543726320" "035743625427161" "357436254271610" "052732653417164" "527326534171640" "015173465324726" "151734653247260" "072632453764151" "726324537641510" "037463254276151" "374632542761510" "041716425327635" "417164253276350" "073625324765141" "736253247651410" "023726351417654" "237263514176540" "057263254376141" "572632543761410" "034573641512762" "345736415127620" "051716254237643" "517162542376430" "052472654131763" "524726541317630" "036713145627425" "367131456274250" "034673245261715" "346732452617150" "026721514637543" "267215146375430" "014167345236275" "141673452362750" "045671415362732" "456714153627320" "014156742352637" "141567423526370" "053672352461714" "536723524617140" "015167245236473" "151672452364730" "015146735423627" "151467354236270" "062742356437151" "627423564371510" "046171435623725" "461714356237250" "016172452634753" "161724526347530" "023627345161475" "236273451614750" "046171452632753" "461714526327530" "041617435263275" "416174352632750" "056171354632742" "561713546327420" "015163745326427" "151637453264270" "053647352462171" "536473524621710" "052462754316137" "524627543161370" "026327435614175" "263274356141750" "046357432652171" "463574326521710" "025623745361417" "256237453614170" "052642753461317" "526427534613170" "026325734615147" "263257346151470" "016135743625427" "161357436254270" "061517346532472" "615173465324720")
_

aimisiyou

顺带做下N皇后问题吧(也是爆炸增长问题)，即在N*N的棋盘上放置N个皇后(N>1)，使得任意两个皇后都不存在攻击状态（即不能同行同列同斜45度线上），求所有可能存在的状态及状态个数。总个数用f(n)表示。
N=2,f(2)=0;
N=3 ,f(3)=0;
N=4，f(4)=2;
……

aimisiyou

顺带也解决了N皇后问题（与此题一样，都是多叉树裁枝查找过程，运算量都是爆炸式增长）。
_ (h 4)
((3 1 4 2) (2 4 1 3))
_ (h 5)
((1 3 5 2 4) (1 4 2 5 3) (2 4 1 3 5) (2 5 3 1 4) (3 1 4 2 5) (3 5 2 4 1) (4 1 3 5 2) (4 2 5 3 1) (5 2 4 1 3) (5 3 1 4 2))
_ (h 6)
((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5))
_ (h 7)
((1 3 5 7 2 4 6) (1 4 7 3 6 2 5) (1 5 2 6 3 7 4) (1 6 4 2 7 5 3) (2 4 6 1 3 5 7) (2 4 1 7 5 3 6) (2 5 7 4 1 3 6) (2 5 3 1 7 4 6) (2 5 1 4 7 3 6) (2 6 3 7 4 1 5) (2 7 5 3 1 6 4) (3 1 6 2 5 7 4) (3 1 6 4 2 7 5) (3 5 7 2 4 6 1) (3 6 2 5 1 4 7) (3 7 4 1 5 2 6) (3 7 2 4 6 1 5) (4 1 5 2 6 3 7) (4 1 3 6 2 7 5) (4 2 7 5 3 1 6) (4 6 1 3 5 7 2) (4 7 5 2 6 1 3) (4 7 3 6 2 5 1) (5 1 6 4 2 7 3) (5 1 4 7 3 6 2) (5 2 6 3 7 4 1) (5 3 1 6 4 2 7) (5 7 2 4 6 1 3) (5 7 2 6 3 1 4) (6 1 3 5 7 2 4) (6 2 5 1 4 7 3) (6 3 7 4 1 5 2) (6 3 5 7 1 4 2) (6 3 1 4 7 5 2) (6 4 7 1 3 5 2) (6 4 2 7 5 3 1) (7 2 4 6 1 3 5) (7 3 6 2 5 1 4) (7 4 1 5 2 6 3) (7 5 3 1 6 4 2))

_ (length (h 4))
2
_ (length (h 5))
10
_ (length (h 6))
4
_ (length (h 7))
40
_ (length (h 8))
92
_ (length (h 9))
352
_ (length (h 10))
724

aimisiyou

可以发现总个数变化不是指数增长，大约是递增乘以一个数值。虽然搜索的范围是爆炸式的，但总个数增长大约是阶乘的模式。估计f(20)<20!（可以肯定的是f(20)<41!）
对于只求满足要求的总个数，换个思路有些进展，尝试求出f(12)。
如果能求出来f(12)，f(20)也就不是问题了。