Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

Re:这题的公式怎么推出来的?

Posted by uni at 2004-05-14 11:05:09 on Problem 1067
In Reply To:这题的公式怎么推出来的? Posted by:C0400348198 at 2004-03-01 17:38:44
这道题的算法很复杂
首先...存在一个比输序列
如果是比输序列的数对..那么则比输
否则比赢
比输序列的规则是
第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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator