Using the recurrent relation comb( n, m ) = comb( n-1, m ) + comb( n-1, m-1 ) we can write recursive function:
Code: Select all
int comb( n, m )
{
if( n == 1 || m == 0 || n == m )
return 1;
else
return comb( n-1, m ) + comb( n-1, m-1 );
}
Here is the complete program:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
int comb( int, int );
int comb2( int, int );
int comb3( int, int );
typedef struct cell {
int x, m, n, ret_add;
} cell;
typedef struct cell_stack {
cell c;
struct cell_stack *next;
} cell_stack;
void push_stack( cell, cell_stack ** );
cell top_stack( cell_stack * );
void pop_stack( cell_stack ** );
int empty_stack( cell_stack * );
void new_stack( cell_stack ** );
typedef struct cell2 {
int x, ret_add;
} cell2;
typedef struct cell_stack2 {
cell2 c;
struct cell_stack2 *next;
} cell_stack2;
void push_stack2( cell2, cell_stack2 ** );
cell2 top_stack2( cell_stack2 * );
void pop_stack2( cell_stack2 ** );
int empty_stack2( cell_stack2 * );
void new_stack2( cell_stack2 ** );
int main()
{
int m, n;
printf( "Input n: " );
scanf( "%d", &n );
if( n < 0 ) {
printf( "Wrong input\n" );
return 1;
}
printf( "Input m: " );
scanf( "%d", &m );
if( m < 0 || n < m ) {
printf( "Wrong input\n" );
return 1;
}
printf( "comb( n, m ) = %d\n" , comb( n, m ) );
printf( "comb2( n, m ) = %d\n" , comb2( n, m ) );
printf( "comb3( n, m ) = %d\n" , comb3( n, m ) );
return 0;
}
int comb( int n, int m )
{
if( n == 1 || m == 0 || m == n )
return 1;
else
return comb( n - 1, m ) + comb( n - 1, m - 1 );
}
int comb2( int n, int m )
{
cell cel;
int ret_val;
cel.n = n;
cel.m = m;
cel.ret_add = 0;
cell_stack *s;
new_stack( &s );
push_stack( cel, &s );
do {
cel = top_stack( s );
pop_stack( &s );
switch( cel.ret_add ) {
case 0:
if( cel.n == 1 || cel.m == 0 || cel.n == cel.m ) {
ret_val = 1;
break;
}
else {
cel.ret_add = 1;
push_stack( cel, &s );
(cel.n)--;
cel.ret_add = 0;
push_stack( cel, &s );
break;
}
case 1:
cel.x = ret_val;
cel.ret_add = 2;
push_stack( cel, &s );
(cel.n)--;
(cel.m)--;
cel.ret_add = 0;
push_stack( cel, &s );
break;
case 2:
ret_val += cel.x;
break;
}
} while( ! empty_stack( s ) );
return ret_val;
}
void push_stack( cell c, cell_stack **s_p )
{
cell_stack *tmp = malloc( sizeof( cell_stack ) );
tmp->next = *s_p;
tmp->c = c;
*s_p = tmp;
}
void new_stack( cell_stack **s_p )
{
*s_p = NULL;
}
cell top_stack( cell_stack *s )
{
return s->c;
}
void pop_stack( cell_stack **s_p )
{
cell_stack *tmp = *s_p;
*s_p = (*s_p)->next;
free( tmp );
}
int empty_stack( cell_stack *s )
{
if( s == NULL )
return 1;
else
return 0;
}
int comb3( int n, int m )
{
cell2 cel;
int ret_val = 0;
cel.ret_add = 0;
cell_stack2 *s;
new_stack2( &s );
push_stack2( cel, &s );
do {
cel = top_stack2( s );
pop_stack2( &s );
switch( cel.ret_add ) {
case 0:
if( n == 1 || m == 0 || n == m ) {
ret_val = 1;
break;
}
else {
cel.ret_add = 1;
push_stack2( cel, &s );
n--;
cel.ret_add = 0;
push_stack2( cel, &s );
break;
}
case 1:
cel.x = ret_val;
cel.ret_add = 2;
push_stack2( cel, &s );
m--;
cel.ret_add = 0;
push_stack2( cel, &s );
break;
case 2:
ret_val += cel.x;
n++;
m++;
break;
}
} while( ! empty_stack2( s ) );
return ret_val;
}
void push_stack2( cell2 c, cell_stack2 **s_p )
{
cell_stack2 *tmp = malloc( sizeof( cell_stack2 ) );
tmp->next = *s_p;
tmp->c = c;
*s_p = tmp;
}
void new_stack2( cell_stack2 **s_p )
{
*s_p = NULL;
}
cell2 top_stack2( cell_stack2 *s )
{
return s->c;
}
void pop_stack2( cell_stack2 **s_p )
{
cell_stack2 *tmp = *s_p;
*s_p = (*s_p)->next;
free( tmp );
}
int empty_stack2( cell_stack2 *s )
{
if( s == NULL )
return 1;
else
return 0;
}