给定一个正整数n，任务是打印第n个非整数 斐波那契数 .斐波那契数的定义如下：
null
Fib(0) = 0Fib(1) = 1for n >1, Fib(n) = Fib(n-1) + Fib(n-2)
前几个斐波那契数是0，1，1，2，3，5，8，13，21，34，55，89，141……。。 例如：
Input : n = 2Output : 6Input : n = 5Output : 10
A. 天真的解决方案 就是找到斐波那契数，然后打印出在找到的斐波那契数中不存在的前n个数。 A. 更好的解决方案 就是用斐波那契数的公式，不断地把两个连续的斐波那契数之间的差距相加。差距之和的值是迄今为止看到的非斐波那契数的计数。下面是上述想法的实现。
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; } |
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> |
输出：
10
时间复杂性： O（n） 辅助空间： O（1） 上述问题和解决方案由 赫曼萨卡 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
