Trójkąt Pascala rekurencyjnie

0

Witam

Mam napisać program który wyświetli mi trójkąt Pascala:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
itd

Sam temat trójkąta Pascala jest chyba oczywisty, natomiast problem mam w tym żeby skorzystać z rekurencji. Zrobienie tego iteracyjnie nie stanowi żadnego problemu, ale tutaj zaczynam się gubić.
Przetrzepałem google i forum i niestety nie natknąłem się na rozwiązanie z wykorzystaniem rekurencji. Pls help :)

0

Rekurencyjny wzór na k-element w n-tym wierszu:
f(n,k) = f(n-1,k) + f(n-1,k-1)

0

Wikipedię też przeczytałem i nie prosiłem o ogólny wzór tylko o konkretne rozwiązanie czyli np. funkcję rekurencyjną i jej wywołanie, chociaż jeżeli ktoś się pofatyguje i napisze kompletny kod to też nie będę narzekał :-)

0

Jeżeli podany wzór Ci nie wystarcza toś wielki leń lub dureń.

int f(int n,int k)
{
   if(n==k || n==0)
      return 1;
   if(k==1 || k==n-1)
      return n;
   return f(n-1,k-1)+f(n-1,k);
}
0

@bogdan
czy przypadkiem nie zabrakło w Twoim kodzie else?

0

Nie bo instrukcja return jest skokiem. W związku z czym program w chwili napotkania returna od razu zwraca wartość funkcji.

0

a czy funkcję int można stosować, jeśli chcemy uzyskać jako wartość tablicę (dwuwymiarową chyba)?

0

@bogdan
Wszystko fajnie, napisz jeszcze jak to wywołać, z jakimi wartościami? Kiedy funkcja kończy swoje działanie skoro nie ma żadnego ograniczenia i można ją wywoływać praktycznie w nieskończoność?

A tak nawiasem mówiąc nazywanie kogoś durniem tylko dlatego że czegoś nie rozumie jest drobnym nietaktem.

0

@MR22 napisał

Kiedy funkcja kończy swoje działanie skoro nie ma żadnego ograniczenia i można ją wywoływać praktycznie w nieskończoność?
My chyba patrzymy na inne funkcje.
W pierwszym wierszu wypisz 1
W drugim wierszu wypisz kolejno f(1,0) i f(1,1)
W trzecim wierszu wypisz f(2,0) f(2,1) f(2,2)
.......
W n-tym wierszu wypisz f(n-1,0),f(n-1,1),....,f(n-1,n-1). Możesz funkcję f(n,k) trochę skrócić

int f(int n,int k)
{
   if(n==k || n==0)
      return 1;
   return f(n-1,k-1)+f(n-1,k);
}

P.S. Możesz się czuć urażony, ale moim zdaniem jest to bardzo proste. Jeśli zatem nie rozumiesz, to albo nawet nie próbowałeś, tzn. jest leniem, albo próbowałeś ...

0

@bogdan
z tego co rozumiem to trzeba ta funkcję wywoływać iteracyjnie tak?
Czyli cos w stylu:
for(int i=0; i<iloscWierszy; i++)
{
for(int j=0; j<iloscKolumn; j++)
printf("Element trójkąta: %d", f(i,j));
}

Czy tak wyglądałoby wywołanie tej funkcji?

0

Tak. Zadbaj o odstępy między liczbami w jednym wierszu, i zapewnij by po zmianie wartości zmiennej i przejść do nowego wiersza na ekranie.

0

Czyli w zasadzie wywołanie trójkąta pascala w sposób rekurencyjny opiera się w pewnym stopniu o iterację?
Bo własnie tak to zrobiłem.

Teraz małe zapytanie: czy funkcji rekurencyjnej nie powinno się używać w celu przyspieszenia pracy programu? Bo w przypadku tego zadania, wykorzystanie funkcji rekurencyjnej ma charakter raczej ćwiczeniowy. Przecież w rekurencji dla 3 elementu w 10 wierszu program najpierw cofa się do wiersza 1 (lub drugiego?), a potem znów idzie do przodu, do 10. Wykonuje razem prawie 20 kroków. W wersji iteracyjnej są to 2 kroki dla każdego elementu. Przez co 32 wiersze w ite. robi w 2 sek, a rek. trwa to znacznie dłużej.

0

IMHO rekurencja znacznie spowalnia. I powinna być stosowana tylko do zagadnień, które z natury są rekurencyjne (ciąg Fibonacciego). Przy tworzeniu trójkąta Pascala wielokrotnie liczysz to samo, np. podczas obliczania wyrazu f(5,2) wywołujesz rekurencyjnie f(4,1) i f(4,2), które wcześniej obliczyłeś, a teraz będziesz liczył na nowo. Można by przyspieszyć obliczenia gdyby w jakiejś kolekcji z szybkim dostępem zapamiętywać wszystkie obliczone wartości f(n,k).

0

Czyli w zasadzie wywołanie trójkąta pascala w sposób rekurencyjny opiera się w pewnym stopniu o iterację?

obliczenie elementu stojacego na danej pozycji odbywa sie rekurencyjnie.
wypisanie "wszystkich" elementow trojkata odbywa sie iteracyjnie.

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