## FANDOM

1. Design, develop and execute a program in C to find and output all the roots of a given quadratic equation, for non-zero coefficients.

Summary:

Any quadratic equation has two roots and the roots of the equation can be found using the formula

x = (-b±√discriminant)/2a
where discriminant = b2-4ac and
a,b,c are coefficients when the equation is represented in form ax2+bx+c= 0

Hence as per the equation, if discriminant is equal to 0, then the value of both the roots are equal and real. Also to find x, when discriminant is not 0, we need to find square root of disc. When discriminant value is less than 0, the square root of the discriminant is imaginary and hence the roots of the equation are supposed to be imaginary and distinct. When discriminant value is greater than 0, the square root of the discriminant is real and hence the roots of the equation are supposed to be real and distinct.

Algorithm:

1) Take the inputs i.e. coefficients of the equation, a,b,c from the user.

2) Calculate the value of discriminant = b2-4ac

3) Decide whether roots are equal or distinct. If discriminant is equal to 0, then go to step 4, else go to step 5.

4) Calculate x1 and x2. x1 = x2 = -b/2a. Print roots are real and equal. Then go to step 8.

5) Decide whether roots are real or imaginary. If discriminant is lesser than 0, roots are imaginary and go to step 6. If discriminant is greater than 0, roots are real and go to step 7.

6) Calculate the roots x1 and x2. X1 = p+qi and x2 =p-qi where p = -b/2a and q = (√(discriminant*-1))/2a. Print roots are imaginary and distinct.

7) Calculate the roots x1 and x2. X1 = (-b+√(discriminant))/2a and x2 =(-b-√(discriminant))/2a. Print roots are real and distinct.

8) Print the value of x1 and x2.

9) STOP

Examples:

a) if a=5, b=10 and c =2, then discriminant = b2-4ac = (10)2 -4*5*2 = 100-40 = 60.

Since the discriminant is not 0, hence the roots are distinct. Also since discriminant is greater than 0, roots are real. Hence as per step 7,

x1 = (-b+√(discriminant))/2a = (-10+√60)/2*5 = (-10+7.746)/10 = -2.254/10 = 0.2254.

x2 = (-b-√(discriminant))/2a = (-10-√60)/2*5 = (-10-7.746)/10 = -17.746/10 = -1.7746.

b) if a=2, b=-5 and c =10, then discriminant = b2-4ac = (-5)2 -4*2*10 = 25-80 = -55.

Since the discriminant is not 0, hence the roots are distinct. Also since discriminant is lesser than 0, roots are imaginary. Hence as per step 6,

x1 =p+qi = -b/2a +.((√(discriminant*-1))/2a)i = -(-5)/2*2 + ((√(-55*-1))/22)i = 1.25 + 0.337i

x2 = p-qi = -b/2a -.((√(discriminant*-1))/2a)i = -(-5)/2*2 - ((√(-55*-1))/22)i = 1.25 - 0.337i

Program:

/*****************************************************************

*File : 01Quadratic.c
*Description : Program to find the roots of a Quadratic Equation
*Author : Prabodh C P
*Compiler : gcc compiler, Ubuntu 10.04
*Date : 7 September 2010
*****************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

/*****************************************************************

*Function : main
*Input parameters :
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS :
* 0 on success
*****************************************************************/

int main(int argc, char **argv)
{
float fA,fB,fC,fDesc,fX1,fX2,fRealp,fImagp;

printf("\n*************************************************************");
printf("\n*\tPROGRAM TO FIND ROOTS OF A QUADRATIC EQUATION\t *\n");
printf("*************************************************************");

printf("\nEnter the coefficients of a,b,c \n");
scanf("%f%f%f",&fA,&fB,&fC);
if(0 == fA)
{
printf("\nInvalid input not a quadratic equation-try again\n");
exit(0);
}

/*COMPUTE THE DESCRIMINANT*/
fDesc=fB*fB-4*fA*fC;

if(0 == fDesc)
{
fX1 = fX2 = -fB/(2*fA);

printf("\nRoots are equal and the Roots are \n");
printf("\nRoot1 = %f and Root2 = %f\n",fX1,fX2);
}
else if(fDesc > 0)
{
fX1 = (-fB+sqrt(fDesc))/(2*fA);
fX2 = (-fB-sqrt(fDesc))/(2*fA);
printf("\nThe Roots are Real and distinct, they are \n");
printf("\nRoot1 = %f and Root2 = %f\n",fX1,fX2);
}
else
{
fRealp = -fB / (2*fA);
fImagp = sqrt(fabs(fDesc))/(2*fA);
printf("\nThe Roots are imaginary and they are\n");
printf("\nRoot1 = %f+i%f\n",fRealp,fImagp);
printf("\nRoot2 = %f-i%f\n",fRealp,fImagp);
}

return 0;
}

/***************

* OUTPUT *

***************/

*************************************************************

* PROGRAM TO FIND ROOTS OF A QUADRATIC EQUATION *

*************************************************************

Enter the coefficients of a,b,c

1 -4 4

Roots are equal and the Roots are

Root1 = 2.000000 and Root2 = 2.000000

*************************************************************

* PROGRAM TO FIND ROOTS OF A QUADRATIC EQUATION *

*************************************************************

Enter the coefficients of a,b,c

1 -5 6

The Roots are Real and distinct, they are

Root1 = 3.000000 and Root2 = 2.000000

*************************************************************

* PROGRAM TO FIND ROOTS OF A QUADRATIC EQUATION *

*************************************************************

Enter the coefficients of a,b,c

1 3 3

The Roots are imaginary and they are

Root1 = -1.500000+i0.866025

Root2 = -1.500000-i0.866025

2. Design, develop and execute a program in C to implement Euclid’s algorithm to find the GCD and LCM of two integers and to output the results along with the given integers.

Summary:

In its simplest form, Euclid's algorithm starts with a pair of positive integers, and forms a new pair that consists of the smaller number and the difference between the larger and smaller numbers. The process repeats until the numbers in the pair are equal. That number then is the greatest common divisor of the original pair of integers.

The main principle is that the GCD does not change if the smaller number is subtracted from the larger number. For example, the GCD of 252 and 105 is exactly the GCD of 147 (= 252 − 105) and 105. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers, so this repetition will necessarily stop sooner or later — when the numbers are equal (if the process is attempted once more, one of the numbers will become 0).

Euclid’s Algorithm can thus be simplified by finding the remainder of the two integers and forms a new pair consisting of the divisor and the remainder.

Also to calculate the LCM of any two numbers m and n, following formula can be used if GCD

of the two numbers, GCD(m,n) is already known.

LCM(m,n) = (m*n)/GCD(m,n)

To illustrate the extension of Euclid's algorithm, consider the computation of gcd(120, 23), which

is shown in the table below. Notice that the quotient in each division is recorded as well

alongside the remainder. In this example, the divisor in the last line (which is equal to 1)

indicates that the gcd is 1; that is, 120 and 23 are coprime (also called relatively prime).


Iteration Dividend Divisor Remainder Quotient 1 120 23 5 5 2 23 5 3 4 3 5 3 2 1 4 3 2 1 1 5 2 1 0 2 6 1 0
</center>

Algorithm:

1. Take the inputs i.e. m and n, the numbers for which GCD and LCM needs to be found.

2. If both m and n are equal to 0, then print “GCD doesn’t exist”. Go to step 9.

3. If n is equal to 0, then go to step 6. Else calculate reminder = m (mod) n.

4. Assign m=n and n = reminder.

5. If new value of n is 0, then go to step 6, else go back to step 3.

6. GCD= m. Print the value of GCD.

7. LCM = ( Initial value of m * initial value of n) /GCD

8. STOP

Example:

a) If m = 10, n = 15


Iteration Dividend Divisor Remainder Quotient 1 10 15 10 0 2 15 10 5 1 3 10 5 0 2 4 5 0
</center>

Hence,

GCD = m = 5.

LCM = (Initial m *Initial n)/GCD = (10*15)/5 = 30.

Program:

/*****************************************************************

*File : 02GcdLcm.c

*Description : Program to find the GCD & LCM of two numbers

*Author : Prabodh C P

*Compiler : gcc compiler, Ubuntu 10.04

*Date : 7 September 2010

*****************************************************************/

#include<stdio.h>

#include<stdlib.h>

/*****************************************************************

*Function : main

*Input parameters :

* int argc - no of commamd line arguments

* char **argv - vector to store command line argumennts

*RETURNS :

* 0 on success

*****************************************************************/

int main(int argc, char **argv)

{

int iX1,iX2,iY1,iY2,iRem,iGcd,iLcm; printf("\n*********************************************************");

printf("\n*\tPROGRAM TO FIND GCD & LCM OF TWO NUMBERS\t*\n");

printf("*********************************************************");

printf("\nEnter two numbers\n");

scanf("%d%d",&iX1,&iX2);

if(0 == iX1 && 0 == iX2)

{

printf("\nGCD doesn't exist\n");

exit(0);

}

else /*APPLY EUCLID'S ALGORITHM*/

{

iY1 = iX1;

iY2 = iX2;

while(iY2!=0)

{

iRem = iY1%iY2;

iY1 = iY2;

iY2 = iRem;

}

iGcd = iY1;

iLcm = (iX1*iX2)/iGcd;

printf("\n LCM of %d and %d is= %d\n",iX1,iX2,iLcm);

}

return 0;

}

/***************

* OUTPUT *

***************/

*********************************************************

* PROGRAM TO FIND GCD & LCM OF TWO NUMBERS *

*********************************************************

Enter two numbers

0 0

GCD doesn't exist

*********************************************************

* PROGRAM TO FIND GCD & LCM OF TWO NUMBERS *

*********************************************************

Enter two numbers

64 48

GCD of 64 and 48 is= 16

LCM of 64 and 48 is= 192

*********************************************************

* PROGRAM TO FIND GCD & LCM OF TWO NUMBERS *

*********************************************************

Enter two numbers

5 0

GCD of 5 and 0 is= 5

LCM of 5 and 0 is= 0

3. Design, develop and execute a program in C to reverse a given four digit integer number and check whether it is a palindrome or not. Output the given number with suitable message.

Summary:

Palindrome is a number, word, phrase, or sequence that reads the same backward as forward, e.g., “madam” or “malayalam” or 1221 or 10301.

Algorithm:

1. Get the input i.e. num, the 4 digit number which needs to be checked for being a palindrome

2. Initialize rev=0.

3. Calculate the remainder and quotient when num is divided by 10. Rem = num(mod) 10 and quo = num/10.

4. Assign num = quo and rev = (rev*10)+rem

5. If num is equal to 0, go to step 6, else go back to 3.

6. Compare initial num and rev. If they are equal, then print initial num is a palindrome. Else print that initial num is not a palindrome.

7. STOP

Program:

/*****************************************************************

*File : 03Palindrome.c

*Description : Program to check whether the given integer is a Palindrome or not

*Author : Prabodh C P

*Compiler : gcc compiler, Ubuntu 10.04

*Date : 7 September 2010

*****************************************************************/

#include<stdio.h>

#include<stdlib.h>

/*****************************************************************

*Function : main

*Input parameters :

* int argc - no of commamd line arguments

* char **argv - vector to store command line argumennts

*RETURNS :

* 0 on success

*****************************************************************/

int main(int argc, char **argv)

{

int iNum,iRev = 0,iTemp,iRem;

printf("\n*\tPROGRAM TO CHECK WHETHER AN INTEGER IS A PALINDROME OR NOT\t *\n");

printf("**************************************************************************");

printf("\nEnter a number\n");

scanf("%d",&iNum);

iTemp = iNum;

while(iNum!=0)

{

iRem = iNum % 10;

iRev = iRev * 10 + iRem;

iNum = iNum/10;

}

printf("\nReverse is %d",iRev);

if(iRev == iTemp)

printf("\nNumber %d is a palindrome\n",iTemp);

else

printf("\nNumber %d is not a palindrome\n",iTemp);

return 0;

}

/***************

* OUTPUT *

***************/

******************************************************************

* PROGRAM TO CHECK WHETHER AN INTEGER IS A PALINDROME OR NOT *

******************************************************************

Enter a number

7667

Reverse is 7667

Number 7667 is a palindrome

******************************************************************

* PROGRAM TO CHECK WHETHER AN INTEGER IS A PALINDROME OR NOT *

******************************************************************

Enter a number

1234

Reverse is 4321

Number 1234 is not a palindrome

4) Design, develop and execute a program in C to evaluate the given polynomial f(x) = a4x4 + a3x3 + a2x2 + a1x + a0 for given value of x and the coefficients using Horner’s method.

Summary:

Horner's method of polynomial evaluation is described below

The expression is broken down in the following way

f(x) = a4x4 + a3x3 + a2x2 + a1x + a0

f(x) = x ( a4x3 + a3x2 + a2x + a1 ) + a0

f(x) = x ( x( a4x2 + a3x2 + a2 ) + a1 ) + a0

f(x) = x ( x( x ( a4x + a3 ) + a2 ) + a1 ) + a0

f(x) = x ( x( x ( x ( a4 ) + a3 ) + a2 ) + a1 ) + a0

Example:

Input values:

x=6

a0=5, a1=4, a2=3, a3=2, a4=1

sum = a4 * x 1 * 6 → 6

sum = ( sum + a3 ) * x ( 6 + 2 ) * 6 → 48

sum = ( sum + a2 ) * x ( 48 + 3 ) * 6 306

sum = ( sum + a1 ) * x ( 306 + 4 ) *6 1860

Algorithm:

Step 1  : Start

Step 2 : Input the degree and value of x

Step 3 : Input Coefficients , upper limit is provided by the value of degree

Step 4 : i = degree, sum =0

Step 5 : sum = ( sum + ai ) * x

Step 6 : decrement i by 1

Step 6 : if ( i > 0 ) goto step 5

Step 7  : add a0 to the final sum

Step 8  : display sum

Step 9 : Stop

Program:

/*****************************************************************

*File : 04Horner.c

*Description : Program to implement Horners method for Polynomial evaluation

*Author : Prabodh C P

*Compiler : gcc compiler, Ubuntu 10.04

*Date : 7 September 2010

*****************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

/*****************************************************************

*Function : main

*Input parameters: no parameters

*RETURNS : 0 on success

*****************************************************************/

int main(void)

{

int iDeg,i,iaArr[10];

float fX,fSum=0;

printf("\n*********************************************************************");

printf("\n*\tPROGRAM TO EVALUATE A POLYNOMIAL USING HORNERS METHOD\t *\n");

printf("*********************************************************************");

printf("\nEnter the degree of the polynomial and value of x\n");

scanf("%d%f",&iDeg,&fX);

printf("\nEnter the coefficients in descending order of degree\n");

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

{

scanf("%d",&iaArr[i]);

}

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

{

fSum=(fSum+iaArr[i])*fX;

}

fSum = fSum + iaArr[iDeg];

printf("\nValue of polynomial after evaluation=%g\n",fSum);

return 0;

}

/***************

* OUTPUT *

***************/

****************************************************************

* PROGRAM TO EVALUATE A POLYNOMIAL USING HORNERS METHOD *

****************************************************************

Enter the degree of the polynomial and value of x

5

2

Enter the coefficients in reverse order

6 5 4 3 2 1

Value of polynomial after evaluation=120.000000

****************************************************************

* PROGRAM TO EVALUATE A POLYNOMIAL USING HORNERS METHOD *

****************************************************************

Enter the degree of the polynomial and value of x

4 1

Enter the coefficients in reverse order

1 2 3 4 5

Value of polynomial after evaluation=15.000000

5. Design, develop and execute a program in C to copy its input to its output, replacing each string of one or more blanks by a single blank.

Summary:

The program introduces concept of Character comparision and also white space characters like ‘\t’ and null characters like ‘\0’ To find and replace all multiple blanks, with a single blank in the string, we will start from second character as current character in the input string and compare it with the previous character and if only both are not spaces, then the current character will stored in the destination string. We will continue this till we reach the end of the input string which is denoted by null character, ‘\0’.

Algorithm:

1) Take the input, acSStr, i.e. array of characters including multiple spaces and tabs.

2) Initialize an destination array, acDStr, which will hold the value of results

3) Initialize variable cPrevChar as the first element of the input array and cCurrentChar as the second element of the input array.

4) Check if cPrevChar is a tab, ‘\t’, if so, add a space to the Destination array, acDStr and assign cPrevChar to a space, “ “.

5) If cCurrentChar is equal to null character, ‘\0’, then go to step 10.

6) If both aPrevChar and cCurrentChar are white spaces, then go to step 9.

7) If cCurrentChar is a tab, then assign it to a space.

8) Add cCurrentChar to destination array, acDStr.

9) Assign cPrevChar to cCurrentChar and assign cCurrentChar to the next element in the input String, acSStr. Go to step 5.

10) Assign a null character, ‘\0’ to the destination string, acDStr.

11) Print the destination string, acDStr.

12) STOP.

/*****************************************************************

*File : 05RemSpace.c

*Description : Program to replace multiple whitespaces with a single space

*Author : Prabodh C P

*Compiler : gcc compiler, Ubuntu 10.04

*Date : 7 September 2010

*****************************************************************/

#include<stdio.h>

#include<stdlib.h>

/*****************************************************************

*Function : main

*Input parameters :

* int argc - no of commamd line arguments

* char **argv - vector to store command line argumennts

*RETURNS :

0 on success

*****************************************************************/

int main(int argc, char **argv)

{

char acSStr[100],acDStr[100];

int i,j=0;

char cPrevChar,cCurChar;

int iPrevSpace,iCurSpace;

printf("\n*************************************************************************");

printf("\n*\tPROGRAM TO REPLACE MULTIPLE WHTESPACES WITH A SINGLE BLANK\t*\n");

printf("*************************************************************************");

printf("\nEnter a Sentence\n");

gets(acSStr);

cPrevChar = acSStr[0];

cCurChar = acSStr[1];

/*IF FIRST CHARACTER IS A TAB REDUCE IT TO A SINGLE SPACE*/

if(cPrevChar == '\t')

cPrevChar = ' ';

acDStr[j++] = cPrevChar;

//for(i = 1; (*(acSStr+i)); i++)

for(i = 1; acSStr[i] != '\0'; i++)

{

iPrevSpace = 0;

iCurSpace = 0;

/*CHECK WHETHER PREVIOUS CHARECTER WAS A WHITESPACE*/

if(cPrevChar == ' ' || cPrevChar == '\t')

iPrevSpace = 1;

/*CHECK WHETHER CURRENT CHARECTER WAS A WHITESPACE*/

if(cCurChar == ' ' || cCurChar == '\t')

iCurSpace = 1;

/*CHECK WHETHER BOTH PREVCHAR & CURCHAR ARE NOT SPACES*/

if(!(iPrevSpace && iCurSpace))

{

/*THEN COPY CURCHAR INTO DESTINATION STRING*/

/* IF CURCHAR IS A TAB REDUCE IT TO A SPACE*/

if(cCurChar == '\t')

cCurChar = ' ';

acDStr[j++] = cCurChar;

}

cPrevChar = cCurChar;

cCurChar = acSStr[i+1];

}

/*PLACE A NULL TERMINATOR AT END OF STRING*/

acDStr[j] = '\0';

printf("\nThe String without spaces is\n");

puts(acDStr);

return 0;

}
/***************

* OUTPUT *

***************/

*****************************************************************

* PROGRAM TO REPLACE MULTIPLE WHTESPACES WITH A SINGLE BLANK *

*****************************************************************

Enter a Sentence

I like programming C.

The String without spaces is

I like programming C.

*****************************************************************

* PROGRAM TO REPLACE MULTIPLE WHTESPACES WITH A SINGLE BLANK *

*****************************************************************

Enter a Sentence

I am an Indian

The String without spaces is

I am an Indian

6. Design, develop and execute a program in C to input N integer numbers in ascending order into a single dimension array, and then to perform a binary search for a given key integer number and report success or failure in the form of a suitable message.

Summary:

Binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.

Example:

Array = 1 3 4 6 8 9 11
Key = 4

Iteration1:
Find the mid element of Array , its 6
Compare key to 6. It's smaller. Repeat with Array = 1 3 4.
Iteration2:
Find the mid element , its 3
Compare key to 3. It's bigger. Repeat with Array = 4.
Iteration3:
Find mid element , its 4
Compare key to 4. It's equal. We're done, we found key.

In each iteration the length of the list we are looking in gets cut in half. Therefore, the total number of iterations cannot be greater than logN.

Algorithm :

Step 1: Start
Step 2: Input Length of array
Step 3: Input the array elements on by one in Non-descending order
Step 4: Input Key element to search
Step 5: if length of array < 1 goto step 12
Step 6: Find the mid element of the array
Step 7: If mid element matches the key, goto step 11
Step 8: If mid element > key , goto step 9 else goto step 10
Step 9: Set the end of the array as the element before mid element. Go to step 5
Step 10: Set the beginning of the array as the element after the mid element. Go to step 5
Step 11: Display successfully found key , goto step 13
Step 12: Display unsuccessful in finding the key
Step 13: Stop

Program:

/*****************************************************************

*File : 06BinarySearch.c

*Description : Program to implement binary search

*Author : Prabodh C P

*Compiler : gcc compiler, Ubuntu 10.04

*Date : 7 September 2010

*****************************************************************/

#include<stdio.h>

#include<stdlib.h>

/*****************************************************************

*Function : main

*Input parameters :

* int argc - no of commamd line arguments

* char **argv - vector to store command line argumennts

*RETURNS :

0 on success

*****************************************************************/

int main(int argc, char **argv)

{

int iNum, i, iFound, iaArr[10], iKey, iPos, iLow, iHigh, iMid;

printf("\n**************************************************");

printf("\n*\tPROGRAM TO IMPLEMENT BINARY SEARCH\t *\n");

printf("**************************************************");

printf("\nEnter no of elements\n");

scanf("%d",&iNum);

printf("\nEnter the elements in ascending order\n");

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

scanf("%d",&iaArr[i]);

printf("\nEnter the Key element\n");

scanf("%d",&iKey);

iFound = 0;

iLow = 0;

iHigh = iNum-1;

while(iLow <= iHigh)

{

iMid = (iLow + iHigh)/2;

if(iKey == iaArr[iMid]) /*KEY ELEMENT FOUND*/

{

iPos = iMid;

iFound = 1;

break;

}

else if(iKey < iaArr[iMid]) /*KEY ELEMENT IS IN 1ST HALF*/

iHigh = iMid - 1;

else /*KEY ELEMENT IS IN 2ND HALF*/

iLow = iMid +1;

}

if(iFound)

printf("\nKey element %d found at position %d\n",iKey,iPos+1);

else

printf("\nKey element not found\n");

return 0;

}

/***************

* OUTPUT *

***************/

**************************************************

* PROGRAM TO IMPLEMENT BINARY SEARCH *

**************************************************

Enter no of elements

5

Enter the elements in ascending order

1 3 5 7 9

Enter the Key element

7

Key element 7 found at position 4

**************************************************

* PROGRAM TO IMPLEMENT BINARY SEARCH *

**************************************************

Enter no of elements

4

Enter the elements in ascending order

2 4 6 8

Enter the Key element

5

Key element not found

Community content is available under CC-BY-SA unless otherwise noted.