Generate the n-th Fibonacci
string that is defined with the next recurrent formula:
·
f(0) = “a”;
·
f(1) = “b”;
·
f(n) = f(n – 1) + f(n – 2), where “+” operation
means concatenation
For example, f(3) =
f(2) + f(1) = (f(1) + f(0)) + f(1) = “b” + “a” + “b”
= “bab”.
Input. One integer n (0 ≤ n ≤ 20).
Output. Print the n-th
Fibonacci string.
|
Sample input 1 |
Sample output 1 |
|
3 |
bab |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
5 |
babbabab |
recursion
Implement a recursive
function that generates the n-th Fibonacci string.
Algorithm realization
Function f returns the n-th Fibonacci string.
string f(int n)
{
if (n == 0) return "a";
if (n == 1) return "b";
return f(n-1) + f(n-2);
}
Read input value of n and print the n-th Fibonacci string.
cin >> n;
cout << f(n) << endl;
#include <stdio.h>
int n;
void f(int
n)
{
if (n == 0)
{
printf("a"); return;
}
if (n == 1)
{
printf("b"); return;
}
f(n-1);
f(n-2);
}
int main(void)
{
scanf("%d",&n);
f(n); printf("\n");
return 0;
}
Java realization
import java.util.*;
public class Main
{
static String f(int n)
{
if (n == 0) return "a";
if (n == 1) return "b";
return f(n - 1) + f(n - 2);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
System.out.println(f(n));
con.close();
}
}
Python ðåàëèçàöèÿ
def f(n):
if n == 0:
return "a"
elif n == 1:
return "b"
else:
return f(n-1) + f(n-2)
n = int(input())
print(f(n))