Recurrence Equation

/* 漸化式（nＣrの計算）
n個の中からr個を選ぶ組み合わせの数 nCrを求める.

nCr=(n-r+1)/r nC_{r-1}
nC0=1

0Ｃ0=1  
1Ｃ0=1  1Ｃ1=1  
2Ｃ0=1  2Ｃ1=2  2Ｃ2=1  
3Ｃ0=1  3Ｃ1=3  3Ｃ2=3  3Ｃ3=1  
4Ｃ0=1  4Ｃ1=4  4Ｃ2=6  4Ｃ3=4  4Ｃ4=1  
5Ｃ0=1  5Ｃ1=5  5Ｃ2=10  5Ｃ3=10  5Ｃ4=5  5Ｃ5=1
*/

#include 

long combi(int,int);

main()
{
    int n,r;

    for (n=0;n<=5;n++) {
        for (r=0;r<=n;r++)
            printf("%dＣ%d=%ld  ",n,r,combi(n,r));
        printf("\n");
    }
}
long combi(int n,int r)
{
    int i;
    long p=1;

    for (i=1;i<=r;i++)
        p=p*(n-i+1)/i;
    return p;
}

/* Ｈｏｒｎｅｒの方法 
多項式 f(x)=a_n x^n + a_{n-1}x^{n-1}+ ... + a_1x+a_0
の値を Hornerの方法を用いて計算する。

f_i=f_{i-1}x+a_{n-i}
f_0=a_n

fn(1.000000)=15.000000
fn(2.000000)=129.000000
fn(3.000000)=547.000000
fn(4.000000)=1593.000000
fn(5.000000)=3711.000000

f(x)=5x^4+4x^3+3x^2+2x+1

*/

#include 

double fn(double,double *,int);

main()
{
    static double a[]={1,2,3,4,5};    /* 係数 */
    double x;

    for (x=1;x<=5;x++)
        printf("fn(%f)=%f\n",x,fn(x,a,4));
}
double fn(double x,double a[],int n)
{
    double p;
    int i;

    p=a[n];
    for (i=n-1;i>=0;i--)
        p=p*x+a[i];
    return p;
}

/* Ｐａｓｃａｌの三角形 

nCr={n-1}_C_{r-1}+{n-1}_C_r
                                     1   
                                   1     1   
                                1     2     1   
                             1     3     3     1   
                          1     4     6     4     1   
                       1     5    10    10     5     1   
                    1     6    15    20    15     6     1   
                 1     7    21    35    35    21     7     1   
              1     8    28    56    70    56    28     8     1   
           1     9    36    84   126   126    84    36     9     1   
        1    10    45   120   210   252   210   120    45    10     1   
     1    11    55   165   330   462   462   330   165    55    11     1   
  1    12    66   220   495   792   924   792   495   220    66    12     1  
*/

#include 
#define N 12

long combi(int,int);

main()
{
    int n,r,t;

    for (n=0;n<=N;n++){
        for (t=0;t<(N-n)*3;t++)        /* 空白 */
            printf(" ");
        for (r=0;r<=n;r++)
            printf("%3ld   ",combi(n,r));
        printf("\n");
    }
}
long combi(int n,int r)
{
    int i;
    long p=1;

    for (i=1;i<=r;i++)
        p=p*(n-i+1)/i;
    return p;
}

Back to C Language