Jasiu wchodzi po schodach - zadanie na rekurencję C++

1

Cześć wszystkim!
Już od jakiegoś czasu śledzę to forum. Do tej pory bardzo dużo z niego wyciągnąłem. Niestety mam problem z pewnym zadaniem na algorytmy.

  • Jasiu wchodzi po schodach po 1, 2 lub 3 stopnie. Użytkownik programu podaje ile jest stopnie. Program ma wypisać wszystkie możliwe kombinacje wejścia po schodach oraz ile tych kombinacji jest. Np 5-> 1+1+1+1+1, 2+3, 3+2, 1+2+1+1 itd.*

Za cholerę nie wiem jak się za to zabrać, może jest ktoś chętny do pomocy? Zadanie trzeba rozwiązać rekurencyjnie, a to jest moja najsłabsza w tej chwili strona :/

Z góry dziękuję za pomoc

1

No możesz tu walnąć taką trywialną rekurencje:

def fun(n):
    rec(n, 0)


def rec(n, k):
    if n > 0:
        for i in range(1, 4):
            if n-i >= 0:
                print("  " * k + str(i))
                rec(n - i, k + 1)


fun(5)

Popatrz na to od końca -> jeśli Jasiu stoi na schodzie k to mógł tam dojść przeskakując o 1 stopień z k-1, albo o 2 stopnie z k-2 albo o 3 stopnie z k-3. Więc wszystkie możliwości to właśnie wypisanie 1 plus wszystkich możliwości dojścia do schodu k-1, wypisanie 2 oraz możliwości dojścia do k-2 a także 3 i możliwości dojścia do k-3.

To nam wypisze takie śmieszne drzewko:

1
  1
    1
      1
        1
      2
    2
      1
    3
  2
    1
      1
    2
  3
    1
2
  1
    1
      1
    2
  2
    1
  3
3
  1
    1
  2
0

Tak, jak zazwyczaj się podchodzi do zadań rekurencję: wyobraź sobie, że masz pod ręką wróżkę, która Ci może powiedzieć, ile jest rozwiązań dla każdej konkretnej wartości mniejszej, niż masz teraz i na podstawie tego chcesz odpowiedzieć, ile jest rozwiązań dla Twojej wartości.

W tym przypadku na n-ty stopień możemy się dostać idąc na n-1 i idąc o jeden, na n-2 i idąc o dwa albo na n-3 i idąc o trzy.

Ostatecznie, schody[n] = schody[n-1] + "+1", schody[n-2] + "+2", schody[n-3] + "+3". Pozostaje zakodzić.

0

@Shalom:
Nie wiem czy dobrze to napisałem:

 int jas(int n)
{
    if(n>0)
    {
        for(int i=1; i<=3; i++)
        {
            cout << i;
            return jas(n-1);
        }
    }

}

Tak?

@Althorion
O co chodzi z tym +"+1"?

0

Nie no aż tak prosto nie jest, bo teraz wypisujesz sobie i ale skaczesz w dół zawsze o 1 a powinieneś o i ;) No i taka trywialna funkcja to raczej żeby zobrazować rozwiązanie, bo jak chcesz te wszystkie możliwości sensownie wypisać to trzeba je jednak sobie zbierać gdzieś a nie tylko wypisywać ;) No i to ci niezbyt ładnie wypisze. Tam wyżej w kodzie dodałem sobie zmienną która mówi ile spacji wcięcia zrobić, żeby coś było widać ;]

0

Kurcze, wiem, że to trochę może zabrzmieć jak lenistwo, ale czy byłby ktoś tak dobry i napisał choć kawałem tego kodu? Ledwo zaczęliśmy rekurencję, a już takie zadanie dostałem. Nie mam zielonego pojęcia w co ręce włożyć. To nie lenistwo - to bezradność :/

0

@Althorion
O co chodzi z tym +"+1"?

Wypisywałeś rozwiązania w postaci stringów, np. "1+1+1+1+1", to Ci napisałem w pseudokodzie coś, co miało oznaczać „weź istniejące stringi i do każdego z nich dopisz na końcu +1”.

0
#include <iostream>
using namespace std;

void schodki(int n,int do_tablicy,int &licznik, int tab[],int &j);

int main()
{
    int tab[20]={0}, do_tablicy=0, licznik=0, n=0, j=0;
    cout<<"ILE SCHODOW? : ";
    cin>>n;
    j=n;
    schodki(n, do_tablicy,licznik,tab,j);
    cout<<"  Sposobow: "<<licznik;
    return 0;
}

void schodki(int n,int do_tablicy,int &licznik, int tab[],int &j)
{
        if(n>=3)                   /*          POCZATEK WARUNKOW   */
        {
            tab[do_tablicy]=3;
            schodki(n-3,do_tablicy+1,licznik,tab,j);
        }
        if(n>=2)
        {                                                                                   /*          ZAPISUJE DO TABLICY DANY KROK PO  CZYM         */
            tab[do_tablicy]=2;                                                           /*           WYWOLUJE FUNKCJEOD NOWA AZ DO ZERA         */
            schodki(n-2,do_tablicy+1,licznik,tab,j);
        }
        if(n>=1)
        {
            tab[do_tablicy]=1;
            schodki(n-1,do_tablicy+1,licznik,tab,j);
        }
                                        /*          KONIEC WARUNKOW   */

        if(n<=0)                                                                           /* W ZERZE DZIEJE SIE NAJWIECEJ BO PRAKTYCZNIE */
        {                                                                                        /* CIAGLE JEST WYWOLYWANY TEN WARUNEK */
            int pomoc=0;
            licznik++;
        for(int i=0; pomoc<j; i++)                        // " j "zapamietuje ile bylo schodow i wykorzystuje to w petli ktora wyswietla elementy jednego przypadku
            {
            cout<<tab[i];
            pomoc+=tab[i];

            }
                cout<<endl;
        }


}

To działa

1 użytkowników online, w tym zalogowanych: 0, gości: 1