Lab Test II : Solution
For students with odd PC numbers
The program
#include <stdio.h>
#define MAX_N 9
#define ARR_DIM 10
int s[ARR_DIM][ARR_DIM];
int srec(n,k) {
if (k > n) return (0);
if (k==0) return ( (n==0) ? 1 : 0 );
return((n-1)*srec(n-1,k)+srec(n-1,k-1));
}
void siter () {
int n, k;
for (n=0; n<=MAX_N; ++n) for (k=0; k<=n; ++k) {
if (k==0) s[n][k] = ((n==0) ? 1 : 0);
else if (k==n) s[n][k] = s[n-1][k-1];
else s[n][k] = (n-1)*s[n-1][k]+s[n-1][k-1];
}
}
int main ()
{
int n, k;
printf("Recursive method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" s(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",srec(n,k));
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
printf("Iterative method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" s(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
siter();
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",s[n][k]);
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
}
Output
Recursive method
n | s(n,0) s(n,1) s(n,2) s(n,3) s(n,4) s(n,5) s(n,6) s(n,7) s(n,8) s(n,9)
---+-----------------------------------------------------------------------
0 | 1
1 | 0 1
2 | 0 1 1
3 | 0 2 3 1
4 | 0 6 11 6 1
5 | 0 24 50 35 10 1
6 | 0 120 274 225 85 15 1
7 | 0 720 1764 1624 735 175 21 1
8 | 0 5040 13068 13132 6769 1960 322 28 1
9 | 0 40320 109584 118124 67284 22449 4536 546 36 1
---------------------------------------------------------------------------
Iterative method
n | s(n,0) s(n,1) s(n,2) s(n,3) s(n,4) s(n,5) s(n,6) s(n,7) s(n,8) s(n,9)
---+-----------------------------------------------------------------------
0 | 1
1 | 0 1
2 | 0 1 1
3 | 0 2 3 1
4 | 0 6 11 6 1
5 | 0 24 50 35 10 1
6 | 0 120 274 225 85 15 1
7 | 0 720 1764 1624 735 175 21 1
8 | 0 5040 13068 13132 6769 1960 322 28 1
9 | 0 40320 109584 118124 67284 22449 4536 546 36 1
---------------------------------------------------------------------------
For students with even PC numbers
The program
#include <stdio.h>
#define MAX_N 9
#define ARR_DIM 10
int S[ARR_DIM][ARR_DIM];
int Srec(n,k) {
if (k > n) return (0);
if (k==0) return ( (n==0) ? 1 : 0 );
return(k*Srec(n-1,k)+Srec(n-1,k-1));
}
void Siter () {
int n, k;
for (n=0; n<=MAX_N; ++n) for (k=0; k<=n; ++k) {
if (k==0) S[n][k] = ((n==0) ? 1 : 0);
else if (k==n) S[n][k] = S[n-1][k-1];
else S[n][k] = k*S[n-1][k]+S[n-1][k-1];
}
}
int main ()
{
int n, k;
printf("Recursive method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" S(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",Srec(n,k));
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
printf("Iterative method\n");
printf(" n | ");
for (k=0; k<=MAX_N; ++k) printf(" S(n,%d)",k);
printf("\n---+");
for (k=0; k<=7*(MAX_N+1); ++k) printf("-");
printf("\n");
Siter();
for (n=0; n<=MAX_N; ++n) {
printf("%2d |", n);
for (k=0; k<=n; ++k)
printf("%7d",S[n][k]);
printf("\n");
}
for (k=0; k<=4+7*(MAX_N+1); ++k) printf("-");
printf("\n\n");
}
Output
Recursive method
n | S(n,0) S(n,1) S(n,2) S(n,3) S(n,4) S(n,5) S(n,6) S(n,7) S(n,8) S(n,9)
---+-----------------------------------------------------------------------
0 | 1
1 | 0 1
2 | 0 1 1
3 | 0 1 3 1
4 | 0 1 7 6 1
5 | 0 1 15 25 10 1
6 | 0 1 31 90 65 15 1
7 | 0 1 63 301 350 140 21 1
8 | 0 1 127 966 1701 1050 266 28 1
9 | 0 1 255 3025 7770 6951 2646 462 36 1
---------------------------------------------------------------------------
Iterative method
n | S(n,0) S(n,1) S(n,2) S(n,3) S(n,4) S(n,5) S(n,6) S(n,7) S(n,8) S(n,9)
---+-----------------------------------------------------------------------
0 | 1
1 | 0 1
2 | 0 1 1
3 | 0 1 3 1
4 | 0 1 7 6 1
5 | 0 1 15 25 10 1
6 | 0 1 31 90 65 15 1
7 | 0 1 63 301 350 140 21 1
8 | 0 1 127 966 1701 1050 266 28 1
9 | 0 1 255 3025 7770 6951 2646 462 36 1
---------------------------------------------------------------------------