Fibonacci Strings ISC 2014 Theory

A sequence of fibonacci strings is generated as follows:
S0 = “a”, S1 = “b”, Sn = S(n – 1) + S(n – 2) where ‘+’ denotes concatenation. Thus the sequence is a, b, ba, bab, babba, babbabab, … n terms.

Design a class FiboString to generate fibonacci strings. Some of the members of the class are given below:
Class name: FiboString
Data members/instance variables:
x: to store the first string.
y: to store the second string.
z: to store the concatenation of the previous two strings.
n: to store the number of terms.
Member functions/methods:
FiboString(): constructor to assign x = “a”, y = “b” and z = “ba”.
void accept(): to accept the number of terms ‘n’.
void generate(): to generate and print the fibonacci strings. The sum of (‘+’ i.e. concatenation) first two strings is the third string. Eg. “a” is first string, “b” is second string, then the third will be “ba”, and fourth will be “bab” and so on.

Specify the class FiboString, giving details of the constructor, void accept() and void generate(). Define the main() function to create an object and call the functions accordingly to enable the task.

import java.io.*;
class FiboString{
    private String x;
    private String y;
    private String z;
    private int n;
    public FiboString(){
        x = "a";
        y = "b";
        z = "ba";
        n = 0;
    }
    public void accept()throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("n = ");
        n = Integer.parseInt(br.readLine());
    }
    public void generate(){
        if(n == 1)
            System.out.print(x + "\t");
        else if(n == 2)
            System.out.print(x + "\t" + y + "\t");
        else{
            System.out.print(x + "\t" + y + "\t");
            for(int i = 3; i <= n; i++){
                System.out.print(z + "\t");
                x = new String(y);
                y = new String(z);
                z = new String(y + x);
            }
        }
    }
    public static void main(String args[])throws IOException{
        FiboString obj = new FiboString();
        obj.accept();
        obj.generate();
    }
}

Leave a Reply

%d bloggers like this: