Dado un entero positivo n, la tarea es imprimir el n-ésimo número que no es de Fibonacci . Los números de Fibonacci se definen como:
Fib(0) = 0 Fib(1) = 1 for n >1, Fib(n) = Fib(n-1) + Fib(n-2)
Los primeros números de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..
Ejemplos:
Input : n = 2 Output : 6 Input : n = 5 Output : 10
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find n'th Fibonacci number
#include <bits/stdc++.h>
using namespace std;
// Returns n'th Non-Fibonacci number
int nonFibonacci(int n)
{
// curr is to keep track of current fibonacci
// number, prev is previous, prevPrev is
// previous of previous.
int prevPrev = 1, prev = 2, curr = 3;
// While count of non-fibonacci numbers
// doesn't become negative or zero
while (n > 0) {
// Simple Fibonacci number logic
prevPrev = prev;
prev = curr;
curr = prevPrev + prev;
// (curr - prev - 1) is count of
// non-Fibonacci numbers between curr
// and prev.
n = n - (curr - prev - 1);
}
// n might be negative now. Make sure it
// becomes positive by removing last added
// gap.
n = n + (curr - prev - 1);
// n must be now positive and less than or equal
// to gap between current and previous, i.e.,
// (curr - prev - 1);
// Now add the positive n to previous Fibonacci
// number to find the n'th non-fibonacci.
return prev + n;
}
// Driver code
int main()
{
cout << nonFibonacci(5);
return 0;
}
C
// C program to find n'th Fibonacci number
#include<stdio.h>
// Returns n'th Non-Fibonacci number
int nonFibonacci(int n)
{
// curr is to keep track of current fibonacci
// number, prev is previous, prevPrev is
// previous of previous.
int prevPrev=1, prev=2, curr=3;
// While count of non-fibonacci numbers
// doesn't become negative or zero
while (n > 0)
{
// Simple Fibonacci number logic
prevPrev = prev;
prev = curr;
curr = prevPrev + prev;
// (curr - prev - 1) is count of
// non-Fibonacci numbers between curr
// and prev.
n = n - (curr - prev - 1);
}
// n might be negative now. Make sure it
// becomes positive by removing last added
// gap.
n = n + (curr - prev - 1);
// n must be now positive and less than or equal
// to gap between current and previous, i.e.,
// (curr - prev - 1);
// Now add the positive n to previous Fibonacci
// number to find the n'th non-fibonacci.
return prev + n;
}
// Driver code
int main()
{
printf("%d",nonFibonacci(5));
return 0;
}
// This code is contributed by allwink45.
Java
// Java program to find
// n'th Fibonacci number
import java.io.*;
class GFG {
// Returns n'th Non-
// Fibonacci number
static int nonFibonacci(int n)
{
// curr is to keep track of
// current fibonacci number,
// prev is previous, prevPrev
// is previous of previous.
int prevPrev = 1, prev = 2, curr = 3;
// While count of non-fibonacci
// numbers doesn't become
// negative or zero
while (n > 0) {
// Simple Fibonacci number logic
prevPrev = prev;
prev = curr;
curr = prevPrev + prev;
// (curr - prev - 1) is count
// of non-Fibonacci numbers
// between curr and prev.
n = n - (curr - prev - 1);
}
// n might be negative now. Make
// sure it becomes positive by
// removing last added gap.
n = n + (curr - prev - 1);
// n must be now positive and less
// than or equal to gap between
// current and previous, i.e.,
// (curr - prev - 1);
// Now add the positive n to
// previous Fibonacci number
// to find the n'th non-fibonacci.
return prev + n;
}
// Driver Code
public static void main(String args[])
{
System.out.println(nonFibonacci(5));
}
}
// This code is contributed by aj_36
Python
# Python program to find n'th # Fibonacci number # Returns n'th Non-Fibonacci # number def nonFibonacci(n): # curr is to keep track of # current fibonacci number, # prev is previous, prevPrev # is previous of previous. prevPrev = 1 prev = 2 curr = 3 # While count of non-fibonacci # numbers doesn't become # negative or zero while n > 0: prevPrev = prev prev = curr curr = prevPrev + prev # (curr - prev - 1) is # count of non-Fibonacci # numbers between curr # and prev. n = n - (curr - prev - 1) # n might be negative now. # Make sure it becomes positive # by removing last added gap. n = n + (curr - prev - 1) # n must be now positive and # less than or equal to gap # between current and previous, # i.e., (curr - prev - 1) # Now add the positive n to # previous Fibonacci number to # find the n'th non-fibonacci. return prev + n # Driver code print(nonFibonacci(5)) # This code is contributed by anuj_67.
C#
// C# program to find
// n'th Fibonacci number
using System;
class GFG
{
// Returns n'th Non-
// Fibonacci number
static int nonFibonacci (int n)
{
// curr is to keep track of
// current fibonacci number,
// prev is previous, prevPrev
// is previous of previous.
int prevPrev = 1, prev = 2, curr = 3;
// While count of non-fibonacci
// numbers doesn't become
// negative or zero
while (n > 0)
{
// Simple Fibonacci number logic
prevPrev = prev;
prev = curr;
curr = prevPrev + prev;
// (curr - prev - 1) is count
// of non-Fibonacci numbers
// between curr and prev.
n = n - (curr - prev - 1);
}
// n might be negative now. Make
// sure it becomes positive by
// removing last added gap.
n = n + (curr - prev - 1);
// n must be now positive and less
// than or equal to gap between
// current and previous, i.e.,
// (curr - prev - 1);
// Now add the positive n to
// previous Fibonacci number
// to find the n'th non-fibonacci.
return prev + n;
}
// Driver Code
public static void Main ()
{
Console.WriteLine (nonFibonacci(5));
}
}
//This code is contributed by aj_36
PHP
<?php
// PHP program to find
// n'th Fibonacci number
// Returns n'th Non-
// Fibonacci number
function nonFibonacci($n)
{
// curr is to keep track of
// current fibonacci number,
// prev is previous, prevPrev
// is previous of previous.
$prevPrev = 1;
$prev = 2;
$curr = 3;
// While count of non-fibonacci
// numbers doesn't become
// negative or zero
while ($n > 0)
{
// Simple Fibonacci
// number logic
$prevPrev = $prev;
$prev = $curr;
$curr = $prevPrev + $prev;
// (curr - prev - 1) is count
// of non-Fibonacci numbers
// between curr and prev.
$n = $n - ($curr - $prev - 1);
}
// n might be negative now. Make
// sure it becomes positive by
// removing last added gap.
$n = $n + ($curr - $prev - 1);
// n must be now positive and
// less than or equal to gap
// between current and previous,
// i.e., (curr - prev - 1);
// Now add the positive n to
// previous Fibonacci number
// to find the n'th non-fibonacci.
return $prev + $n;
}
// Driver code
echo nonFibonacci(5);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to find n'th Fibonacci number
// Returns n'th Non-Fibonacci number
function nonFibonacci(n)
{
// curr is to keep track of current fibonacci
// number, prev is previous, prevPrev is
// previous of previous.
let prevPrev=1, prev=2, curr=3;
// While count of non-fibonacci numbers
// doesn't become negative or zero
while (n > 0)
{
// Simple Fibonacci number logic
prevPrev = prev;
prev = curr;
curr = prevPrev + prev;
// (curr - prev - 1) is count of
// non-Fibonacci numbers between curr
// and prev.
n = n - (curr - prev - 1);
}
// n might be negative now. Make sure it
// becomes positive by removing last added
// gap.
n = n + (curr - prev - 1);
// n must be now positive and less than or equal
// to gap between current and previous, i.e.,
// (curr - prev - 1);
// Now add the positive n to previous Fibonacci
// number to find the n'th non-fibonacci.
return prev + n;
}
// Driver code
document.write(nonFibonacci(5));
// This code is contributed by Mayank Tyagi
</script>
Producción :
10
Complejidad de tiempo: O(n), Espacio auxiliar: O(1)
C++
#include <iostream>
using namespace std;
int main()
{
int i = 0, j = 1, k, m, no, b[10];
// Range is 10
no = 10;
b[1] = 0;
b[2] = 1;
// Check if range is less equals to 1
if (no <= 1) {
cout << "You have enter a wrong range";
}
// check if range is greater than 1
// and less equals to 5
else if (no <= 5 && no > 1) {
cout << "\nThere is not any Non-Fibonacci series "
"that lies between 1 to "
<< no << " term of Fibonacci Series.";
}
// If range is greater than 5
else {
// Loop to calculate fibonacci series till
// range
for (m = 2; m < no; m++) {
k = i + j;
i = j;
j = k;
// Store fibonacci series into b[]
// array
b[m] = k;
}
i = 5;
cout << "\nThe Non-Fibonacci series that lies "
"between 1 to "
<< no << " term of Fibonacci Series is: \n";
// Loop to calculate Non-Fibonacci
// series
for (int ans = 4; ans < b[no - 1]; ans++) {
if (ans != b[i])
// Print Non-Fibonacci Series
cout << ans << " ";
else
i++;
}
}
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i = 0, j = 1, k, m, no, b[10];
// Range is 10
no = 10;
b[1] = 0;
b[2] = 1;
// Check if range is less equals to 1
if (no <= 1) {
printf("You have enter a wrong range");
}
// check if range is greater than 1 and less equals to 5
else if (no <= 5 && no > 1) {
printf("\nThere is not any Non-Fibonacci series "
"that lies between 1 to %d term of "
"Fibonacci Series.",
no);
}
// If range is greater than 5
else {
// Loop to calculate fibonacci series till range
for (m = 2; m < no; m++) {
k = i + j;
i = j;
j = k;
// Store fibonacci series into b[] array
b[m] = k;
}
i = 5;
printf(
"\nThe Non-Fibonacci series that lies between "
"1 to %d term of Fibonacci Series is: \n",
no);
// Loop to calculate Non-Fibonacci series
for (int ans = 4; ans < b[no - 1]; ans++) {
if (ans != b[i])
// Print Non-Fibonacci Series
printf("%d ", ans);
else
i++;
}
}
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
int[] holes = {21, 3, 6};
int i = 0, j = 1, k, m, no;
int[] b = new int[10];
// Range is 10
no = 10;
b[1] = 0;
b[2] = 1;
// Check if range is less equals to 1
if (no <= 1) {
System.out.print("You have enter a wrong range");
}
// check if range is greater than 1
// and less equals to 5
else if (no <= 5 && no > 1) {
System.out.print("\n" + "There is not any Non-Fibonacci series that lies between 1 to" + no +
" term of Fibonacci Series.");
}
// If range is greater than 5
else {
// Loop to calculate fibonacci series till
// range
for (m = 2; m < no; m++) {
k = i + j;
i = j;
j = k;
// Store fibonacci series into b[]
// array
b[m] = k;
}
i = 5;
System.out.println("\n" + "The Non-Fibonacci series that lies between 1 to "
+ no + " term of Fibonacci Series is: "+ "\n");
// Loop to calculate Non-Fibonacci
// series
for (int ans = 4; ans < b[no - 1]; ans++) {
if (ans != b[i])
// Print Non-Fibonacci Series
System.out.print(ans + " ");
else
i++;
}
}
}
// This Solution is contributed by shinjanpatra.
Python3
i = 0
j = 1
b = []
no = 10 # Range is 10
b.append(0)
b.append(1)
if(no <= 1): # Check if range is less equals to 1
print("You have enter a wrong range...")
elif(no <= 5 and no > 1): # check if range is greater than 1 and less equals to 5
print("\nThere is not any Non-Fibonacci series that lies between 1 to ",
no, " term of Fibonacci Series.")
else: # If range is greater than 5
for m in range(2, no): # Loop to calculate fibonacci series till range
k = i+j
i = j
j = k
b.append(k) # Store fibonacci series into list b
i = 5
print("\nThe Non-Fibonacci series that lies between 1 to ",
no, " term of Fibonacci Series is:")
for ans in range(4, b[no-1]): # Loop to calculate Non-Fibonacci series
if ans != b[i]:
print(ans, end=" ") # Print Non-Fibonacci Series
else:
i = i+1
C#
// C# code to implement the approach
using System;
class GFG {
public static void Main(string[] args)
{
int[] holes = { 21, 3, 6 };
int i = 0, j = 1, k, m, no = 10;
int[] b = new int[10];
// Range is 10
b[1] = 0;
b[2] = 1;
// Check if range is less equals to 1
if (no <= 1) {
Console.Write("You have enter a wrong range");
}
// check if range is greater than 1
// and less equals to 5
else if (no <= 5 && no > 1) {
Console.Write(
"\n"
+ "There is not any Non-Fibonacci series that lies between 1 to"
+ no + " term of Fibonacci Series.");
}
// If range is greater than 5
else {
// Loop to calculate fibonacci series till
// range
for (m = 2; m < no; m++) {
k = i + j;
i = j;
j = k;
// Store fibonacci series into b[]
// array
b[m] = k;
}
i = 5;
Console.WriteLine(
"\n"
+ "The Non-Fibonacci series that lies between 1 to "
+ no + " term of Fibonacci Series is: ");
// Loop to calculate Non-Fibonacci
// series
for (int ans = 4; ans < b[no - 1]; ans++) {
if (ans != b[i])
// Print Non-Fibonacci Series
Console.Write(ans + " ");
else
i++;
}
}
}
}
// This Solution is contributed by phasing17
Javascript
<script>
// driver code
let i = 0, j = 1, k, m, no, b = new Array(10);
// Range is 10
no = 10;
b[1] = 0;
b[2] = 1;
// Check if range is less equals to 1
if (no <= 1) {
console.log("You have enter a wrong range");
}
// check if range is greater than 1
// and less equals to 5
else if (no <= 5 && no > 1) {
document.write("</br>","There is not any Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series.");
}
// If range is greater than 5
else {
// Loop to calculate fibonacci series till
// range
for (m = 2; m < no; m++) {
k = i + j;
i = j;
j = k;
// Store fibonacci series into b[]
// array
b[m] = k;
}
i = 5;
document.write("</br>","The Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series is: ","</br>");
// Loop to calculate Non-Fibonacci
// series
for (let ans = 4; ans < b[no - 1]; ans++) {
if (ans != b[i])
// Print Non-Fibonacci Series
document.write(ans , " ");
else
i++;
}
}
// This code is contributed by shinjanpatra
</script>
Producción
The Non-Fibonacci series that lies between 1 to 10 term of Fibonacci Series is: 4 6 7 9 10 11 12 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33
Complejidad de tiempo: O(n), Espacio auxiliar: O(n)
El problema y la solución anteriores son aportados por Hemang Sarkar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA