作者jurian0101 (Hysterisis)
看板puzzle
标题Re: [问题] 数列
时间Sat Jul 7 01:49:55 2012
※ 引述《EIORU ()》之铭言：
: 有一个正整数数列 规则如下 , 起始数字是 X , y*z=X , 且 y<=z
: 则第1个数字为 yz 并排
: 当数列的数字最接近但不足10000时结束
: 将最後一个数字 和 该数字是数列的第几个 相乘 得出 S Q: 求S最大是多少
: Ex. 1,11,111,337,1337,7191,9799 end S = 9799 x 6 = 58794
: 0 1 2 3 4 5 6
: Ex. 2,12 -> (1)112 (2)26 (3)34 都可以
: (遇到多选时)
看到天使大的推文就想说这题有没有可能光从条件就估计出最长的数列 (下简称链)
的上限。
先来看原题解答数列 (黑文於下, |表示把y z分开)
9|999 -> 8|991 -> 7|928 -> 6|496 -> 2|976 -> 19|52 ->
9|88 -> 7|92 -> 6|44 -> 2|64 -> 1|28 -> 2|8 -> 1|6 -> 6
看看趋势，把每两项的比写出来是
1.11, 1.13, 1.22, 2.18, 1.52, 1.98, 1.25, 1.23, 2.44, 2.06,
4.57, 1.75, 2.67
如果顺着算的话...鬼才知道第三步得选这个大飞跃的路走...
那倒着算呢，分支数极少、又不需要因数分解可以算很快吧
但是...例如说用纸笔算疯狂的把9999~9900这一百个数中最长的那些链列举出来
结果你只会找到 9999 (13步) 、9997 和 9992 (12步，12步的链还有25个QAQ)
更糟糕的是这一堆计算还是不能排除某个数98xx刚好有14步的链...
因此这题就只好就范围内穷举了(ie写程式= =|||)
做法一样有顺着算(很慢)、倒着算(飞快)两种
Mathematica码: 伤眼注意 XD
(*空格为帮助阅读，执行前全拿掉比较不会出错*)
(*此为倒着算算法*)
Clear[LongestChain];
ID[x_Integer]:=IntegerDigits[x];
FD[x_List]:=FromDigits[x];
LongestChain[n_]:=
LongestChain[x]=
Module[{}, poss=Times@@@
Cases[
Table[
{FD[ID[n][[1;;i]], FD[ID[n][[i+1;;]]]},
{i,1,Quotient[Length@[ID@n],2]}
],
{a_Integer,b_Integer}/;a<=b
];
If[poss=={}, 0, 1 + Max@@(LongestChain/@poss)]
]
LongestChainTrace[n_]:=
LongestChainTrace[n]=
Module[{}, poss=Times@@@
Cases[
Table[
{FD[ID[n][[1;;i]], FD[ID[n][[i+1;;]]]},
{i,1,Quotient[Length@[ID@n],2]}
],
{a_Integer,b_Integer}/;a<=b
];
If[poss=={}, {n}, Prepend[LongestChainTrace[poss[[
Select[Ordering[LongestChain/@poss], #==1&,1][[1]]
]]],n]]
]
(*以100,000为例寻找*)
result = LongestChain/@ Range[100000];
(*列出前三长的chain开头 (结尾) *)
show = Table[{Flatten@Position[result,Max[result]-i], Max[result]-i},{i,0,2}]
(*想看哪个链自行手动^^*)
LongestChainTrace[]
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.236.119.215
1F：→ newacc:倒着算然後让程式顺着找会比较快07/07 10:56
2F：→ newacc:像是9999前一个可以是9*999=8991也可以是99*99=9801 07/07 10:56
3F：→ newacc:就让程式去看这两个数字谁的链数比较大07/07 10:57
4F：→ newacc:让程式顺着找的意思是先让程式从1开始算每一个数字的最大链 07/07 10:57
5F：→ newacc:数，这样很快可以找到8991对应的最大链数 07/07 10:58
※ 编辑: jurian0101 来自: 36.236.116.115 (07/07 14:50)
6F：推 DreamYeh:这题我该怎说呢...会给人种可以靠人解的假象 最後发现还 07/09 11:47
7F：→ DreamYeh:是要靠程式穷举ˊwˋ... 07/09 11:48