Koodausharjoitus – Portaiden kiipeäminen – Fibonacci-numerot – C++ – Online Judge
Kysymys: Kiipeät portaita. Huipulle pääseminen kestää n askelta. Joka kerta voit ottaa 1 tai 2 askelta. Kuinka monta erilaista tapaa päästä huipulle?
Ongelman kuvaus: http://oj.leetcode.com/problems/climbing-stairs/
Tämä ongelma saattaa aluksi näyttää vaikealta, mutta kun ajattelet hetken, saatat löytää sen niin helpoksi. Vastaus on Fibonacci-luvut (katso tästä, täältä )
No, alkuperäiset Fibonacci-luvut määritellään sarjoiksi:
Tätä ongelmaa varten meidän on vain muutettava hieman:
ja koska vain yhdelle vaiheelle on vain yksi erillinen tapa ja kahdelle vaiheelle, meillä on kaksi ratkaisua: 1 + 1 tai 2.
Loput ovat kuin Fibonacci-sarja. Koska nykyisestä sijainnista, olemme mahdollisesti kahdesta edellisestä paikasta, F(n-1) ja F(n-2).
Voit käyttää rekursiota, mutta tämä voidaan ratkaista tehokkaammalla iteratiivisella ratkaisulla.
Tai pidät yksinkertaisemmasta rekursiivisesta funktiosta:
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
Huomautus: Rekursiivinen antaa testissä 44 AIKARAJA YLITTYY. Tämä johtuu siitä, että rekursiivinen funktio yleensä laskee väliarvot monta kertaa. Esimerkiksi , . lasketaan kahdesti.