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

公式的推导

Posted by Berry at 2007-10-18 12:56:44 on Problem 2440 and last updated at 2007-10-18 13:03:41
合法的情况:
000     001     010     011     100     110
设达到长度n-1的时候,得到的分别以上述串结尾的序列个数分别为
f1(n-1) f2(n-1) f3(n-1) f4(n-1) f5(n-1) f6(n-1) 
则总共的序列个数F(n-1)=f1(n-1)+f2(n-1)+f3(n-1)+f4(n-1)+f5(n-1)+f6(n-1)
则:
f1(n)=f1(n-1)+f5(n-1)
f2(n)=f1(n-1)+f5(n-1)
f3(n)=f2(n-1)
f4(n)=f2(n-1)
f5(n)=f3(n-1)+f6(n-1)
f6(n)=f4(n-1)
F(n)=f1(n)+f2(n)+f3(n)+f4(n)+f5(n)+f6(n)
    =f1(n-1)+f5(n-1)+f1(n-1)+f5(n-1)+f2(n-1)+f2(n-1)+f3(n-1)+f6(n-1)+f4(n-1)
    =F(n-1)+f1(n-1)+f2(n-1)+f5(n-1)
    =F(n-1)+f1(n-2)+f5(n-2)+f1(n-2)+f5(n-2)+f3(n-2)+f6(n-2)
    =F(n-1)+2*f1(n-2)+2*f5(n-2)+f3(n-2)+f6(n-2)
    =F(n-1)+2*f1(n-3)+2*f5(n-3)+2*f3(n-3)+2*f6(n-3)+f2(n-3)+f4(n-3)
    =F(n-1)+F(n-3)+f1(n-3)+f3(n-3)+f5(n-3)+f6(n-3)
    =F(n-1)+F(n-3)+f1(n-4)+f5(n-4)+f2(n-4)+f3(n-4)+f6(n-4)+f4(n-4)
    =F(n-1)+F(n-3)+F(n-4)


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