Kodeerimisharjutus – trepist üles ronimine – Fibonacci numbrid – C++ – võrgukohtunik

Küsimus: Ronite trepist. Tippu jõudmiseks kulub n sammu. Iga kord saate teha 1 või 2 sammu. Kui palju erinevaid viise tippu jõudmiseks?

Probleemi kirjeldus: http://oj.leetcode.com/problems/climbing-stairs/

See probleem võib esmapilgul tunduda keeruline, kuid kui te hetkeks järele mõtlete, võib see osutuda nii lihtsaks. Vastus on Fibonacci numbrid (vt siit, siit )

Algsed Fibonacci numbrid on määratletud jadadena:

Selle probleemi lahendamiseks peame lihtsalt veidi muutma:

ja kuna ainult 1 sammu jaoks on ainult 1 eristatav viis ja 2 sammu jaoks, on meil kaks lahendust: 1 + 1 või 2.

Ülejäänud on nagu Fibonacci seeria. Sest praegusest positsioonist oleme tõenäoliselt kahest eelmisest positsioonist, F(n-1) ja F(n-2) .

Võite kasutada rekursiooni, kuid seda saab lahendada tõhusama iteratiivse lahendusega.

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

Või eelistate lihtsamat rekursiivset funktsiooni:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Märkus. Rekursiiv annab  testis 44 väärtuse TIME LIMIT EXCEEDED. Seda seetõttu, et rekursiivne funktsioon arvutab tavaliselt vaheväärtusi mitu korda. Näiteks , .  arvutatakse kaks korda.