斐波那契数列及返回问题？

Question

我正在学习C++，之前已经开始学习Python编程。这是一个简单的程序，用来计算两个值a和b之间的斐波那契数。不过，当我运行代码时，只打印出了数字1，我搞不清楚为什么。我觉得这可能和在for循环里使用return有关。希望能得到一些帮助。

#include <iostream>
using namespace std;

int fibo(int b,int a=0){
    int x=0;
    int y=1;
    for(int i=0; i<=b; i++){
        int x0=x;
        int z=x+y;
        x=y;
        y=z;
        if(x>a){
            return x0;
        }
    }
}

int main()
{
    cout << fibo(100)<<endl;
    return 0;
}

这里是Python的函数，供参考

def fibo(b,a=0):
    x=0
    y=1
    while x<=b:
        z=x+y
        x0=x
        x=y
        y=z
        if x>a:
            print x0

我在C++中也尝试了以下代码

#include <iostream>
using namespace std;

int fibo(int b,int a=0){
    int x=0;
    int y=1;
    for(int i=0; i<=b; i++){
        int x0=x;
        int z=x+y;
        x=y;
        y=z;
        if(x>a){
            cout << x0 <<endl;
        }
    }
}

int main()
{
    fibo(100);
    return 0;
}

不过这段代码输出的斐波那契数超过了b的值

Answer 1

试试这个：

#include <iostream>
using namespace std;

int fibo(int b,int a=0){
    int x=0;
    int y=1;

    while(x<=b)
    {
        int z=x+y;
        int x0=x;
        x=y;
        y=z;
        if(x>a && x<b)
        {
            cout << x << " ";
        }
    }
}

int main()
{
    fibo(100);
    return 0;
}

http://ideone.com/225KIY

Answer 2

通常用来计算某个limit的数学（递归）方法（这并不一定是最好的或最高效的方法！）：可以在这里查看演示 这里

#include <iostream>
using namespace std;

int fibo(int x) 
{
    if (x == 0) return 0;
    if (x == 1) return 1;

    return fibo(x-1)+fibo(x-2);
}

int main()
{
int j=1,limit=100;

    do
    {
    cout<< fibo(j) <<'\t';
    ++j;
    } while(fibo(j)<=limit);

    return 0;
}

Answer 3

这是你代码从Python转到C++的具体版本

#include <iostream>

using namespace std;

void fibo(int b,int a=0){
    int x=0;
    int y=1;
    int z, x0;
    while( x <= b ) {
        z= x + y;
        x0 = x;
        x = y;
        y = z;
        if(x > a) {
            cout << x0 << endl;
        }
    }
}

int main()
{
    fibo(100);
    return 0;
}

在你的Python代码中，如果没有明确的返回值，函数的默认返回值是None。在C++中，这相当于一个void函数。

你的for循环为什么不工作？

for循环是用来重复执行一定次数的。它的语法是：

for (initialization; condition; increase) statement;

和while循环一样，这个循环会在条件为真的时候重复执行语句。不过，for循环还提供了特定的可选位置，用来放初始化和增加的表达式，这些表达式会在循环第一次开始之前执行，并在每次循环结束后执行。

1. 初始化会被执行。通常，这里会声明一个计数器变量，并将其设置为某个初始值。这一步只会在循环开始时执行一次。
2. 检查条件。如果条件为真，循环继续；否则，循环结束，跳过语句，直接进入第5步。
3. 执行语句。和往常一样，这可以是一个单独的语句，也可以是用大括号{ }包围的一块代码。
4. 执行增加，然后循环回到第2步。
5. 循环结束：执行继续到它后面的下一个语句。

想了解更多，可以查看这里：http://www.cplusplus.com/doc/tutorial/control/#for.

现在我们来分析一下你的循环：

int x=0;    // initialize x to 0
int y=1;    // initialize y to 1
for(        
  int i=0;  // initialize i to 0
  i<=b;     // keep looping until i is less than or equal to b (a variable passed in)
  i++       // after every single loop iteration, increment i by 1
) {  
    int x0=x;  // initialize x0 to x
    int z=x+y; // initialize z to (x + y)
    x=y;       // assign the value of y to x
    y=z;       // assign the value of z to y
    if(x>a){   // if x is greater than a, print the value of x0
        cout << x0 <<endl;
    }
}

在你的Python代码中，你没有使用i，而是用x作为你的循环不变式。所以这应该是你for循环的condition：x <= b。初始化部分应该是你在循环之前设置的变量，所以：int x = 0, y = 1, x0, z应该是initialization。最后一部分是增加。在你的Python代码中，增加是x = y，但在for循环中，这部分是在每次循环结束后执行的，所以我们不能直接在for循环的增加部分写x = y，因为y = z是在增加之前执行的。我们可以用一点代数：z = y + x，这样我们就可以通过z - x来得到y的值。

这就形成了for循环：

void fibo2(int b,int a=0){
    for(
        int x = 0, y = 1, x0, z;
        x <= b;
        x = (z-x)
    ) {
        x0 = x;
        z = x+y;
        y = z;
        if(x > a){
            cout << x0 <<endl;
        }
    }
}

希望这对你有帮助。