Fibonacci String Program in Java and Python
Fibonacci string program with algorithm, explanation, Java class solution and simple Python solution for ISC students.
Question:
A sequence of Fibonacci Strings is generated as follows: S0 = "a", S1 = "b", and Sn = S(n-1) + S(n-2), where + denotes concatenation.
Thus the sequence is: a, b, ba, bab, babba, babbabab and so on. Design a class FiboString with the constructor, accept() and generate() methods to print n terms.
Algorithm:
Step 1: Start.
Step 2: Declare object variables x, y, z and n.
Step 3: In the constructor, store x = a, y = b and z = ba.
Step 4: In accept(), input the number of terms n.
Step 5: In generate(), check n and display x if at least one term is needed.
Step 6: If n is at least 2, display y as the second term.
Step 7: Initialize a loop counter from 3 because the first two terms are already known.
Step 8: Inside the loop, form z by concatenating y and x.
Step 9: Display z as the current Fibonacci string.
Step 10: Update x with y and y with z to prepare the previous two strings for the next iteration.
Step 11: Repeat until the loop counter reaches n.
Step 12: Stop.
Explanation:
The Fibonacci string series works like the numeric Fibonacci series, but it uses string concatenation instead of addition. Each new string is formed from the previous two strings.
The variables x and y store two consecutive strings. The variable z stores the newly generated string before the values are shifted for the next term.
The first two terms are special cases because they are already known as a and b. The loop begins only from the third term.
After displaying a newly formed string, the program assigns x = y and y = z. This shifting is necessary because the next term must again use the latest two strings.
The class design keeps the state of the sequence inside object variables. This means accept() changes only n, while generate() uses and updates x, y and z to produce the series.
The loop counter controls how many strings are displayed, while the object variables store the current state of the series. No array is required because only the previous two string values are needed to compute the next string.
A Fibonacci string follows the same growth idea as Fibonacci numbers, but with strings. Each new term is formed by joining previous string terms in a fixed order. The program stores earlier terms and repeatedly builds the next one by concatenation. The loop count controls how many terms are generated or which term is required. This teaches that recurrence is not limited to arithmetic values; the same previous-term dependency can be applied to text sequences as long as the construction rule is clear.
Java Program:
/**
* The class FiboString prints the sequence of fibonacci strings
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC 2014 Question 10 (Theory)
*/
import java.util.Scanner;
class FiboString
{
String x,y,z;
int n;
FiboString() // Constructor
{
x = "a";
y = "b";
z = "ba"; // mentioned in the question otherwise not required. z = "" is sufficient
}
void accept()
{
Scanner sc = new Scanner(System.in);
System.out.print("\nEnter the number of terms : ");
n = sc.nextInt();
}
void generate()
{
System.out.print("\nThe Fibonacci String Series is : ");
if(n <= 1) // If no of terms is less than or equal to 1
System.out.print(x);
else // If no of terms is more than or equal to 2
{
System.out.print(x+", "+y);
for(int i=3; i<=n; i++)
{
z = y+x;
System.out.print(", "+z);
x = y;
y = z;
}
}
}
public static void main(String args[])
{
FiboString ob = new FiboString();
ob.accept();
ob.generate();
}
}Equivalent Python Program:
# Read the text input and split or scan it according to the question requirement.
# Helper functions keep repeated calculations separate from the main logic.
# Loops process each word/character and update counters or result strings.
# Display the final text result after sorting, checking or rearranging is complete.
class FiboString:
def __init__(self):
self.x = "a"
self.y = "b"
self.z = "ba"
self.n = 0
def accept(self):
self.n = int(input("Enter the number of terms: "))
def generate(self):
if self.n >= 1:
print(self.x, end="")
if self.n >= 2:
print(", " + self.y, end="")
for i in range(3, self.n + 1):
self.z = self.y + self.x
print(", " + self.z, end="")
self.x = self.y
self.y = self.z
print()
obj = FiboString()
obj.accept()
print("The Fibonacci String Series is:")
obj.generate()Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.