2012ACM国际决赛试题 Fibonacci Words算法设计与分析
Part 1 Problem Statements
Problem Reference: ACM-ICPC World Finals 2012 Problem D: Fibonacci Words
1.1 Problem
The Fibonacci Words sequence of bit strings is defined as:
Here + denotes concatenation of strings. The first few elements are:
n F(n)
0 0
1 1
2 10
3 101
4 10110
5 10110101
6 1011010110110
7 101101011011010110101
8 1011010110110101101011011010110110
Given a bit pattern p and a number n, how often does p occur in F(n) ?
1.2 Input and Output
The first line of each test case contains the integer n (
For each test case, display its case number followed by the number of n occurrences of the bit pattern p in F(n) . Occurrences may overlap. The number of occurrences will be less than
| Sample Input | Output for Sample Input |
|---|---|
| Case 1: 6 10 | Case 1: 5 |
| Case 2: 7 10 | Case 2: 8 |
| Case 3: 6 01 | Case 1: 5 |
| Case 4: 6 101 | Case 4: 4 |
| Case 5: 96 10110101101101 | Case 5: 7540113804746346428 |
Part 2 Algorithm Analysis
2.1 Pre-Analysis
Since we are going to develop our discussion on p and F(n), we first let G(n) represents the result of on earth how often does p occur in F(n). Using signal ||, we could write this relationship as G(n) = |F(n)|.
At the same time, G(n) is also the final result to be printed out .
From the statements in Part 1 we know
F(n) = F(n-1) + F(n-2), n >= 2,
which means we can get F(n) by means of connecting F(n-2) to the end of F(n-1 ) .
Thus we could get some inspiration from what called formalistic（形式主义的） thinking and give such a informal formula
G(n) = G(n-1) + G(n-2), n >= 2 .
Actually, we have made a big progress to solve the problem by give the formula (of course, it’s wrong)
G(n) = G(n-1) + G(n-2) , n >= 2 .
2.2 More-Analysis
Think about now we have two strings p1 and p2, while p2 is longer than p1. To check out whether p1 is included in p2, normally we could check every substring of p2 while is the same length with p1.
Similarly , for F(n) = F(n-1) + F(n-2) , n >= 2 ,G(n) means we have done what we have said——to check whether p is included in F(n) and get the result G(n).
Now let’s do some more analysis about the problem.
We assume F(n) = a1a2..am1 + b1b2..bm2 and we could immediately get
F(n-1) = a1a2..am1 and F(n-2) = b1b2..bm2 .
We assume the length of pattern p is M and now we have known G(n-1) and G(n-2), what means we have checked whether p is included in F(n-1) and F(n-2) .
So in the string F(n) what we have not checked yet is just the substring
a(m1-M+1)..am1 + b1..bM-1 .
Similarly , let E(n) = a(m1-M+1)..am1 + b1..bM-1 and Q(n) = | E(n)|.
More accurately to say,there are several cases of E(n).
First, m1+ m2 = M , E(n) = F(n-1) + F(n-2) ;
Secondly, m1+ m2 > M and m2 < M & m1 > M , E(n) = a(m1-M+1)..am1 + F(n-2) ;
Thirdly, m1+ m2 > M and m2 < M & m1 < M , E(n) = F(n) ;
Fourthly, m1+ m2 > M and m2 > M & m1 > M ,E(n) = a(m1-m+1)..am1 + b1..bm-1
Notice here when m = 1 or 0 E(n) =
Now we could give the right formula on P(n) .
G(0) = |F(0)| , G(1) = |F(1)|
To continue our work, first we need a array F_N[] ,which F_N[i] to store the string F[i] , and a string p to store the pattern “p”. Secondly , we need a temporary string to store E[n].
2.3 Fibonacci_Words_First_Solution (C++ Code with C-Free)
2.3.1 Source Code
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
const int NUM = 42 ;
class Fibonacci_Words{
private:
string En ;//保存迭代中的En
string F_N[NUM] ;//保存各项F[n]
int p_len ;//保存pattern的字串长度
int P_N[NUM] ;//保存各项P[n]
public:
Fibonacci_Words(){
Init_F_and_P();
}
void Init_F_and_P() { //初始化F(n)
F_N[0] = "0" ;P_N[0] = -1 ;
F_N[1] = "1" ;P_N[1] = -1 ;
for( int i = 2 ; i < NUM ; i++ ) {
P_N[i] = -1 ;
F_N[i] = F_N[i-1] + F_N[i-2] ;
}
}
void Get_P_and_N(string p , int n){
p_len = p.length();
}
int Fibonacci_Words_Solution( string p , int n ){
int Q = 0 ;
if(n >= 2 ){
En = Get_En( p , n ) ;
if( P_N[n] == -1){
Q = Num_Of_P_In_En( p , En);//use Num_Of_P_In_En to get Q[n]
P_N[n]=Fibonacci_Words_Solution(p,n-1)+Fibonacci_Words_Solution(p,n-2) + Q;
}
return P_N[n] ;
}
if(n == 0 || n == 1){
P_N[n] = Num_Of_P_In_En( p , F_N[n]);
return P_N[n] ;
}
return 0 ;
}
string Get_En (string p , int n ){
En = "" ;
int a_n ; int b_n ;
a_n = F_N[n-1].length();
b_n = F_N[n-2].length();
if( a_n + b_n >= p_len ){
if(a_n + b_n == p_len ) {
En = F_N[n];
return En ;
}
if( b_n < p_len && a_n >= p_len ){
En = F_N[n].substr(a_n - p_len + 1 );
return En ;
}
if(b_n < p_len && a_n < p_len){
En = F_N[n].substr(0);
return En ;
}
if( b_n >= p_len){
En = F_N[n].substr(a_n - p_len + 1, 2 * (p_len - 1));
return En ;
}
}
return En ;
}
int Num_Of_P_In_En( string p , string En){
int Q = 0 ; int e_n = En.length();
for(int i = 0; i <= e_n - p_len ; i++){
if( p == En.substr(i,p_len) ){
Q++ ;
}
}
return Q ;
}
};
int main(){
int n ;
string p ;
int i = 1 ;
int temp ;
int j = 0 ;
cout << " Welcome To The 1st Solution Of Fibonacci Words By Guo Yuan " << endl;
cout << "Please enter the text data here:" << endl
<< " A sample could be 6 10 7 10 6 01 6 101 ~~" << endl;
while(1){
cin >> n >> p ;
temp = n ;
for( j = 0 ; temp == 0 ; j++){
temp = temp / 10 ;
}
if(i == 1){
cout << "Input :n" << setw(5)<< "p" <<right<< setw(48) << "Output :P[n]" << endl;
}
Fibonacci_Words Text;
Text.Get_P_and_N( p , n );
cout << "Case " << i << ":" << n <<" " << left << setw(42-j)<< p << left << setw(2)
<< "Case " << i++ << ":" << Text.Fibonacci_Words_Solution(p , n) << endl;
}
return 0 ;
}2.3.2 Result
Notice that Case 7:96 101 haven’t been printed out. It means the program is not so perfect and that’s what to be discussed in Part 3.
Part 3 Other Solution
3.1 Why Other Solution ?
In Part 2, we use string to store F(n) , but it’s easy to see that length of string F(n) is O(n!) and when n = 100 , the program break down because of lacking memory .Thus I tried several times to find that the maximum n = 42 or some better number but not exceeds 50,which means we can only check p when n <= 42.That’s the reason why Case 7:96 101 haven’t been printed out. That’s a big bug!!
To solve this problem, we need much deeper analysis about Fibonacci Words. First, let we go back to look Fibonacci Words again and let S(n) to record the length of F(n), thus we get
With some math common sense , we know S(n) is just the famous Fibonacci Sequence f(n+1) ,which first studied by Italy mathematician Fibonacci (A.D1175~A.D1250).
Thus ,we get
S(n) = f(n+1) =  ,
And from F(n) = F(n-1) + F(n-2) , n >= 2 we get F(n) = F(n-1) + F(n-2) , n >= 2 = F(n-1) + F(n-3) + F(n-4) = F(n-1) + F(n-3) + F(n-5) + … + F((n+1)%2 )This form means a lot and we just stop here.
3.2 Kill the bug
Still, we assume inputs are n and pattern p and the length of p is M.
Let then we get
S(j+1) = S(j)+S(j-1) < 2M
For k >= 0
F(j + k ) = F(j + k -1) + F(j + k -2)
= F(j + k -1 )+ F(j + k - 3) + F(j + k - 4)
= F(j + k -1 )+ F(j + k - 3) + F(j + k - 5)+…+F(j + k %2)
This means for any k >= 2 , the last substring of F(j+k) could just be F(j) or F(j +1) and the first substring of F(j+k ) is just F(j) .Now because of
F(j+1) > F(j) > M
For F(j + k) = F(j+k -1) + F(j+k -2) ,
E(j+k) = F(j + (k-1) %2)LM + F(j + (k-2) %2)FM
Which means when k = 2x + 1 ,
E(j+k) = F(j )LM + F(j + 1)FM
when k = 2x , x *
E(j+k) = F(j+1 )LM + F(j)FM
Here , if F(n) = a1a2..am , m > M
F(n)LM = am-M+1…am-1am , F(n)FM = a1a2..aM-1.
Let E(1) = F(j)LM + F(j+1)FM , E(0) = F(j+1)LM + F(j)FM , then
E(j+k) = E(k%2)
Q(1) = |E(1)| , Q(0 ) = |E(0)| .
Since P(j + k) = P(j+k -1) + P(j+k -2) + Q(j+k) , Q(j+k) = | E(j+k) |,
now see, what we have got is
P(j + k) = P(j+k -1) + P(j+k -2) + Q(k%2).
Finally , if we want get P(n), we just need to confirm j and store F(j) and F(j+1) and E(1) and E(0) ,then just to get Q(1) and Q (0) . We don’t need to store F(0) ~ F(NUM) , the big bug died !!
3.3 Fibonacci_Words_Second_Solution (C++ Code with C-Free)
3.3.1 Source Code
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
class Fibonacci_Words{
private:
string p ;
string En[2] ;//保存迭代中的En[0]/En(0)
string F_N[2] ;//F[j] = F_N[0] , F[j+1] = F_N[1]
unsigned long long int Q[2] ;//保存 Q[0]Q[1]
unsigned long long int P[2] ;//
unsigned long long int M ;//保存pattern的字串长度
unsigned long long int S ;//保存F(n)的长度
unsigned long long int j ;//保存j
public:
Fibonacci_Words(){};
Fibonacci_Words(string p_out , unsigned long long int n){
Get_P_and_N( p_out , n);
Init_F();
};
void Init_F() { //初始化
unsigned long long int i = 0 ;
En[0] = En[1] = "" ;
F_N[0] = "0" ; F_N[1] = "1" ;//初始化F(n)
Q[0] = P[0] =0 ; Q[1] = P[1] =0 ;//初始化Q[]和P[]
for( i = 1 ; i <= j/2 ; i++ ) {//根据j的大小得到 F[j]和 F[j+1]
F_N[0] = F_N[1] + F_N[0] ;//F(2i )
F_N[1] = F_N[0] + F_N[1] ; //F(2i+1)
}
if( j % 2 ){
string str = F_N[0] ;
F_N[0] = F_N[1];//F_N[0] = F[j]
F_N[1] = F_N[1] + str ;//F_N[1] = F[j+1]
}
En[1] = F_N[0].substr(S-M + 1,M -1) + F_N[1].substr(0 ,M -1);
En[0] = F_N[1].substr(F_N[1].length()-M + 1,M -1) + F_N[0].substr(0 ,M -1);
for( unsigned long long int i = 0; i < 2 * (M -1) ; i++){
if( p == En[1].substr(i,M) ){
Q[1]++ ;
}
if( p == En[0].substr(i,M) ){
Q[0]++ ;
}
}
for( unsigned long long int i= 0 ; i < F_N[1].length() ;i++ ){
if( i < F_N[0].length() && p == F_N[0].substr(i,M) ){
P[0]++ ;
}
if( p == F_N[1].substr(i,M) ){
P[1]++ ;
}
}
}
void Get_P_and_N(string p_out , unsigned long long int n){//确定算法中的j和S[j]
p = p_out ;
M = p.length(); S = 1 ;
unsigned long long int S0 = 0 ; unsigned long long int S1 = 1 ;
for(j = 0 ; S < M ;j++ ) { //生成Fibonacci的数列值，但只保存S[j]
S = S0 + S1 ;
S0 = S1 ;
S1 = S ;
}//S[j] = S
}
unsigned long long int Fibonacci_Words_Solution( unsigned long long int n ){
unsigned long long int k = 0 ;
for( k = 1 ; k <= (n - j ) / 2 ; k++ ){//不断迭代得到P[n]
P[0] = P[1] + P[0] + Q[0];//P[j+2k]
P[1] = P[0] + P[1] + Q[1];//P[j+2k+1]
}
k--;
if( (j + 2 * k) == n ){
return P[0] ;
}
if( (j + 2 * k + 1) == n ){
return P[1] ;
}
}
};
int main(){
string p ;
unsigned long long int n ;
unsigned long long int j ;
unsigned long long int temp ;
unsigned long long int i = 1 ;
cout << " Welcome To The 2nd Solution Of Fibonacci Words By Guo Yuan" << endl;
cout << "Please enter the text data here:" << endl
<< " A sample could be 6 10 7 10 6 01 6 101 ~~" << endl;
while(1){
cin >> n >> p ;
temp = n ;
for( j = 0 ; temp == 0 ; j++){
temp = temp / 10 ;
}
if(i == 1){
cout << "Input :n" << setw(9)<< "p" << right << setw(53) << "Output :P[n]" << endl;
}
Fibonacci_Words Text(p,n);
cout << "Case " << i << ":" << left << setw(7-j) << n
<< " " << left << setw(42-j)<< p << left << setw(2)
<< "Case " << i++ << ":" << Text.Fibonacci_Words_Solution(n) << endl;
}
return 0 ;
}3.3.2 Result
Now Case 7: 96 101 is printed out and Case 8 the right comparing with the data given.
Part 4 Summary
@_1 Fibonacci_Words_First_Solution is a bad way to solve the problem.
Its main disadvantage is to use string to store F(0)~F(n), but in this solution it is just a must thing to store F(0)~F(n) .That causes the lack of memory. But if we discuss it in math only, it’s absolutely right.
And because of recalling of function Fibonacci_Words_Solution( string p , int n ) with the code
P_N[n]=Fibonacci_Words_Solution(p,n-1)+Fibonacci_Words_Solution( p , n-2 ) + Q ;
int Num_Of_P_In_En( string p , string En){
int Q = 0 ; int e_n = En.length();
for(int i = 0; i <= e_n - p_len ; i++){
if( p == En.substr(i,p_len) ){
Q++ ;
……so much times , it makes the cost of the time to get P(n) is so long .
@_2 Fibonacci_Words_Second_Solution is a perfect way to solve the problem .
To solve the problem we just use 5 string and 7 integer varies.
string p ;
string En[2] ;//保存迭代中的En[0]/En(0)
string F_N[2] ;//F[j] = F_N[0] , F[j+1] = F_N[1]
unsigned long long int Q[2] ;//保存 Q[0]Q[1]
unsigned long long int P[2] ;//
unsigned long long int M ;//保存pattern的字串长度
unsigned long long int S ;//保存F(n)的长度
unsigned long long int j ;//保存j And the string we store is just the shortest 2 strings F(j) and F(j+1), not like the Fibonacci_Words_First_Solution to store F(0)~F(n).
There is no recall of function and the basic operator is plus not comparing p with E(n) .
for( k = 1 ; k <= (n - j ) / 2 ; k++ ){//不断迭代得到P[n]
P[0] = P[1] + P[0] + Q[0];//P[j+2k]
P[1] = P[0] + P[1] + Q[1];//P[j+2k+1]
}This makes the Fibonacci_Words_Second_Solution run so fast and the cost of Fibonacci_Words_Second_Solution is O(n). But it’s easy to see the Fibonacci_Words_First_Solution’s basic operator is the sad operator comparing p with E(n) .
@_3 Because of no worry about lacking memory to store F(0)~F(n) , the maximum n even could be 264-1 and the length of pattern is also could be 264-1 for unsigned long long int is unsigned 8 Bytes ,64 bytes. It’s perfect and even better than what is given “
@_4 Another interesting problem
For any integer j given and j <= 264-1, absolutely there is a F(n) which |F(n)|=k >= j.
So if F(n) = a1a2a3..ak , aj = 1 or 0 ?
2012/6/2 [原文为我本科《算法设计》课程的课程作业]