CS13002 Programming and Data Structures, Spring 2002--2003
(SECTION 1/A)

LAB TEST 2 -- Solutions

[ODD]    [EVEN]


For students with odd PC numbers

Part I

The three recursive functions are straightforward rewriting of the inductive definitions of the sequences. We also plan to keep track of the number of calls for each function on each argument value. Let us keep three global auxiliary arrays for that purpose. For this exercise arrays of size 26 suffice. But for allowing the possibility of accepting bigger inputs (n) let us stay prepared for n as big as 99.

int nA[100], nB[100], nC[100];
On every occassion we want to count the numbers of calls, we should reset these counters to zeros. This can be handled by the following routine:
void resetCount ( int n )
{
   int i;

   for (i=0;i<=n;i++) nA[i] = nB[i] = nC[i] = 0;
}
Now one can implement the recursive routines A, B and C easily:
int A ( int n )
{
   nA[n]++;
   if (n==0) return(0);
   if (n==1) return(1);
   return(A(n/3)-2*B(n-2)+C(n));
}

int B ( int n )
{
   nB[n]++;
   if (n==0) return(-1);
   if (n==1) return(0);
   if (n==2) return(1);
   return(n-A(n-1)+C(n-2)-B(n-3));
}

int C ( int n )
{
   nC[n]++;
   if (n==0) return(1);
   return(B(n)-3*C(n/2)+5);
}
For handling [n/2] and [n/3] we have not required any specific truncation commands. The argument n is an integer variable. So n/2 and n/3 actually means integer division, i.e., division followed by truncation. That's what we want!

Part II

This part is a bit tricky. Look at the equations. Our strategy is to set the initial terms forcibly to the values supplied. Then we plan to calculate the next terms using the older values. Suppose that Ai, Bi and Ci are already computed for i=0,...,n-1. In the iterative step we use these values to compute An, Bn and Cn. An depends on Cn (and some Ai and Bj which are already computed). Cn, in turn, depends on Bn (and some older values). Finally, Bn can be computed using older terms that are all available at this point. Thus one must first compute Bn and then Cn and finally An. Incorporating these observations makes the iterative function work correctly.

void iterative ( int n )
{
   int i;
   int a[100], b[100], c[100];

   a[0]=0; a[1]=1;
   b[0]=-1; b[1]=0; b[2] = 1;
   c[0]=1;
   for (i=1;i<=n;i++) {
      if (i>=3) b[i]=i-a[i-1]+c[i-2]-b[i-3];
      c[i]=b[i]-3*c[i/2]+5;
      if (i>=2) a[i]=a[i/3]-2*b[i-2]+c[i];
   }
   printf("a(%2d)=%d, b(%2d)=%d, c(%2d)=%d.\n",n,a[n],n,b[n],n,c[n]);
}

The main() function

The output

n = 25
Recursive method :
A(25)=-137
Number of calls:
A( 0): 4030280 A( 1): 2886293 A( 2): 4030280 A( 3): 1706147 A( 4):  794935
A( 5):  385211 A( 6):  189821 A( 7):   94249 A( 8):   46964 A( 9):   23442
A(10):   11711 A(11):    5853 A(12):    2926 A(13):    1463 A(14):     731
A(15):     366 A(16):     183 A(17):      91 A(18):      46 A(19):      23
A(20):      11 A(21):       6 A(22):       3 A(23):       1 A(24):       1
A(25):       1
B( 0): 7729526 B( 1):17582325 B( 2): 9167077 B( 3): 3699246 B( 4): 1665141
B( 5):  789815 B( 6):  384571 B( 7):  189741 B( 8):   94239 B( 9):   46962
B(10):   23442 B(11):   11711 B(12):    5853 B(13):    2926 B(14):    1463
B(15):     731 B(16):     366 B(17):     183 B(18):      91 B(19):      46
B(20):      23 B(21):      11 B(22):       6 B(23):       3 B(24):       1
B(25):       1
C( 0):14211037 C( 1):14211037 C( 2): 7582327 C( 3): 2929464 C( 4): 1285579
C( 5):  601327 C( 6):  290645 C( 7):  142857 C( 8):   70817 C( 9):   35256
C(10):   17590 C(11):    8785 C(12):    4391 C(13):    2194 C(14):    1097
C(15):     549 C(16):     274 C(17):     137 C(18):      69 C(19):      34
C(20):      17 C(21):       9 C(22):       4 C(23):       2 C(24):       1
C(25):       1
B(25)=105
Number of calls:
A( 0): 3224015 A( 1): 2308886 A( 2): 3224015 A( 3): 1364831 A( 4):  635907
A( 5):  308148 A( 6):  151848 A( 7):   75394 A( 8):   37568 A( 9):   18753
A(10):    9368 A(11):    4682 A(12):    2341 A(13):    1170 A(14):     585
A(15):     293 A(16):     146 A(17):      73 A(18):      37 A(19):      18
A(20):       9 A(21):       5 A(22):       2 A(23):       1 A(24):       1
A(25):       0
B( 0): 6183220 B( 1):14064955 B( 2): 7333188 B( 3): 2959205 B( 4): 1332028
B( 5):  631811 B( 6):  307636 B( 7):  151784 B( 8):   75386 B( 9):   37567
B(10):   18753 B(11):    9368 B(12):    4682 B(13):    2341 B(14):    1170
B(15):     585 B(16):     293 B(17):     146 B(18):      73 B(19):      37
B(20):      18 B(21):       9 B(22):       5 B(23):       2 B(24):       1
B(25):       1
C( 0):11368096 C( 1):11368096 C( 2): 6065470 C( 3): 2343421 C( 4): 1028396
C( 5):  481031 C( 6):  232501 C( 7):  114278 C( 8):   56650 C( 9):   28203
C(10):   14071 C(11):    7028 C(12):    3512 C(13):    1755 C(14):     878
C(15):     439 C(16):     219 C(17):     110 C(18):      55 C(19):      27
C(20):      14 C(21):       7 C(22):       3 C(23):       2 C(24):       1
C(25):       0
C(25)=179
Number of calls:
A( 0): 3224407 A( 1): 2309166 A( 2): 3224407 A( 3): 1364996 A( 4):  635984
A( 5):  308186 A( 6):  151866 A( 7):   75403 A( 8):   37573 A( 9):   18755
A(10):    9369 A(11):    4683 A(12):    2341 A(13):    1170 A(14):     585
A(15):     293 A(16):     146 A(17):      73 A(18):      37 A(19):      18
A(20):       9 A(21):       5 A(22):       2 A(23):       1 A(24):       1
A(25):       0
B( 0): 6183972 B( 1):14066662 B( 2): 7334079 B( 3): 2959565 B( 4): 1332189
B( 5):  631888 B( 6):  307674 B( 7):  151802 B( 8):   75395 B( 9):   37572
B(10):   18755 B(11):    9369 B(12):    4683 B(13):    2341 B(14):    1170
B(15):     585 B(16):     293 B(17):     146 B(18):      73 B(19):      37
B(20):      18 B(21):       9 B(22):       5 B(23):       2 B(24):       1
B(25):       1
C( 0):11369477 C( 1):11369477 C( 2): 6066207 C( 3): 2343705 C( 4): 1028521
C( 5):  481090 C( 6):  232529 C( 7):  114292 C( 8):   56657 C( 9):   28206
C(10):   14073 C(11):    7029 C(12):    3513 C(13):    1755 C(14):     878
C(15):     439 C(16):     219 C(17):     110 C(18):      55 C(19):      27
C(20):      14 C(21):       7 C(22):       3 C(23):       2 C(24):       1
C(25):       1

Iterative method :
a(25)=-137, b(25)=105, c(25)=179.
Mind-boggling, eh -- the number of times the functions are called, especially on smaller argument values. You must have observed a visible delay during the recursive computations, whereas the iterative function returns immediately (under your human perceptions!).


For students with even PC numbers

Part I

The three recursive functions are straightforward rewriting of the inductive definitions of the sequences. We also plan to keep track of the number of calls for each function on each argument value. Let us keep three global auxiliary arrays for that purpose. For this exercise arrays of size 26 suffice. But for allowing the possibility of accepting bigger inputs (n) let us stay prepared for n as big as 99.

int nA[100], nB[100], nC[100];
On every occassion we want to count the numbers of calls, we should reset these counters to zeros. This can be handled by the following routine:
void resetCount ( int n )
{
   int i;

   for (i=0;i<=n;i++) nA[i] = nB[i] = nC[i] = 0;
}
Now one can implement the recursive routines A, B and C easily:
int A ( int n )
{
   nA[n]++;
   if (n==0) return(0);
   if (n==1) return(1);
   return(A(n/2)+B(n)-3*C(n-2));
}

int B ( int n )
{
   nB[n]++;
   if (n==0) return(1);
   return(n-2*B(n/3)+C(n));
}

int C ( int n )
{
   nC[n]++;
   if (n==0) return(-1);
   if (n==1) return(0);
   if (n==2) return(1);
   return(5-A(n-1)+B(n-2)-C(n-3));
}
For handling [n/2] and [n/3] we have not required any specific truncation commands. The argument n is an integer variable. So n/2 and n/3 actually means integer division, i.e., division followed by truncation. That's what we want!

Part II

This part is a bit tricky. Look at the equations. Our strategy is to set the initial terms forcibly to the values supplied. Then we plan to calculate the next terms using the older values. Suppose that Ai, Bi and Ci are already computed for i=0,...,n-1. In the iterative step we use these values to compute An, Bn and Cn. An depends on Bn (and some Ai and Cj which are already computed). Bn, in turn, depends on Cn (and some older values). Finally, Cn can be computed using older terms that are all available at this point. Thus one must first compute Cn and then Bn and finally An. Incorporating these observations makes the iterative function work correctly.

void iterative ( int n )
{
   int i;
   int a[100], b[100], c[100];

   a[0]=0; a[1]=1;
   b[0]=1;
   c[0]=-1; c[1]=0; c[2] = 1;
   for (i=1;i<=n;i++) {
      if (i>=3) c[i]=5-a[i-1]+b[i-2]-c[i-3];
      b[i]=i-2*b[i/3]+c[i];
      if (i>=2) a[i]=a[i/2]+b[i]-3*c[i-2];
   }
   printf("a(%2d)=%d, b(%2d)=%d, c(%2d)=%d.\n",n,a[n],n,b[n],n,c[n]);
}

The main() function

The output

n = 25
Recursive method :
A(25)=823
Number of calls:
A( 0):       0 A( 1): 6689017 A( 2): 4779342 A( 3): 1909675 A( 4):  849225
A( 5):  399308 A( 6):  193424 A( 7):   95162 A( 8):   47195 A( 9):   23502
A(10):   11726 A(11):    5857 A(12):    2928 A(13):    1463 A(14):     731
A(15):     366 A(16):     183 A(17):      91 A(18):      46 A(19):      23
A(20):      11 A(21):       6 A(22):       3 A(23):       1 A(24):       1
A(25):       1
B( 0):15009286 B( 1): 8108518 B( 2): 6900768 B( 3): 2749776 B( 4): 1238632
B( 5):  589301 B( 6):  287609 B( 7):  142098 B( 8):   70630 B( 9):   35211
B(10):   17579 B(11):    8783 B(12):    4391 B(13):    2194 B(14):    1097
B(15):     549 B(16):     274 B(17):     137 B(18):      69 B(19):      34
B(20):      17 B(21):       9 B(22):       4 B(23):       2 B(24):       1
B(25):       1
C( 0): 8310151 C( 1):11639282 C( 2): 8528521 C( 3): 3530809 C( 4): 1621089
C( 5):  778528 C( 6):  381725 C( 7):  189033 C( 8):   94065 C( 9):   46921
C(10):   23433 C(11):   11709 C(12):    5853 C(13):    2926 C(14):    1463
C(15):     731 C(16):     366 C(17):     183 C(18):      91 C(19):      46
C(20):      23 C(21):      11 C(22):       6 C(23):       3 C(24):       1
C(25):       1
B(25)=-721
Number of calls:
A( 0):       0 A( 1): 5350717 A( 2): 3823118 A( 3): 1527599 A( 4):  679317
A( 5):  319416 A( 6):  154725 A( 7):   76123 A( 8):   37752 A( 9):   18800
A(10):    9380 A(11):    4685 A(12):    2342 A(13):    1170 A(14):     585
A(15):     293 A(16):     146 A(17):      73 A(18):      37 A(19):      18
A(20):       9 A(21):       5 A(22):       2 A(23):       1 A(24):       1
A(25):       0
B( 0):12006315 B( 1): 6486213 B( 2): 5520102 B( 3): 2199618 B( 4):  990813
B( 5):  471397 B( 6):  230066 B( 7):  113668 B( 8):   56499 B( 9):   28166
B(10):   14062 B(11):    7026 B(12):    3512 B(13):    1755 B(14):     878
B(15):     439 B(16):     219 B(17):     110 B(18):      55 B(19):      27
B(20):      14 B(21):       7 B(22):       3 B(23):       2 B(24):       1
B(25):       1
C( 0): 6647503 C( 1): 9310563 C( 2): 6822184 C( 3): 2824385 C( 4): 1296751
C( 5):  622765 C( 6):  305351 C( 7):  151213 C( 8):   75245 C( 9):   37533
C(10):   18745 C(11):    9366 C(12):    4682 C(13):    2341 C(14):    1170
C(15):     585 C(16):     293 C(17):     146 C(18):      73 C(19):      37
C(20):      18 C(21):       9 C(22):       5 C(23):       2 C(24):       1
C(25):       1
C(25)=-748
Number of calls:
A( 0):       0 A( 1): 5350679 A( 2): 3823091 A( 3): 1527588 A( 4):  679312
A( 5):  319414 A( 6):  154724 A( 7):   76122 A( 8):   37752 A( 9):   18800
A(10):    9380 A(11):    4685 A(12):    2342 A(13):    1170 A(14):     585
A(15):     293 A(16):     146 A(17):      73 A(18):      37 A(19):      18
A(20):       9 A(21):       5 A(22):       2 A(23):       1 A(24):       1
A(25):       0
B( 0):12006229 B( 1): 6486167 B( 2): 5520062 B( 3): 2199602 B( 4):  990806
B( 5):  471394 B( 6):  230064 B( 7):  113667 B( 8):   56498 B( 9):   28166
B(10):   14062 B(11):    7026 B(12):    3512 B(13):    1755 B(14):     878
B(15):     439 B(16):     219 B(17):     110 B(18):      55 B(19):      27
B(20):      14 B(21):       7 B(22):       3 B(23):       2 B(24):       1
B(25):       0
C( 0): 6647456 C( 1): 9310497 C( 2): 6822134 C( 3): 2824365 C( 4): 1296742
C( 5):  622760 C( 6):  305349 C( 7):  151212 C( 8):   75244 C( 9):   37533
C(10):   18745 C(11):    9366 C(12):    4682 C(13):    2341 C(14):    1170
C(15):     585 C(16):     293 C(17):     146 C(18):      73 C(19):      37
C(20):      18 C(21):       9 C(22):       5 C(23):       2 C(24):       1
C(25):       1

Iterative method :
a(25)=823, b(25)=-721, c(25)=-748.
Mind-boggling, eh -- the number of times the functions are called, especially on smaller argument values. You must have observed a visible delay during the recursive computations, whereas the iterative function returns immediately (under your human perceptions!).


The main() function

int main ()
{
   int i,n;

   printf("n = "); scanf("%d",&n); printf("%d\n",n);
   if (n<0) {
      fprintf(stderr,"Error: I can not handle negative values of n.\n");
      exit(1);
   }

   printf("Recursive method :\n");
   resetCount(n);
   printf("A(%d)=%d\n",n,A(n));
   printf("Number of calls:\n");
   for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");

   resetCount(n);
   printf("B(%d)=%d\n",n,B(n));
   printf("Number of calls:\n");
   for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");

   resetCount(n);
   printf("C(%d)=%d\n",n,C(n));
   printf("Number of calls:\n");
   for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
   for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");

   printf("\nIterative method :\n");
   iterative(n);
}
If the ugly sequence of formatted printf's appears unpleasant to your eyes, you may rewrite main() using two satellite functions as follows:
void printCallOne ( int n , int arrayName[] , char functionName )
{
   int i;

   for (i=0;i<=n;i++)
      printf("%c(%2d):%8d%c",functionName,i,arrayName[i],(i%5==4)?'\n':' ');
   if (i%5!=0) printf("\n");
}

void printCall ( int n )
{
   printCallOne(n,nA,'A');
   printCallOne(n,nB,'B');
   printCallOne(n,nC,'C');
}

int main ()
{
   int i,n;

   printf("n = "); scanf("%d",&n); printf("%d\n",n);
   if (n<0) {
      fprintf(stderr,"Error: I can not handle negative values of n.\n");
      exit(1);
   }

   printf("Recursive method :\n");
   resetCount(n);
   printf("A(%d)=%d\n",n,A(n));
   printCall(n);

   resetCount(n);
   printf("B(%d)=%d\n",n,B(n));
   printCall(n);

   resetCount(n);
   printf("C(%d)=%d\n",n,C(n));
   printCall(n);

   printf("\nIterative method :\n");
   iterative(n);
}


[Course home] [Home]