[C]Rekurencyjnie - Symbol Newtona

[Mikser]

Witam,
Mam program, który rekurencyjnie oblicza wartość symbolu Newtona, prezentuję się on tak:

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>

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


int main()
{
    int n1;
    int k1;
    printf("If you want to calculate the value of Newton's symbole enter  number 'n' and number 'k'\n\n");
    scanf("%d %d",&n1,&k1);
    int x=newton(n1,k1);
    printf("n=%d\nk=%d\n",n1,k1);
    printf("The value of Newton's symbole for %d and %d is %d\n",n1,k1,x);

    system("pause");
    return 0;
}

Mój problem polega na tym, że kompletnie nie wiem jak to działa.
Mógłby ktoś wytłumaczyć to w ten sposób:

Jest to graficzne przedstawienie dla rekurencyjnego obliczania silni i rozumiem jak to działa w tym wypadku, natomiast symbol newtona jest dla mnie czarną magią.

Z góry dziękuję za pomoc

[kalwi]

Po pierwsze, nikt nie będzie ci tego graficznie rozpisywał. Słyszałeś o czymś takim jak debuger? Do takich rzeczy właśnie to służy.

Po drugie:

\(\displaystyle{ C^k_n= \frac{n!}{k!\left( n-k\right)! } =C^{k-1}_{n-1}+C^{k}_{n-1}}\)

[Mikser]

Po pierwsze, nikt nie będzie ci tego graficznie rozpisywał. Słyszałeś o czymś takim jak debuger? Do takich rzeczy właśnie to służy.

Nie liczyłem, że ktoś mi to skrobnie w paincie, tylko na tej zasadzie wyjaśni

W każdym razie, dziękuje za ten wzór
e; ucieło - choć dalej nic z tego nie rozumiem

[kalwi]

A czy tak ciężko wpaść na to, w jaki sposób to sprawdzić?

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>

int newton(int n, int k)
{
    if(n == 0)
    {
        printf("n == 0, k == %d, zwracam 1\n\n", k);
        return 1;
    }
    else if(n == k)
    {
        printf("n == k == %d, zwracam 1\n\n", n);
        return 1;
    }
    else if(k == 0)
    {
        printf("n == %d, k == 0, zwracam 1\n\n", n);
        return 1;

    }
    else
    {
        printf("n = %d, k = %d\nwywolaj newton(%d, %d) + newton(%d,%d)\n\n", n,k,n-1,k-1,n-1,k);
        return newton(n-1, k-1) + newton(n-1, k);
    }
}


int main(void)
{
    printf("The value of Newton's symbole for %d and %d is %d\n", 5, 3, newton(5,3));
    return 0;
}

Kod: Zaznacz cały

n = 5, k = 3
wywolaj newton(4, 2) + newton(4,3)

n = 4, k = 2
wywolaj newton(3, 1) + newton(3,2)

n = 3, k = 1
wywolaj newton(2, 0) + newton(2,1)

n == 2, k == 0, zwracam 1

n = 2, k = 1
wywolaj newton(1, 0) + newton(1,1)

n == 1, k == 0, zwracam 1

n == k == 1, zwracam 1

n = 3, k = 2
wywolaj newton(2, 1) + newton(2,2)

n = 2, k = 1
wywolaj newton(1, 0) + newton(1,1)

n == 1, k == 0, zwracam 1

n == k == 1, zwracam 1

n == k == 2, zwracam 1

n = 4, k = 3
wywolaj newton(3, 2) + newton(3,3)

n = 3, k = 2
wywolaj newton(2, 1) + newton(2,2)

n = 2, k = 1
wywolaj newton(1, 0) + newton(1,1)

n == 1, k == 0, zwracam 1

n == k == 1, zwracam 1

n == k == 2, zwracam 1

n == k == 3, zwracam 1

The value of Newton's symbole for 5 and 3 is 10

-- 26 lis 2016, o 01:22 --

A nawet masz, zerknij sobie: