一个好玩的游戏

dlpg070

aimisiyou 发表于 2020-3-4 13:14
可以发现总个数变化不是指数增长，大约是递增乘以一个数值。虽然搜索的范围是爆炸式的，但总个数增长大约是 ...

代码进行一些优化,速度大幅提高,我的计算结果:
1 和aimisiyou相同 n=1,---,11
2 速度快一些
3 预计 n=12 计算时间不会太长,约6664*20= 133280秒= 37.0小时
  如果采用多线程,分段多人协作等,几个小时内可得结果
4 考虑到 aimisiyou 采用先进算法,理应比我快,请LISP转c++ 试试
5 n=20 难,我望而却步,如得解,可发论文,可申请OEIS数列号,祝好运

*** 王守恩一个好玩的游戏搜索 ***
    Wed Mar  4 10:21:21 2020

n=  8 cnt=1876  Elapsed time 0.59

n=  9 cnt=8316  Elapsed time 13.86   = 0.59   * 21.5

n= 10 cnt=46768 Elapsed time 389.75  = 13.86  * 28.1

n= 11 cnt=320208 Elapsed time 6664.78 = 389.75* 17.1


-------
-------------------------
屏幕显示:防死机,演示分段处理
n=11 20 段
n=12 22 段

L:\Release>game
ctime is Wed Mar  4 10:21:21 2020

n=11
n=11
n= 11 i1=  0 Elapsed time 0.01
n= 11 i1=  1 Elapsed time 246.00
n= 11 i1=  2 Elapsed time 491.56
n= 11 i1=  3 Elapsed time 734.86
n= 11 i1=  4 Elapsed time 976.42
n= 11 i1=  5 Elapsed time 1216.60
n= 11 i1=  6 Elapsed time 1458.84
n= 11 i1=  7 Elapsed time 1702.57
n= 11 i1=  8 Elapsed time 1946.33
n= 11 i1=  9 Elapsed time 2189.68
n= 11 i1= 10 Elapsed time 2433.57
n= 11 i1= 11 Elapsed time 2678.44
n= 11 i1= 12 Elapsed time 2945.66
n= 11 i1= 13 Elapsed time 3236.90
n= 11 i1= 14 Elapsed time 3546.96
n= 11 i1= 15 Elapsed time 3881.42
n= 11 i1= 16 Elapsed time 4245.66
n= 11 i1= 17 Elapsed time 4642.54
n= 11 i1= 18 Elapsed time 5079.83
n= 11 i1= 19 Elapsed time 5563.39
n= 11 i1= 20 Elapsed time 6089.63

Elapsed time 6664.78

aimisiyou

可以推出f(12)<C(192,12).
已经找到F(n)一种计数方式，但涉及到大数运算，目前只能给出一些推论，小于某一个上界。
如果大数运算解决了，统计个数f(n)的复杂度为O(n)（若将大数运算看成平常数运算的话）.

aimisiyou

不会编辑公式，贴张统计个数的图片吧。失误失误,那个系数是f(n)的一个上界，“即为”应该为“小于”。

aimisiyou

采用图形来观察每个解的特征，通过前面四个图形可得出，大部分解为朝右凸的半包围形式或者Z形式，对搜索可能有些帮助。"马跳日"的走法较多。

dlpg070

aimisiyou 发表于 2020-3-5 15:42
采用图形来观察每个解的特征，通过前面四个图形可得出，大部分解为朝右凸的半包围形式或者Z形式，对搜索可 ...

最新结果,经过约26小时计算,得 a(12)=2127544
列a(1)--- a(12)于下无首位判别)
n=  1 cnt=      1 Elapsed time 0.00
n=  2 cnt=      2 Elapsed time 0.00
n=  3 cnt=      6 Elapsed time 0.00
n=  4 cnt=     10 Elapsed time 0.00
n=  5 cnt=     22 Elapsed time 0.00
n=  6 cnt=     76 Elapsed time 0.01
n=  7 cnt=    364 Elapsed time 0.02
n=  8 cnt=   1876 Elapsed time 0.39
n=  9 cnt=   8316 Elapsed time 9.25
n= 10 cnt=  46768 Elapsed time 389.75
n= 11 cnt= 320208 Elapsed time 6664.78
n= 12 cnt=2127544 Elapsed time 约26小时
---------------------------------------

aimisiyou

$$恭喜你又往前走了一步！！！$$
$$我把问题简化为求带约束条件的不定方程解的个数。令x_{i}为i所排在的位置数，则有$$
$$x_{0}+2(x_{1}+x_{2}+x_{3}+……+x_{n})=\frac{3*(n+1)*n}{2}+1$$,
$$约束条件：$$
$$1\leq x_{0}\leq2*n+1$$
$$1\leq x_{i} \leq2*n-i   ,                          (1\leq i \leq n)$$
$$且x_{0},x_{1},x_{2}……x_{n}及x_{1}+2,x_{2}+3,x_{3}+4,……x_{n}+(n+1)两两互不相等$$

王守恩

aimisiyou 发表于 2020-3-6 12:18
$$恭喜你又往前走了一步！！！$$
$$我把问题简化为求带约束条件的不定方程解的个数。令x_{i}为i所排在的位 ...

求助。
f(01)=0000001=000000×2+01
f(02)=0000002=000000×2+01+01
f(03)=0000006=000001×2+01+02+01
f(04)=0000010=000001×2+02+03+01+02
f(05)=0000022=000000×2+06+04+04+04+04
f(06)=0000076=000000×2+20+14+12+10+12+08
f(07)=0000364=000026×2+54+48+46+42+40+42+40
f(08)=0001876=000150×2
f(09)=0008316=000000×2
f(10)=0046768=000000×2
f(11)=0320208=017792×2
f(12)=2127544=108144×2

第1个数表示0出现在首尾的次数
第2个数表示1出现在首尾的次数
第3个数表示2出现在首尾的次数
第4个数表示3出现在首尾的次数
第5个数表示4出现在首尾的次数
第6个数表示5出现在首尾的次数

aimisiyou

王守恩 发表于 2020-3-6 14:58
求助。
f(01)=0000001=000000×2+01
f(02)=0000002=000000×2+01+01

如果只找其中一个解，是否可以考虑递归方法，要么能得到解，要么没有解，比单纯的搜索要快些。

王守恩

dlpg070 发表于 2020-3-4 13:54
代码进行一些优化,速度大幅提高,我的计算结果:
1 和aimisiyou相同 n=1,---,11
2 速度快一些

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

王守恩

dlpg070 发表于 2020-3-6 10:54
最新结果,经过约26小时计算,得 a(12)=2127544
列a(1)--- a(12)于下无首位判别)
n=  1 cnt=      1  ...

尊敬的 mathe！能帮个忙，把下面这串数放到 0IES 去求助一下？
题目：将 0,1,1,2,2,…,n,n 排成一列，
要求两个 k 中间有 k 个数（k=1,2,…,n)，
譬如。
1有1种排法： ("101")
2有1种排法 :  ("12102")
3有1种排法：("1312032")
4有3种排法：("131423024" "141302432" "240231413")
5有11种排法
,,,,,,
我们约定：第1个数(不能是0)要比最后1个数小。得到一串数(好不容易找了15个数，通项不好找)：
1, 1, 1, 3, 11, 38, 130, 638, 4158, 23384, 124520, 847484, 6987380, 53746000, 400346544, ...
第 15 个数 400346544 由网友uk702给出，谢谢网友uk702！
第 14 个数 53746000 由网友yjh_27给出，谢谢网友yjh_27(Excel论坛)！
第 13 个数 6987380 由网友时间的音符给出，谢谢网友时间的音符(Excel论坛)！
前面12个数由本帖给出，谢谢 aimisiyou！谢谢dlpg070 ！
谢谢 uk702！谢谢 aimisiyou！谢谢 adlpg070！这是论坛共同的财富。