Message-ID: <36C19FC3.3B6EB459@mbox2.singnet.com.sg>
Date: Wed, 10 Feb 1999 23:03:31 +0800
From: "| õ¿õ | õ¿õ | õ¿õ | õ¿õ |" <cdman AT mbox2 DOT singnet DOT com DOT sg>
X-Mailer: Mozilla 4.03 [en] (Win95; I)
MIME-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Need help with recursion??
Content-Type: multipart/mixed; boundary="------------D57A3336A6494214D8FEEF6D"
Reply-To: djgpp AT delorie DOT com

This is a multi-part message in MIME format.
--------------D57A3336A6494214D8FEEF6D
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Hi there,
            I never learn recursion yet but i am required to use it in
my project, therefore asking for help. my program  can calculate the
determinant up to 4 order, using determinant and cramer's rule. But I
need to use recursion to calculate any order of the determinant using
both method. Attached, is a my C++ program code, hope that someone
will help me with it. I only learn the basic to 2-d array as argument,
nothing more than that.

--------------D57A3336A6494214D8FEEF6D
Content-Type: text/plain; charset=us-ascii; name="project.cpp"
Content-Disposition: inline; filename="project.cpp"
Content-Transfer-Encoding: 7bit

/* cramer's rule and determinant program with comments */



#include <stdio.h>

#include <conio.h>



float det[5][5] = {{0}};

/* this is the main determinant array which also facilitates the inclusion for the constant

in case of cramers rule  */



float det33[3][3],det44[4][4];

/* these are two arrays for the 3rd and 4th order determinants */



float det_val=0;

/* this is the determinant value i.e. the final answer */



int order,i,j,choice;

/*order=order of determinant..i,j,choice are just some variables */



void get_det_input();

/* this function gets the input data in case of determinants */



void get_cramer_input();

/* this function gets the input data in case of cramers rule */

int get_menu();

/* gets the initial menu */



float compute_2nd_order(float a,float b,float c, float d);

/* computes the 2nd order determinant and we explicitly specify the elements */



float compute_3rd_order();

/* computes the 3rd order determinant. For this the elements are filled

in the 'det33' array previously defined */



float compute_4th_order();

/*computes 4th order using det44 */



void solve_cramer();

/*solves the unkonws using cramers rule */



void main()

{

 int i,j;

 do {

     clrscr();

     choice = get_menu();

     /* get here what to do : determinant, cramers  or exit */

     if (choice==1)

      /* if choice is determinant */

	{

	  get_det_input();

	  /*get determinant input */

	  switch (order) {

		case 1 : det_val=det[0][0];

			/* if order is 1 straightofrward answer */

			 break;



		case 2 : det_val=compute_2nd_order(det[0][0],det[0][1],det[1][0],det[1][1]);

			/* if order is 2 compute using function */

			break;



		case 3 : for (i=0;i<3;++i)

			   for(j=0;j<3;++j)

				det33[i][j]=det[i][j];

		/* the above loop is for filling det33 array  so that

		this could be used by the compute_3rd_order function .Remember I

		use only det33 array in that function */

			 det_val=compute_3rd_order();

			 break;



		case 4 : for (i=0;i<4;++i)   // this loop is for filling 3rd det.array

			   for(j=0;j<4;++j)

				det44[i][j]=det[i][j];

		/* the above loop is for filling det44 array  so that

		this could be used by the compute_4th_order function .Remember I

		use only det44 array in that function */

			 det_val=compute_4th_order();

			 break;

	      };//switch



	  printf("\nSolution : Det = %f",det_val);

	  printf("\n\nPress any key to continue....");

	}

   else if (choice==2)

	{

	/*if choice is cramers */

	  get_cramer_input();

	  solve_cramer();

	  printf("\n\nPress any key to continue....");

	}

   else printf("\n\nPress any key to exit....");

   getch();

  }

 while (choice!=3);

 /* do until the userrr doesnt exit */

}



float compute_4th_order()

/* this function uses det44 array */

{

  int bool=1;  // to do add subtract alternatively

/* this boolean variable is used to do add-subtract of the determinants

alternatively. Remember ..how determinats are calculated*/

  float retval=0;

 /*this is the return variable value*/

  int i,j,m;

  int tempcol,col=0;

  /* here i have used a slightly different logic..but its simple...consider a

  4*4 determinant..now to calcuate it we have to multiply and add the top row

  elements with their corresponding minors...for these reasons i have used

  'col' which is initially 0 and is incremented at the end of the loop...

  now when this 'col' is used it should be multipplied with its 3rd

  order minor..therefore i have used 'tempcol' which is basically fof filling

  the third array 'det33' */

  for (m=0;m<4;++m)

   {

      for (i=0;i<3;++i)

	  {

	    tempcol=0;

	    for(j=0;j<3;++j) {

		if (tempcol==col) ++tempcol;

		/* if the tempcolumn for minor is same as column chosen then

		skip the column because a minor is obtained by NOT using its

		column...therefore */

		det33[i][j]=det44[i+1][tempcol++];

		/* now just assign the corresponding elements to the det33 array */

	      }

	   };

     if (bool) retval=retval+det44[0][m]*compute_3rd_order ();

     /* here get the 3rd order minor and multiply and alternatively add-

     subtract wiht the first row elemenst of the 4th determinant */

     else retval=retval-det44[0][m]*compute_3rd_order();

     bool=1-bool;

     /* here increase the col*/

     ++col;

  }

 return(retval);

}



float compute_3rd_order()

/* this function uses det33 array */

{

 int bool=1;

/* this boolean variable is used to do add-subtract of the determinants

alternatively. Remember ..how determinats are calculated*/

 int c1,c2,m;

 float retval=0;

 /*this is the return variable value*/

 for (m=0;m<3;++m)

 /* this loop is used to calculate the MINOR and calculate the determinant*/

   {

     if (m==0) c1=1; else c1=0;

     /* this is a little complicated.  Consider a 3*3 determinant.when m=0

     i.e.first row 1st column then minor elements are taken from 2,3 rows and columns.

     okay...a 2*2 minor requires 2 rows and 2 columns..c1 is the column1 and c2=column2.

     this is just a small logic which eliminates the current column of which it is a minor.got it */

     if (m==2) c2=1; else c2=2;

     if (bool) retval=retval+det33[0][m]*compute_2nd_order (det33[1][c1],det33[1][c2],det33[2][c1],det33[2][c2]);

     /* if bool is true i.e.bool=1 then the minor product gets added else subtracted */

     else retval=retval-det33[0][m]*compute_2nd_order (det33[1][c1],det33[1][c2],det33[2][c1],det33[2][c2]);

     /*this line "bool=1-bool"is very simple, yet very effective as it toggles

     the value of bool between 0 and 1*/

     bool=1-bool;

  }

 return(retval);

}



float compute_2nd_order(float a,float b,float c, float d)

/* this is a very simple function...actually not needed but used anyway */

{

 int retval=0;

 retval=a*d-b*c;

 return(retval);

}



void solve_cramer()

/* actually i did not have time to make a GENERIC function because it

requires careful planning and preparation ..i have just used a case switch

which sees that the no of unknowns and acts accordingly.*/

{

 float sol[4]={{0}};

/* this is the final solutiona array */

 float temp[4][4];

 /* this is a temporary array to store the delta determinant (deteminant of the unkonwns) */

 float delta;

/* this is th value of the deltra determinant */

 int m,n;

 switch (order) {

	case 1 : sol[0]=det[0][1]/det[0][0];

  /* if just single unknown then solution = RHS divided by LHS */

		 break;



	case 2 : delta=compute_2nd_order(det[0][0],det[0][1],det[1][0],det[1][1]);

		 if (delta==0) printf("No unique solution because determinant =0");

	     /* I think this is the condition for the non-unique solution..check it out */

		 sol[0]=compute_2nd_order(det[0][2],det[0][1],det[1][2],det[1][1])/delta;

	     /* sol[0] is obtained by replacing 1st column  by the RHS determinant */

		 sol[1]=compute_2nd_order(det[0][0],det[0][2],det[1][0],det[1][2])/delta;

	     /* sol[1] is obtained by replacing 2st column  by the RHS determinant */

		 break;



	case 3 : for (m=0;m<3;++m)

		 /* this looop just fills out the det33 array from det arry for

		 processing by the compute_3rd_order function */

		   for(n=0;n<3;++n)

		     {

			det33[m][n]=det[m][n];

			temp[m][n]=det[m][n];

		     }

		  delta=compute_3rd_order();

		  /*delta is assisgned the value and is checked for 0 */

		  if (delta==0) printf("No unique solution because determinant =0");

		  else {

		       for (j=0;j<3;++j)

		       /*the outer loop is for the no of unknowns...1st,2nd,3rd */

			  {

			     for(i=0;i<3;++i)

			     /* this inner  loop if for replacing the corresponding column

			     with the RHS determinant */

				det33[i][j]=det[i][3];

				sol[j]=compute_3rd_order();

				sol[j]=sol[j]/delta;

				 for (m=0;m<3;++m)

			/* this last loop is used so that the original delta array is restored */

				  for(n=0;n<3;++n)

					det33[m][n]=temp[m][n];

			   }//for

		    } //else

		 break;



	case 4 :

		/* same as the above : case 3 */

		for (m=0;m<4;++m)

		  for(n=0;n<4;++n)

		    {

			det44[m][n]=det[m][n];

			temp[m][n]=det[m][n];

		    }

		  delta=compute_4th_order();

		  if (delta==0) printf("No unique solution because determinant =0");

		  else {

		       for (j=0;j<4;++j)

			  {

			     for(i=0;i<4;++i)

				det44[i][j]=det[i][4];

				sol[j]=compute_4th_order();

				sol[j]=sol[j]/delta;

				 for (m=0;m<4;++m)

				  for(n=0;n<4;++n)

					det44[m][n]=temp[m][n];

			   }//for

		    } //else

		 break;

      };//switch



 printf("\nSolution is :");

 for (i=0;i<order;++i)

 printf("\n\tx%d = %f",i+1,sol[i]);

}



int get_menu()

/* this function isjust the layout of the menu..nothing much...BUt it

returns the CHOICE which is selected by the user */

{

 do {

	clrscr();

	 printf("\n\tMenu");

	 printf("\n     =========");

	 printf("\n1. Solve Determinant");

	 printf("\n2. Cramer's Rule\n3. Exit\n\nEnter Choice : ");

	 scanf("%d",&choice);

      }

 while ((choice!=1)&&(choice!=2)&&(choice!=3));

 return(choice);

}



void get_det_input()

/* this function gets the determinant input */

{

 do {

     printf("\nEnter the order of the determinant : ");

     scanf("%d",&order);

    }

  while ((order<1)||(order>4));

  /* only orders 1,2,3,4 are accepted */

 printf("\n");

 /* the following loop gets the array elements one by one */

 for (i=0;i<order;++i)

  {

     for (j=0;j<order;++j)

	{

	 printf("\tEnter element[%d][%d] :",i+1,j+1);

	 scanf("%f",&det[i][j]);

	}

     printf("\n");

    }

}



void get_cramer_input()

/* this function gets the cramers equation input */

{

 do {

   printf("\nEnter the no. of unknowns : ");

   scanf("%d",&order);

    }

 while ((order<1)||(order>4));

  /* only orders 1,2,3,4 are accepted */

 printf("\n");

 /* the following loop gets the array elements one by one */

 for (i=0;i<order;++i)

  {

     for (j=0;j<order;++j)

	{

	 printf("\tEnter element[%d][%d] :",i+1,j+1);

	 scanf("%f",&det[i][j]);

	}

	/* the next two lines get that extra elements.i.e. the constant of equation */

     printf("\t\tEnter Constant :");

     scanf("%f",&det[i][j]);

     printf("\n");

    }

}
--------------D57A3336A6494214D8FEEF6D
Content-Type: text/plain; charset=us-ascii; name="Project.txt"
Content-Disposition: inline; filename="Project.txt"
Content-Transfer-Encoding: 7bit


PROJECT TITLE:
==============
Development of Software Routines to find the 4th Order Determinant.

PROJECT DESCRIPTION:
====================

A 2nd order determinant,

   | a11   a12 |
   | a21   a22 |

can be calculated using the formula:

   | a11   a12 |
   | a21   a22 | =  a11 * a22 - a12 * a22


To calculate the 3rd order determinant, each element of a selected row multiples the minor of the element. The result are added or subtracted together in an alternating pattern

The minor of an element aij is determinant obtained by removing row i and column j.

As an example, the 3rd order determinant,

   | a11   a12   a13 |
   | a21   a22   a23 |
   | a31   a32   a33 |

can be calculated as

   | a11   a12   a13 |
   | a21   a22   a23 |  
   | a31   a32   a33 |    

=  a11 * minor(a11) - a12 * minor(a12) + a13 * minor(a13)

or

   | a11   a12   a13 | 
   | a21   a22   a23 | 
   | a31   a32   a33 |

=  a11 * | a22  a23 | - a12 * | a21  a23 | + a13 * | a21  a22 |
         | a32  a33 |         | a31  a33 |         | a31  a32 |

	  row 1,	       row 1,	            row 1,
	  column 1	       column 2		    column 3
	  removed	       removed		    removed



PROJECT REQUIREMENT:
====================

You are required to produce a set of functions, with the appropriate arguments, to calculate until the 4th order determinant. In order to achieve that you have to write functions to find the 2nd order determinant, the 3rd order determinant and to extract the array elements of a minor.

(Alternative algorithm is to develop the 2nd order determinant and the 3rd order minor. This means incorporating the last two functions above as one).

You are required to come up with the input function to enable the data entry of the elements of the determinant. Design the function such that it can be used for data entry into any order of determinant.

Your program should contain the main() function whereby the various function are called and the result vertifed. This is used to test your functions.


PROJECT ENHANCEMENT:
====================

Instead of using merely a test stub as suggested in (b), develop a complete program to implement Cramer's rule to solve simultaneous linear equations of up to 4 unknowns. Remember also that there are simultaneous equations that do not have unique solutions. Your program has to test for this. Find out the condition where no unique solution can be found. You must also develop another function to replace the appropriate columns of the determinant with the constants of your equations.


The solution by Cramer's rule to the linear system

	a11x1 + a12x2 + a13x3 = b1
	a21x1 + a22x2 + a23x3 = b2
	a31x1 + a32x2 + a33x3 = b3 

is in the form


	     1     | b1  a12  a13 |
	x1 = - det | b2  a22  a23 |
	     D	   | b3  a32  a33 |


	     1     | a11  b1  a13 |
	x2 = - det | a21  b2  a23 |
	     D	   | a31  b3  a33 |


	     1     | a11  a12  b1 |
	x3 = - det | a21  a22  b2 |
	     D	   | a31  a32  b3 |


where

	         | a11  a12  a13 |
	 D = det | a12  a22  a23 |
		 | a13  a32  a33 |


Another enhancement you may want to consider is to write a generic function to find the determinant of ANY order. To achieve this you will need to use recursion, which is outside the scope of our curriculum but it is not a very difficult technique to use. With this, you can solve any systems of linear equations using determinants. A very useful routine to have when you have to solve the parameters of a network of electrical circuits using mesh technique.


			   -=[ FINISH ]=-
	   


		

--------------D57A3336A6494214D8FEEF6D--