PPS SSSSHHEHESHSHEHHEHAKAKHEHE12131415.pdf

Great it is

1. PROGRAMMING
FOR PROBLEM
SOLVING
Lecture –12, 13, 14 & 15
Dr. S.Kanungo
Dept. of CSE, BIT Mesra

2. Function to Compute Factorial
•int factorial(int n) {
int i, /* local variables */
product; /* accumulator for product computation */
product = 1;
/* Computes the product n x (n-1) x (n-2) x . . . x 2 x 1*/
for (i= n; i> 1; --i) {
product = product * i;
}
/* Returns function result */
return (product);
}
➢Theloopbodyexecutesfordecreasingvaluesofifromn
through2,andeachvalueofiisincorporatedinthe
accumulatingproduct.Loopexitoccurswheniis1.

3. •NestedCountingLoopProgram
#include<stdio.h>
intmain(void)
{
inti,j; /*loopcontrolvariables*/
printf(" ij\n");/*printscolumnlabels*/
for(i=1;i<4;++i){ /*headingofouterforloop*/
printf("Outer%6d\n",i);
for(j=0;j<i;++j){/*headingofinnerloop*/
printf("Inner%9d\n",j);
} /*endofinnerloop*/
} /*endofouterloop*/
return(0);
}

4. •Output
i j
Outer 1
Inner 0
Outer 2
Inner 0
Inner 1
Outer 3
Inner 0
Inner 1
Inner 2
➢Theouterloopcontrolvariable,i,appearsinthecondition
thatdeterminesthenumberofrepetitionsoftheinner
loop.Althoughthisisperfectlyvalid,youcannotusethe
samevariableastheloopcontrolvariableofbothanouter
andaninnerforloopinthesamenest.

5. •do-whileStatement:Evaluatealooprepetition
conditionafterthefirstexecutionoftheloopbody
➢pseudocodeforaninputvalidationloop
1.Getadatavalue.
2.Ifdatavalueisn’tintheacceptablerange,
gobacktostep1.
➢SYNTAX:
do
statement;
while(looprepetitioncondition);
➢EXAMPLE:/*Findfirstevennumberinput*/
do
status=scanf("%d",&num);
while(status>0&&(num%2)!=0);

6. •The Comma Operator
➢It can be used as an operator to separate values
in an expression.
➢It will only use the last value in evaluating the
expression.
➢Example: x = (a<4, b+1, y*z); /*Assign y*z to x*/
➢Can be useful in foror whileexpressions
➢Example: for(i=0, j=10; i<j; i++, j--) printf(“BIT\n”);
This is not a nested loop but a single loop with
two counters -it will loop five times only.
➢Example:while ((ch1=getchar(), ch2=getchar()) != '\n') ...;
In this loop two characters are read, the second of
which is compared with a newline character to
determine when to terminate the loop.

7. •The gotoStatement: A bad thing and should be avoided
➢An indication of poorly planned and badly structured code.
➢General format:
gotolabel; /*The label is any alphanumeric name in the
same form as variable or function names.*/
........
label: statement;
➢Example: gotohere;
........
here: x=y;
➢Restriction: It is possible to have a gotofrom within a set
of { } to a label either inside or outside the same { }, but:
it is NOT possible to have a gotooutside a set of { } to a
label inside the { }.

8. •Data structure: A composite of related data items
stored under the same name
•Array: A collection of data items of the same type
➢Acollectionoftwoormoreadjacentmemory
cells,calledarrayelements,thatareassociated
withaparticularsymbolicname.
➢Declaration:doublex[8];instructsthecompiler
toassociateeightmemorycellswiththenamex
➢Subscriptedvariable:Avariablefollowedbya
subscriptinbrackets,designatinganarray
element.
▪x[0](readasxsubzero)maybeusedto
referencetheinitialor0thelementofthearrayx
➢Arraysubscript:Avalueorexpressionenclosed
inbracketsafterthearrayname,specifyingwhich
arrayelementtoaccess

9. •TheEightElementsofArrayx
doublex[8];
•StatementsThatManipulateArrayx

10. •Wecandeclaremorethanonearrayinasingle
typedeclaration.
➢doublecactus[5],needle,pins[6];
➢intfactor[12],n,index;
•SYNTAX:
➢element-typeaname[size];/*uninitialized*/
element-typeaname[size]={initializationlist};/*
initialized*/
➢EXAMPLE:#defineA_SIZE5
...
doublea[A_SIZE];
charvowels[]={'A','E','I','O','U’};
➢StoringaStringinanArrayofCharacters:
charbtech[]=“SecondSemesterStudents";

11. •LimitationsandDangersintheUseofanArray
➢Assignwholearraysonetoanother.
eg.intx[10],y[10];
x=y; /*invalidstatement*/
➢Compareonearraywithanother.
eg.intx[10],y[10];
if(x==y)a++; /*validbutalwaysfalse*/
➢Toassignorcomparearrayseachelementof
eacharraymustbeassignedorcomparedin
turn
➢'C'merelycountsforwardorbackwardsin
memoryfromitsstartingpointofelement0...
anduseswhateveritfindsthere

12. •InitialisationofArrays
➢intxyz[6]={4,7,3,9,100,6};
➢Toomanyinitialiserswillcauseacompilationerror.
➢Iftherearetoofewinitialisingvaluesthe
remainingarrayelementswilldefaulttozero.
➢Characterarrayscanalsohaveastring
initialisation:charname[10]=“BITMesra“
➢Ifanarrayisinitialisedthesizecanbeleftto
defaulttothenumberofinitialisingvalues.
eg.chargreeting[]="Hello!";
•TwoDimensionalArrays
➢intx[8][8];Thisdeclares64integersarrangedinan8
x8gridofrowsandcolumns.
➢Firstelement:x[0][0];Lastelement:x[7][7]

13. •UsingIndividualRows
➢Toreadanameintoasingledimensionarray:
gets(SingleName);
➢Toreadanameintoonerowofatwodimension
array:gets(ListOfNames[41]);
Thiswouldreadthenamefromthekeyboard
intothe42
nd
rowofthelistofnames.
•MultiDimensionalArrays
➢Anarraycanhavemorethantwodimensions
➢iftherewasaneedforanarraycontainingseveral
namelists,onelistforeachof50branchesina
companydivision?
➢charBranchNames[50][100][30];Thiswould
contain50*100*30=150,000characters

14. •InitializingMultiDimensionalArrays
➢Itcanbeinitializedasasinglelistofinitializer
values:eg.intx[3][4]={3,2,10,5,6,2}
Thiswillinitializex[0][0]tox[0][3]with3,2,10,5
andx[1][0]andx[1][1]to6and2.Allremainingarray
elementsaresettozero
➢Eg.inty[3][4][2]={3,2,10,5,6,2,13,1,9,10,7};
➢y[0][0][0]andy[0][0][1]willbeinitializedto3and
2,andsoonwithy[0][1][0]toy[0][3][1]initialized
to10,5,6,2,13and1.Theremaininginitializers
sety[1][0][0],y[1][0][1]andy[1][1][0]to9,10and
7.
•Alternatively,nested{}canbeusedtoinitialize
thestartofeachrow:eg.intx[3][4]=
{{3,2},{10,5,6},2}

15. •Characterarrayscanhaverowsinitializedwith
strings,providingeachrowislongenoughtotake
thelongestnameplusthenullbyteterminator.:
➢Eg.ListOfNames[100][30]={“SuryaKumar",
“PiyushSingh",“NamanKumar"};
•Example:Thefollowingarraysquarewillbeusedto
storethesquaresoftheintegers0through10(e.g.,
square[0]is0,square[10]is100).Weassumethatthe
nameSIZEhasbeendefinedtobe11.
➢intsquare[SIZE],i;
➢Theforloopfor(i=0;i<SIZE;++i)square[i]=i*i;
initializesthisarrayas:

16. •Example
/*Computesthemeanandstandarddeviationof
anarrayofdataanddisplaysthedifferencebetween
eachvalueandthemean*/
#include<stdio.h>
#include<math.h>
#defineMAX_ITEM8/*maximumnumberofitemsin
listofdata*/
intmain(void)
{
doublex[MAX_ITEM],/*datalist*/
mean, /*mean(average)ofthedata*/
st_dev, /*standarddeviationofthedata*/

17. sum, /*sumofthedata*/
sum_sqr;/*sumofthesquaresofthedata*/
inti;
/*Getsthedata*/
printf("Enter%dnumbersseparatedbyblanksor
<return>s\n>",MAX_ITEM);
for(i=0;i<MAX_ITEM;++i)
scanf("%lf",&x[i]);
/*Computesthesumandthesumofthesquares
ofalldata*/
sum=0;
sum_sqr=0;
for(i=0;i<MAX_ITEM;++i)

18. {
sum+=x[i];
sum_sqr+=x[i]*x[i];
}
/*Computesandprintsthemeanandstandarddeviation*/
mean=sum/MAX_ITEM;
st_dev=sqrt(sum_sqr/MAX_ITEM-mean*mean);
printf("Themeanis%.2f.\n",mean);
printf("Thestandarddeviationis%.2f.\n",st_dev);
/*Displaysthedifferencebetweeneachitemandthemean*/
printf("\nTableofdifferencesbetweendatavaluesandmean\n");
printf("Index Item Difference\n");
for(i=0;i<MAX_ITEM;++i)

19. printf("%3d%4c%9.2f%5c%9.2f\n",i,'',x[i],'',x[i]
-mean);
return(0);
}
➢Output
Enter8numbersseparatedbyblanksor<return>s
>1612682.51214-54.5
Themeanis2.00.
Thestandarddeviationis21.75.
Tableofdifferencesbetweendatavaluesandmean
Index Item Difference
0 16.00 14.00
1 12.00 10.00
2 6.00 4.00
3 8.00 6.00
4 2.50 0.50
5 12.00 10.00
6 14.00 12.00
7 -54.50 -56.50

20. Partial Trace of Computing for Loop

21. /*LowercasetoUppercaseTextConversion*/
#include<stdio.h>
#include<ctype.h>
main(){
charletter[80];
intcount,tag;
/*enterthetext*/
for(count=0;(letter[count]=getchar())!=‘\n’;++count)
;
/*tagthecharactercount*/
tag=count;
/*displaythelineinuppercase*/
for(count=0;count<tag;++count)
putchar(toupper(letter[count]));}

22. •Examples:SkeletalOutline
#include<stdio.h>
main(){
charitem[20];intpartno;floatcost;
…….
scanf(“%s%d%f”,item,&partno,&cost);
……..}
➢Noticetheblankspacethatprecedes%s.Thispreventsanypreviously
enteredextraneouscharactersfrombeingassignedtoitem.
➢ Useofthescanffunctiontoenterastringconsistingofuppercaseletters
andblankspaces:
#include<stdio.h>
main(){ /*Considerstringinput:BITMESRARANCHI
charline[80];ANDBitMesraRanchi*/
….
scanf(“%[ABCDEFGHIJKLMNOPQRSTUWXYZ]”, line);
…..}

23. ➢Toprecedethecharacterswithinthesquarebracketsbya
Circumflex(i.e.,^)
#include<stdio.h>
main(){
charline[80];
……
scanf(“%[^\n]”,line);
.....}
Noticetheblankspacepreceding%[^\n],toignoreanyunwanted
charactersthatmayhavebeenenteredpreviously.
•Example:ProgramforaveragingStudentExamScores
#include<stdio.h>
main(){ /*sampleinteractiveprogram*/
charname[20];floatscore1,score2,score3,avg;
printf("Pleaseenteryourname:”); /*entername*/
scanf("%[^\n]",name);

24. printf("Please enter the first score: "); /* enter 1st score */
scanf("%f", &score1);
printf("Please enter the second score: "); /* enter 2nd score */
scanf ( "%f”,&score2);
printf("Please enter the third score: "); /* enter 3rd score */
scanf(“%f”, &score3);
avg = (scorel+score2+score3)/3; /* calculate avg */
printf ( \n\nName: %-s\n\n", name); /* write output */
printf("Score 1: %-5.1f\n”, score1);
printf("Score 2: %-5.lf\n", score2);
printf("Score 3: %-5.lf\n\n", score3);
printf("Average: %-5.1f\n\n, avg);
}

25. •The continue Statement
➢It is used to bypass the remainder of the current
pass through a loop.
➢The loop does not terminate when a continue
statement is encountered.
➢It can be included within a while, a do -while or a
for statement.
➢Example:
do { /*the processing of the current value of x will be bypassed if the value of x is negative*/
scan'f( "%f”, &x) ;
if(x < 0) { printf("Error-Negative Value For x");
continue; }
/* process the nonnegative value of x */
.....
} while (x <= 100);

26. •Example: Search for a palindrome
#include <stdio.h>
#include <ctype.h>
#define EOL '\n’
#define TRUE 1
#define FALSE 0
main( ) {
char letter[80]; int tag, count, countback, flag, loop = TRUE;
while (loop) {
flag = TRUE;
/* read the text */
printf("Please enter a word, phrase or sentence below:\n");
for (count = 0; (letter[count] = getchar()) != EOL; ++count);
if ((toupper(letter[0]) == 'E') && (toupper(letter[1]) == 'N’)
&& (toupper(letter[2]) == 'D')) break;

27. tag = count -1;
/* carry out the search */
for ((count = 0, countback = tag); count <= tag/2; (++count, --
countback)) {
if (letter[count] != letter[countback]) {
flag = FALSE;
break; }
}
/* display message */
for (count = 0; count <= tag; ++count)
putchar(letter[count]);
if (flag) printf(" IS a palindrome\n\n");
else printf(" is NOT a palindrome\n\n"));
}
}

28. •Addition of two matrix
#include<stdio.h>
intmain(){
intm,n,i,j;
printf("Enterthenumberofrowsandcolumnsofthematrices:");
scanf("%d%d",&m,&n);
inta[m][n],b[m][n],c[m][n];
printf("EntertheelementsofmatrixA:\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);}}
printf("EntertheelementsofmatrixB:\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){scanf("%d",&b[i][j]);}}

29. /*addthematrices*/
for(i=0;i<m;i++){
for(j=0;j<n;j++){
c[i][j]=a[i][j]+b[i][j];}}
//printtheresult
printf("Thesumofthetwomatricesis:\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%d",c[i][j]);
}
printf("\n");
}
return0;
}

30. •MatrixMultiplication
#include<stdio.h>
#include<stdlib.h>
intmain(){
inta[10][10],b[10][10],mul[10][10],r,c,i,j,k;
system("cls");
printf("enterthenumberofrow=");
scanf("%d",&r);
printf("enterthenumberofcolumn=");
scanf("%d",&c);
printf("enterthefirstmatrixelement=\n");
for(i=0;i<r;i++){
for(j=0;j<c;j++){scanf("%d",&a[i][j]);}}

31. printf("enterthesecondmatrixelement=\n");
for(i=0;i<r;i++){
for(j=0;j<c;j++){scanf("%d",&b[i][j]);}}
printf("multiplyofthematrix=\n");
for(i=0;i<r;i++){
for(j=0;j<c;j++){mul[i][j]=0;
for(k=0;k<c;k++){mul[i][j]+=a[i][k]*b[k][j];}}}
//forprintingresult
for(i=0;i<r;i++){
for(j=0;j<c;j++){printf("%d\t",mul[i][j]);}
printf("\n");
}
return0;
}

32. •Output

33. •SearchinganElementinanArray
➢LinearSearchorSequentialSearch
➢Fundamentalsteps:
1.Startwiththearray'stopmostelements.
2.Thetargetvalueshouldbecomparedtothecurrent
element.
3.Thesearchissuccessfulifthecurrentelement
matchestherequestedvalue,andthenthealgorithm
canreturntheelement'sindexoranyotherdesired
output.
4.Gotothefollowingelementinthearrayifthecurrent
elementdoesnotmatchthedesiredvalue.
5.Untilamatchismade,ortheendofthearrayisreached,
repeatsteps2-4.

34. #include<stdio.h>
intlinearSearch(intarr[],intn,inttarget){
for(inti=0;i<n;i++){
if(arr[i]==target){
returni;//Returntheindexifthetargetisfound
}}
return-1;}//Return-1ifthetargetisnotfound
intmain(){
intarr[]={5,2,8,12,3};
intn=sizeof(arr)/sizeof(arr[0]);/*Calculatethenumberofelementsin
thearray*/
inttarget=8;
intresult=linearSearch(arr,n,target);
if(result==-1){printf("Elementnotfound\n");}
else{printf("Elementfoundatindex%d\n",result);}
return0;}

35. •BinarySearch
➢Thistechniqueisutilizedtoquicklylocateaspecific
elementinasortedarrayorlist.
➢Itusesadivide-and-conquerstrategy,periodicallycutting
thesearchareainhalfuntilthetargetelementislocated
orfoundtobeabsent.
➢Steps:
1.Haveasortedarrayorlistasabase.
2.Establishtwopointers,leftandright,withtheirinitial
valuespointingtothearray'sfirstandendmembers.
3.Use(left+right)/2togettheindexofthecenterelement.
4.Comparethetargetvaluetothemiddleelement
a.Thesearchissuccessfuliftheyareequal,andthenthe
programcanreturntheindexoranyotherrequiredresult.

36. b.Therightpointershouldbemovedtothe
elementprecedingthemiddleelementifthe
middleelementisgreaterthanthetargetvalue.
c.Movetheleftpointertotheelementfollowing
themiddleelementifthemiddleelement'svalue
islessthanthetargetvalue.
5.Steps3and4shouldberepeateduntilthe
targetelementislocatedortheleftpointer
exceedstherightpointer.
6.Thedesiredelementisnotinthearrayifit
cannotbelocated.

37. #include<stdio.h>
intbinarySearch(intarr[],intleft,intright,inttarget){
while(left<=right){
intmid=left+(right-left)/2;
if(arr[mid]==target){
returnmid;/*Returntheindexifthetargetisfound*/}
if(arr[mid]<target){
left=mid+1;}else{
right=mid-1;
}
}
return-1;//Return-1ifthetargetisnotfound
}

38. intmain(){
intarr[]={2,5,8,12,20,23,28};
intn=sizeof(arr)/sizeof(arr[0]);/*Calculatethenumber
ofelementsinthearray*/
inttarget=20;
intresult=binarySearch(arr,0,n-1,target);
if(result==-1){
printf("Elementnotfound\n");}
else{
printf("Elementfoundatindex%d\n",result);}
return0;
}
•Output:Anelementfoundatindex4