C++/פונקציות/תרגילים



רקורסיהעריכה

מספרי פיבונאצ'יעריכה

בהנתן ההגדרה הרקורסיבית של מספרי פיבונאצ'י, חשוב על פתרון אינטריבי. כתוב פונקציה לא רקורסיבית שתישם רעיון זה.

פתרון

אחת האפשרויות מוצגת כאן. פתרון זה מבוסס על שמירת האיבר הקודם ולפני הקודם במשתנים f0 ו-f1. כאשר מחושב האיבר הבא (f2) כבר אין צורך באיבר שלפני הקודם וניתן "לזוז" איבר אחד קדימה.

int Fibonacci(int n)
{
    if(n <= 1)
        return n;

    int f0 = 1, f1 = 1;
    for(int i = 2; i < n; i++)
    {
        int f2 = f1 + f2;
        f0 = f1;
        f1 = f2;
    }
    return f1;
}

פתרון נוסף הוא שימוש בנוסחה ישירה לחישוב איברי הסדרה:  


עצרתעריכה

בפרק על לולאות כתבת תוכנית שמחשבת עצרת:  . כתוב פונקציה שתחשב עצרת באמצעות אלגוריתם רקורסיבי.

פתרון
long Factorial(long n)
{
    if(n <= 1)
        return 1;
    else
        return Factorial(n-1)*n;
}