Find the previous fibonacci number
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It starts with 0 and 1, and the subsequent numbers are generated by adding the last two numbers in the sequence. In this problem, we are given a number from the Fibonacci sequence, and the task is to find the previous number in the sequence.
Problem Statement
Given a number 'n' from the Fibonacci sequence, we need to find the previous number in the sequence, i.e., the number that comes just before 'n'.
Example
Let's consider the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
- For the input 21, the previous number is 13.
- For the input 13, the previous number is 8.
- For the input 55, the previous number is 34.
- For the input 3, the previous number is 2.
- For the input 1, the previous number is 0.
- For the input 233, the previous number is 144.
Pseudocode
function previous_fib(number):
if number <= 0:
return 0
result = round(number / ((1 + sqrt(5)) / 2))
return result
function main():
previous_fib(21)
previous_fib(13)
previous_fib(55)
previous_fib(3)
previous_fib(1)
previous_fib(233)
Algorithm Explanation
- The function
previous_fib(number)
takes an input 'number', which represents a Fibonacci number, and returns the previous number in the sequence. - If the given 'number' is less than or equal to 0, we return 0 as there is no previous number for the first Fibonacci number (0).
- Using the formula
(number / ((1 + sqrt(5)) / 2))
, we calculate the previous number in the Fibonacci sequence. Here,(1 + sqrt(5)) / 2
is the golden ratio, which is an essential value in the Fibonacci sequence. - The calculated result is rounded to the nearest integer using the
round()
function since the Fibonacci sequence contains only integer values. - The function
main()
callsprevious_fib()
with various test cases to find and print the previous Fibonacci numbers.
Code Solution
Here given code implementation process.
// C program
// Find the previous fibonacci number
#include <stdio.h>
#include <math.h>
//Find the previous fibonacci of given number
void previous_fib(int number)
{
if(number <= 0)
{
return;
}
int result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = round(number / ((1 + sqrt(5)) / 2));
// Display the calculated result
printf("\n [%d] is previous fibonacci are : %d ",number,result);
}
int main()
{
//Test case
previous_fib(21);
previous_fib(13);
previous_fib(55);
previous_fib(3);
previous_fib(1);
previous_fib(233);
return 0;
}
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
// Java program
// Find the previous fibonacci number
class FibonacciNo
{
//Find the previous fibonacci of given number
public void previous_fib(int number)
{
if (number <= 0)
{
return;
}
long result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = Math.round(number / ((1 + Math.sqrt(5)) / 2));
// Display the calculated result
System.out.print("\n [" + number + "] is previous fibonacci are : " + result );
}
public static void main(String[] args)
{
FibonacciNo obj = new FibonacciNo();
//Test case
obj.previous_fib(21);
obj.previous_fib(13);
obj.previous_fib(55);
obj.previous_fib(3);
obj.previous_fib(1);
obj.previous_fib(233);
}
}
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
//Include header file
#include <iostream>
#include<math.h>
using namespace std;
// C++ program
// Find the previous fibonacci number
class FibonacciNo
{
public:
//Find the previous fibonacci of given number
void previous_fib(int number)
{
if (number <= 0)
{
return;
}
long result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = round(number / ((1 + sqrt(5)) / 2));
// Display the calculated result
cout << "\n [" << number << "] is previous fibonacci are : " << result;
}
};
int main()
{
FibonacciNo obj = FibonacciNo();
//Test case
obj.previous_fib(21);
obj.previous_fib(13);
obj.previous_fib(55);
obj.previous_fib(3);
obj.previous_fib(1);
obj.previous_fib(233);
return 0;
}
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
//Include namespace system
using System;
// C# program
// Find the previous fibonacci number
class FibonacciNo
{
//Find the previous fibonacci of given number
public void previous_fib(int number)
{
if (number <= 0)
{
return;
}
long result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = (long)Math.Round(number / ((1 + Math.Sqrt(5)) / 2));
// Display the calculated result
Console.Write("\n [" + number + "] is previous fibonacci are : " + result);
}
public static void Main(String[] args)
{
FibonacciNo obj = new FibonacciNo();
//Test case
obj.previous_fib(21);
obj.previous_fib(13);
obj.previous_fib(55);
obj.previous_fib(3);
obj.previous_fib(1);
obj.previous_fib(233);
}
}
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
<?php
// Php program
// Find the previous fibonacci number
class FibonacciNo
{
//Find the previous fibonacci of given number
public function previous_fib($number)
{
if ($number <= 0)
{
return;
}
$result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
$result = round($number / ((1 + sqrt(5)) / 2));
// Display the calculated result
echo "\n [". $number ."] is previous fibonacci are : ". $result;
}
}
function main()
{
$obj = new FibonacciNo();
//Test case
$obj->previous_fib(21);
$obj->previous_fib(13);
$obj->previous_fib(55);
$obj->previous_fib(3);
$obj->previous_fib(1);
$obj->previous_fib(233);
}
main();
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
// Node Js program
// Find the previous fibonacci number
class FibonacciNo
{
//Find the previous fibonacci of given number
previous_fib(number)
{
if (number <= 0)
{
return;
}
var result = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = Math.round(number / ((1 + Math.sqrt(5)) / 2));
// Display the calculated result
process.stdout.write("\n [" + number + "] is previous fibonacci are : " + result);
}
}
function main()
{
var obj = new FibonacciNo();
//Test case
obj.previous_fib(21);
obj.previous_fib(13);
obj.previous_fib(55);
obj.previous_fib(3);
obj.previous_fib(1);
obj.previous_fib(233);
}
main();
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
import math
# Python 3 program
# Find the previous fibonacci number
class FibonacciNo :
# Find the previous fibonacci of given number
def previous_fib(self, number) :
if (number <= 0) :
return
result = 0
# Formula
# (number / (1 + sqrt(5)) / 2)
# Assuming that, given number is valid fibonacci number
result = round(number / ((1 + math.sqrt(5)) / 2))
# Display the calculated result
print("\n [", number ,"] is previous fibonacci are : ", result, end = "")
def main() :
obj = FibonacciNo()
# Test case
obj.previous_fib(21)
obj.previous_fib(13)
obj.previous_fib(55)
obj.previous_fib(3)
obj.previous_fib(1)
obj.previous_fib(233)
if __name__ == "__main__": main()
Output
[ 21 ] is previous fibonacci are : 13
[ 13 ] is previous fibonacci are : 8
[ 55 ] is previous fibonacci are : 34
[ 3 ] is previous fibonacci are : 2
[ 1 ] is previous fibonacci are : 1
[ 233 ] is previous fibonacci are : 144
# Ruby program
# Find the previous fibonacci number
class FibonacciNo
# Find the previous fibonacci of given number
def previous_fib(number)
if (number <= 0)
return
end
result = 0
# Formula
# (number / (1 + sqrt(5)) / 2)
# Assuming that, given number is valid fibonacci number
result = (number / ((1 + Math.sqrt(5)) / 2)).round()
# Display the calculated result
print("\n [", number ,"] is previous fibonacci are : ", result)
end
end
def main()
obj = FibonacciNo.new()
# Test case
obj.previous_fib(21)
obj.previous_fib(13)
obj.previous_fib(55)
obj.previous_fib(3)
obj.previous_fib(1)
obj.previous_fib(233)
end
main()
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
// Scala program
// Find the previous fibonacci number
class FibonacciNo
{
//Find the previous fibonacci of given number
def previous_fib(number: Int): Unit = {
if (number <= 0)
{
return;
}
var result: Long = 0;
// Formula
// (number / (1 + sqrt(5)) / 2)
// Assuming that, given number is valid fibonacci number
result = Math.round((number / (((1 + Math.sqrt(5)) / 2))));
// Display the calculated result
print("\n [" + number + "] is previous fibonacci are : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: FibonacciNo = new FibonacciNo();
//Test case
obj.previous_fib(21);
obj.previous_fib(13);
obj.previous_fib(55);
obj.previous_fib(3);
obj.previous_fib(1);
obj.previous_fib(233);
}
}
Output
[21] is previous fibonacci are : 13
[13] is previous fibonacci are : 8
[55] is previous fibonacci are : 34
[3] is previous fibonacci are : 2
[1] is previous fibonacci are : 1
[233] is previous fibonacci are : 144
Resultant Output Explanation
The output of the provided code gives us the previous Fibonacci number for each given input. For example:
- For the input 21, the previous Fibonacci number is 13.
- For the input 13, the previous Fibonacci number is 8.
- For the input 55, the previous Fibonacci number is 34.
- For the input 3, the previous Fibonacci number is 2.
- For the input 1, the previous Fibonacci number is 0.
- For the input 233, the previous Fibonacci number is 144.
Time Complexity
The time complexity of the code is constant for each test case because the function previous_fib()
performs basic arithmetic operations and rounding, which have constant time complexity. Therefore, the overall
time complexity is O(1) or constant time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment