Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这题的公式怎么推出来的?In Reply To:Re:这题的公式怎么推出来的? Posted by:uni at 2004-05-14 11:05:09 > 这道题的算法很复杂 > 首先...存在一个比输序列 > 如果是比输序列的数对..那么则比输 > 否则比赢 > 比输序列的规则是 > 第N号序列的两数差为N > 小的那个数的值是最先的前面数列不出现的整数 > 1 2 1号 > 3 5 2号 > 4 7 3号 > > 所以只要记录N号序列的差和最小数就可以了(序列A) > 1 1 > 2 3 > 3 4 > 4 6 > 5 8 > > 然后计算最小数的逐相差有序列 > 2 1 2 2 1 2........... > > 然后可以发现 > > 此序列有递推关系 > 2 1 2 2 1 2..... > 1 0 1 1 0 1 (都减1) > 2 1 2 0 2 1 2 1 2 0 2 1 2(中间插入2) > 2 1 2 2 1 2 1 2 2 1 2.....(不写0) > 变成原来的序列 > > 由此可以推出 > > 序列A的第7号是11的话 > 那么由于(7+1),(11+2)是费波那切数列 > 所以(12+1),(19+2)也是费数列 > 所以第12号是19 > > 又由于 > > 上面的序列变换中 > 是对称的... > > 所以可以知道 > 12+1=11+2=10+3=.... > 19+1=17+3=16+4=.... > > 所以 > 如果想知道11 17是不是A序列里的 > 只要知道 2 3是不是就可以了 > (12 19 这个序列可以用菲薄那切法推算出来) > > 这样...不到23次运算就可以知道100000000000量级的数是不是A序列里的了 > 当然...也可以由此确定比输序列 > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator