有趣的数论问题

tm__xk

13824.
字数.

tm__xk

本来我是直接跑程序秒的.既然要过程..那就随便码个好了..
157随意,造成4个空当.
穷举2468在其中的分布.
I.13
"3"需3和9分隔,故6为"1".方案数为(12*6*2=)144.
II.112
同理6为"1",方案数为(12*12*2*5=)1440.
III.1111
方案数为(24*30=)720.
综上,总方案数为(6*(144+1440+720)=)13824.

tm__xk

我一定是太无聊了..竟然无聊到用容斥原理算这个问题..
为方便观看,用图来表示是否能相邻的关系..
用点表示数,用边表示不能相邻的关系..可以看到..其实就是2468构成K4,369构成K3(二者公用6)(当然还有157孤立).
我们来看看取其中若干条边后,使这些边两端相邻的方案数..
应该看到,取出的若干条边,如果存在圈,或者存在度数>=3的点,就很没有考虑的意义了..
还有,这里总共6个点,没有圈,于是至多取5条边.
下面记A[i]为取i条边时对应的方案数.
################以上是废话.以下是无聊.以下纯目测,所以嫌太简单的别找我要过程.(ls的过程也是目测,同样别找我解释.)
I.A[0]=9!
II.A[1]=8!*2*9
III.A[2]=7!*(2*21+2^2*15)
IV.A[3]=6!*(2*30+2^2*33+2^3*3)
V.A[4]=5!*(2*24+2^2*27)
VI.A[5]=4!*2*12
综上,总方案数为A[0]-A[1]+A[2]-A[3]+A[4]-A[5]=9!-8!*2*9+7!*(2*21+2^2*15)-6!*(2*30+2^2*33+2^3*3)+5!*(2*24+2^2*27)-4!*2*12=13824.

tm__xk

bristlegrass 发表于 2013-12-31 09:15
好吧...我也是跑程序的...
要思路的话就随便写一个吧

呃..我的程序..大概跑了..半秒?→_→

tm__xk

话说..一般地讲..这就是求图的哈密顿路的数量吖..

tm__xk

bristlegrass 发表于 2013-12-31 18:15
QAQ,好吧我承认我很渣,我是穷举出来的-.-

嘛..我也是穷举吖..这也就是穷举了吧..
嘛..怎么说也每层都把限制条件弄进去了..怎么说也写了个九重循环..跑太慢也不好意思←_←

tm__xk

qiaoyisi 发表于 2014-1-1 14:44
嗯，谢谢，1~10，有算术方法吗？好像是20000多一点把

请定义所谓的"算术方法".

ps.答案是22032.

tm__xk

bristlegrass 发表于 2014-1-3 10:30
刚刚发现写成九重循环确实比穷举九位数快......不到0.02s

必须的吖....

tm__xk

qiaoyisi 发表于 2014-1-3 23:38
tm-xk能发个计算程序我邮箱吗？,我怎么计算1~12要用130多个小时，可能是算法有问题。

1到10的22032种..直接十重循环..每次都分别验证那一位..很快的吖..
算法很简单就不发了吧..(其实是因为我没有用正规的编程语言..不方便别人用..)

你说的130多个小时的是1到12?我没说我算过1到12的吖..不知道会不会很慢..
呃..如果你是想说1到10..笔误了的话..那130多个小时就太慢了..不至于是穷举10!种再验证吧..
等我看看同样方法开到12重能不能跑得动←_←

嘛..其实一般地..这就是个哈密顿路计数..没啥好再取巧的了吧..

tm__xk

qiaoyisi 发表于 2014-1-4 15:47
我算1~11不过几秒，1~12就是12!=479001600 算1秒能处理1000个排列，也要479001.6秒，即7983.36分钟，133.05 ...

1到12的..结果是476928么..
十二重循环..跑了48s..
需要的话我可以把程序贴上来..
(不过我觉得就是简单的循环而已..实在没啥贴的必要..)
(算法就相当于几个好多层循环好多个if而已..而我不是用正规的编程语言写的..所以格式相对比较不一样..这才是我不想贴上来的原因..)