本帖最后由 aimisiyou 于 2020-3-1 00:34 编辑
先找出满足2个1之间有1个数，2个2之间有2个数……2个n之间有n个数的所有情况，剩下的就是剔除工作了，这个不难。
(defun ff (n)
(defun f (k)
(setq str "")
(repeat k
(setq str (strcat "*" str))
)
)
(setq str_n (strcat (itoa n) (f n) (itoa n)) strlst (list str_n) num (+ n n 1))
(while (> n 1)
(setq vlst nil j 0 nk (length strlst))
(while (< j nk)
(setq en (nth j strlst))
(setq str_n (strcat (f (+ n 1)) en (f (+ n 1))))
(setq i 1)
(while (< i (+ (strlen en) n 3))
(if (= "*" (substr str_n i 1) (substr str_n (+ i n) 1))
(if (= i 1)
(progn
(setq str_new (strcat (itoa(- n 1)) (substr str_n (+ i 1) (- n 1)) (itoa (- n 1)) (substr str_n (+ n 2))))
(setq str_new (vl-string-right-trim "*" (vl-string-left-trim "*" str_new)))
(if (<= (strlen str_new) num)
(setq vlst (cons str_new vlst))
)
)
(progn
(setq str_new(strcat (substr str_n 1 (- i 1)) (itoa (- n 1)) (substr str_n (+ i 1) (- n 1))
(itoa (- n 1))(substr str_n (+ n i 1))))
(setq str_new (vl-string-right-trim "*" (vl-string-left-trim "*" str_new)))
(if (<= (strlen str_new) num)
(setq vlst (cons str_new vlst))
)
)
)
)
(setq i (+ i 1))
)
(setq j (+ 1 j))
)
(setq strlst vlst)
(setq n (- n 1))
)
(setq vvlst (vl-remove nil (mapcar '(lambda (y) (if (= "0" (substr y 1 1))
(if (<= (substr y 2 1) (substr y num 1))
y
nil
)
(if (<= (substr y 1 1) (substr y num 1))
y
nil
)
)
)
(apply 'append (mapcar '(lambda (x)
(if (vl-string-search "*" x)
(list (vl-string-translate "*" "0" x))
(list (strcat "0" x) (strcat x"0"))
)
) strlst))
)
)
)
)
FF
_ (ff 1)
("101")
_ (ff 2)
("12102")
_ (ff 3)
("0231213" "1312032")
_ (ff 4)
("240231413" "141302432" "023421314" "131423024")
_ (ff 5)
("14135243205" "20425314135" "14153042352" "23425314105" "13145320425" "20524131543" "15104235243" "30523421514" "31513420524" "15123425304" "15103425324")
_ (ff 6)
("2612145360435" "4260245316135" "4161345236205" "4263245316105" "3161345026425" "2612153460354" "3046325421615" "1016425324635" "1316435024625" "1613504362542" "3062352416154" "1612532463504" "2632503461514" "1416254230653" "2042635413165" "1416354032652" "2342635410165" "2462514136503" "1014635243265" "1314635240265" "2062514136543" "1016352432654" "2362531416504" "1413564320526" "1415604235263" "1014562342536" "2562141536403" "1015623425364" "1415364235206" "1015364235246" "1516304532642" "3450364251216" "1514603542362" "1512642530463" "1510642532463" "3151364250246" "1510463524326" "2532463514106")
_
_ (length (ff 1))
1
_ (length (ff 2))
1
_(length (ff 3))
2
_ (length (ff 4))
4
_ (length (ff 5))
11
_ (length (ff 6))
38
_ (length (ff 7))
156
_ (length (ff 8))
788
_ (length (ff 9))
4130
_
本帖最后由 aimisiyou 于 2020-3-1 08:38 编辑
n=10时数据溢出了。表存储数据容易，但读取第i位置的数据用(nthi lst)，可能i数值会溢出。按字符串存贮可能计算的n要大一些。
程序还可以优化，用nth函数的话，位置数受最大溢出数值限制。匹配查找过程可以简优化，采用布尔运算。
本帖最后由 王守恩 于 2020-3-1 09:54 编辑
王守恩 发表于 2020-2-25 17:58
补充几句。
1、此题三十年前很流行，几乎每个小朋友都在做。遗憾的是，不是每对数都有答案，
本人在此基 ...
同事们搓麻将、打扑克，小朋友也是挺烦人的。我说我来出道题，
用 0,1,1，0,1,1,2,2 把题意解释清楚，就让小朋友自己动手去折腾，
只要找到 1 个答案就可以！做对了再发 2 张牌，骗小朋友蛮好的。
也许来个小朋友第二天还在兴奋的告诉我：我把 9 做出来了！！
对于每个数都有解，我好像不怀疑，但不曾想某个数有多少解，
更不曾想有怎么多解！谢谢各位网友！
aimisiyou 发表于 2020-3-1 08:35
程序还可以优化，用nth函数的话，位置数受最大溢出数值限制。匹配查找过程可以简优化，采用布尔运算。
我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,788,4158,23384
耗时 3246.78秒
n=9 4158,
n=10 23384
待验证,请帮助
本帖最后由 aimisiyou 于 2020-3-1 10:29 编辑
dlpg070 发表于 2020-3-1 09:54
我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,788,4158,23384 ...
如果不考虑首尾大小比较（只要满足2个1之间有1个数，2个2之间有2个数……2个n之间n个数。0分别放在头和尾算2种结果），有兴趣仅仅算下n较大时所有结果的个数吗？当然要考虑避免数值溢出的情况。比如n=20的结果数。
本帖最后由 dlpg070 于 2020-3-1 12:52 编辑
aimisiyou 发表于 2020-3-1 10:23
如果不考虑首尾大小比较（只要满足2个1之间有1个数，2个2之间有2个数……2个n之间n那个数。0分别放在头 ...
非常希望n=20的结果,对于我这是不可能完成的任务,OEIS中有许多类似数列,期待你的杰作
最好还是去重复的(首位比较的目的是去重).OEIS中多数是去重的
例如:A00088 Number of graphs on n unlabeled nodes.
1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952,
29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776,
1787577725145611700547878190848, 24637809253125004524383007491432768
与此题多么相似,前5项完全一样,a(7)也相同,列出20项
注意这个很老的问题至今有人研究,最新的mma代码是2019年的:Jean - Fran?ois Alcover, Dec 03 2019, after Alois P.Heinz
乐见你的算法的神通
如果能求出数列前20项,或可收录到OEIS
本帖最后由 aimisiyou 于 2020-3-1 18:04 编辑
由于之前算法有瑕疵，导致结果有误。经修改，不考虑首尾限制的情况，得到的结果如下：
_ (length (ff 1))
1
_ (length (ff 2))
2
_ (length (ff 3))
6
_ (length (ff 4))
10
_ (length (ff 5))
22
_ (length (ff 6))
76
_ (length (ff 7))
364
_ (length (ff 8))
1876
_ (length (ff 9))
8316
_
没找到有关这个数列的信息。
如果不包含0。则
_ (defun ff (n)
(setq num (+ n n 1))
(defun f (k)
(setq str "")
(repeat k
(setq str (strcat "0" str))
)
)
(defun fstr (kk sstr)
(setq nkk (max (+ kk 2) (- num (strlen sstr))) vlst nil)
(setq sstr (strcat (f nkk) sstr (f nkk)))
(setq slst (mapcar '(lambda (x) (- x 48)) (vl-string->list sstr)))
(setq nlst (mapcar '(lambda (x) (if (= x 0) 1 0)) slst))
(setq nnlst (mapcar '(lambda (x) (- x 48)) (vl-string->list(strcat "1" (fkk) "1"))))
(while (<= (length nnlst) (length nlst))
(if (= 2 (apply '+ (mapcar '(lambda (x y) (boole 1 x y)) nnlst nlst)))
(progn
(setq ntlst (mapcar '+ slst (mapcar '(lambda (y) (* y kk)) nnlst)))
(setq str1 (vl-list->string (mapcar '(lambda (x) (+ 48 x)) ntlst)))
(setq str_new (vl-string-subst str1 (substr sstr 1 (strlen str1)) sstr))
(setq str_new (vl-string-right-trim "0" (vl-string-left-trim "0" str_new)))
(if (<= (strlen str_new) num)
(setq vlst (cons str_newvlst))
)
)
)
(setq nnlst (cons 0 nnlst))
)
vlst
)
(setq str_n (strcat (itoa n) (f n) (itoa n)) vvlst (list str_n))
(while (> n 1)
(setq vvlst (apply 'append (mapcar '(lambda (x) (fstr (- n 1) x)) vvlst)))
(setq n (- n 1))
)
(setq vvlst(vl-remove nil (mapcar '(lambda (x)
(if (vl-string-search "0" x)
nil
x)
)
vvlst)
)
)
)
FF
_ (ff 1)
nil
_ (ff 2)
nil
_ (ff 3)
("312132" "231213")
_ (ff 4)
("41312432" "23421314")
_ (ff 5)
nil
_ (ff 6)
nil
_ (ff 7)
("27423564371516" "72452634753161" "74151643752362" "71316435724625" "71416354732652" "17125623475364" "57141653472362" "73161345726425" "17126425374635" "72462354736151" "24723645317165" "57236253471614" "35723625417164" "57416154372632" "35743625427161" "52732653417164" "15173465324726" "72632453764151" "37463254276151" "41716425327635" "73625324765141" "23726351417654" "57263254376141" "34573641512762" "51716254237643" "52472654131763" "36713145627425" "34673245261715" "26721514637543" "14167345236275" "45671415362732" "14156742352637" "53672352461714" "15167245236473" "15146735423627" "62742356437151" "46171435623725" "16172452634753" "23627345161475" "46171452632753" "41617435263275" "56171354632742" "15163745326427" "53647352462171" "52462754316137" "26327435614175" "46357432652171" "25623745361417" "52642753461317" "26325734615147" "16135743625427" "61517346532472")
_ (length (ff 1))
0
_(length (ff 2))
0
_ (length (ff 3))
2
_ (length (ff 4))
2
_ (length (ff 5))
0
_ (length (ff 6))
0
_ (length (ff 7))
52
_ (length (ff 8))
300
_ (length (ff 9))
0
_
这个数列到是找到了。