Решение задачи Мячик на лестнице с Acmp

Без пояснения   Просмотров: 24


На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через две. То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.

Требуется написать программу, которая определит число всевозможных "маршрутов" мячика с вершины на землю.

Код

#include <bits/stdc++.h>
 
using namespace std;
string sumStr(string a,string b)
{
    string r, tt;
    if(b.size() > a.size())
        return sumStr(b, a);
    while(b.size() < a.size())
        b.insert(0,"0");
    int t = 0;
 
    for(int i = b.size() - 1; i >= 0; --i){
        t += a[i] + b[i] - 96;
        tt = t % 10 + 48;
        r.insert(0,tt);
        t/=10;
    }
    if(t)
        while(t){
            tt = t % 10 + 48;
            r.insert(0,tt);
            t/=10;
        }
    return r;
}
int main()
{
    int n;
    cin >> n;
    vector<string> a;
    a.push_back("1");
    a.push_back("2");
    a.push_back("4");
    for(int i = 3; i < n; ++i){
        string s = sumStr(a[i - 1],a[i - 2]);
        string s1 =  sumStr(s,a[i - 3]);
        a.push_back(s1);
    }
    cout << a[n - 1];
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться