GR24 Programming for Problem Solving Lecture Material PDF

GOKARAJU RANGARAJU INSTITUTEOF ENGINEERING ANDTECHNOLOGY (Autonomous) PROGRAMMING FOR PROBLEM SOLVING (GR24A1006) LECTURE MATERIAL B. Tech I Year (CSE,ECE,EEE,IT,CE,ME,DS,AIML)  Preface The m...

GOKARAJU RANGARAJU INSTITUTEOF ENGINEERING ANDTECHNOLOGY (Autonomous) PROGRAMMING FOR PROBLEM SOLVING (GR24A1006) LECTURE MATERIAL B. Tech I Year (CSE,ECE,EEE,IT,CE,ME,DS,AIML)  Preface The main objective of the course entitled “Programming for Problem Solving” is to make first year B.Tech students familiar with the Computer Programming concepts and language fundamentals in a more systematic manner. This material is written according to GRIET GR-24(Autonomous) syllabus. This book has been prepared to meet the requirements of Programming for Problem Solving This work is Contributed and verified by the faculty of CPDS- CSE/ECE/CSD/CSM 1. S T G Y.Sandhya 2. D. SugunaKumari 3. R.S.Shalini 4. G.Vandhana 5. N.Sashi Prabha 6. V.Vijay Kumar 7. M.Mounica 8. K.Shoban Babu 9. M.Sunitha  UNIT-I Unit-1: Introduction to Programming Introduction to Algorithms: Representation of Algorithm, Flowchart , Pseudo code with examples, compiling & executing program, syntax and logical errors. Introduction to C Programming Language: Structure of c program, variables, data types, constants, Operators, expressions and precedence, Expression evaluation, type conversion. I/O: Simple input and output with formatted I/O and unformatted I/O. Representation of Algorithm Flowchart and Pseudo code with Examples: Algorithm: Algorithm is a finite set of instructions that , if followed accomplishes a particular task. The same problem can be solved with different methods. So, to solve a problem different algorithms, may be accomplished. Algorithm may vary in time. User writes algorithm in his / her own language. So ,it can not be executed on computer. Algorithm should be in sufficient detail that it can be easily translated into any language. Characteristics or properties of Algorithm: Input:Zero or more quantities are externally supplied. Output: At least one quantity is produced. Definiteness: Each instruction is clear and unambiguous. Ex:Add B or C to. Finiteness : Algorithm should terminate after finite number of steps. Effectiveness : Every Instruction must be basic. i.e., it can be carried out, by a person using Pencil and paper. Advantages of Algorithms: 1. It provides the core solution to a given problem. the solution can be implemented on a computer system using any programming language of user’s choice. 2. It facilitates program development by acting as a design document or a blue print of a given problem solution. 3. Itensureseasycomprehensionofaproblemsolutionascomparedtoanequivalent computer program. 4. It eases identification and removal of logical errors in a program. 5. It facilitates algorithm analysis to find out the most efficient solution to a given problem. Disadvantages of Algorithms: 1. In large algorithms the flow of program control becomes difficult to track. 2. Algorithms lack visual representation of programming constructs like flowcharts. 3. Understanding the logic becomes relatively difficult. Examples: Example1 : Add two numbers. Step 1: Start Step 2: Read 2 numbers as A and B Step 3: Add numbers A and B and store result in C Step 4 :Display C Step 5: Stop Example2: Average of 3 numbers. Step 1.Start Step 2.Read the numbers a , b , c Step 3.Compute the sum and divide by 3 Step 4.Store the result in variable d Step 5.Print value of d Step 6.End Example 3: Average of n Natural numbers. Step 1:Start Step 2:Read the number n Step 3:Initialize i to Zero Step 4:Initialize sum to zero Step 5:If i is greater than n Step 6:Read a Step7:Add a to sum and go to step 5 Step 9: Divide the Sum by n and store the result in avg Step 10:Print value of Avg Step 11:End Flowchart: A Flowchart is a Visual representation of the sequence of steps for solving a problem. A flowchart is a set of symbols that indicate various operations in the program.For every process, there is a corresponding symbol in the flowchart. A pictorial representation of a textual algorithm is done using a flowchart. A flowchart gives a pictorial representation of an algorithm. The first flowchart is made by John Von Neumann in 1945.It is a symbolic diagram of operations sequence, dataflow, control flow and processing logic in information processing. The symbols used are simple and easy to learn. It is a very helpful tool for programmers and beginners. Purpose of a Flowchart : 1. Provides communication. 2. Provides an overview. 3. Shows all elements and their relationships. 4. Quick method of showing program flow. 5. Checks program logic. 6. Facilitates coding. 7. Provides program revision. 8. Provides program documentation. 9. Advantages of a Flowchart : 10. Flowchart is an important aid in the development of an algorithm itself. 11. Easier to understand than a program itself. 12. Independent of any particular programming language. 13. Proper documentation. 14. Proper debugging. 15. Easy and clear presentation. Limitations of a Flowchart : Complex logic. 1. Drawing is time consuming. 2. Difficult to draw and remember. 3. Technical detail. Symbols : Symbols are divided in to the following two parts. Auxiliary Symbols. Primary Symbols. FLOWCHART SYMBOLS: Prepare an algorithm and flow chart for swapping two numbers To Swap two integer numbers: Algorithm : Using third variable Step 1 : Start Step 2 : Input num1 , num2 Step 3 : Temp = num1 Step 4 : num1 = num2 Step 5 : num2 =Temp Step 6 : Output num1 , num2 Step 7 : Stop Flowcharts Develop an algorithm and flowchart to find the largest among two numbers. Ans: Algorithm: Step 1: Start Step 2: Input A , B Step 3 : if A > B then output A else output B Step 4 : Stop Flowchart : Develop an algorithm and flowchart to find the largest among three numbers. Algorithm: Step 1 : Start Step 2 :Input A, B, C Step 3 :If A > B go to step 4 ,otherwise go to step 5. Step 4 :if A > C go to step 6,otherwise go to step 8 Step 5 :if B > C goto step 7,otherwise go to step 8 Step 6 : print A is largest and go to step9 Step 7 : print B is largest and go to step9 Step 8 : print C is largest and go to step9 Step 9 :Stop Flowchart: Simulate an algorithm and flowchart to find factorial of a number Flowchart: Algorithm: Step 1:Start Step 2:Input n Step 3:Initialize counter variable, i , to 1 and factors = 1 Step 4:if i=y (x=4,y=7) 1 == is equal to 8==8 1 != is not equal to 6!=5 1 When arithmetic expression are used on either side of a relational operator, the arithmetic expression will be evaluated first and then the results compared, that means arithmetic operators have a higher priority over relational operators. Logical Operator: C has 3 logical operators. The logical operators are used when we want to test more than one condition and make decisions. The operators are as follows: Operator Meaning Example Result && Logical AND 4>3 && 5!=6 1 || Logical OR 5b) ?a: b; o/p:- Big will be assigned the value of b (45) since a>b is false. Bitwise Operators: C supports a special operator known as bitwise operators for manipulation of data at bit level. These operators are used for testing the bits or shifting them right to left. Note: Bitwise operators may not be applied to float or double. Operator Meaning Example & Bitwise AND X&y | Bitwise OR x|y ^ Bitwise exclusive OR X^y >y ~ Bitwise ones complement ~y Special operators: C supports some special operators such as comma operator, size of operator, pointer operators(& and *) and member selection operators (. and -> ). comma operator: The comma operator is used to link the related expressions together. A comma- linked list of expressions is evaluated left to right and the value of right- most expression is the value of the combined expression. For example, the statement value = (x=10, y=5, x+y); This statement first assigns the value 10 to x, then assigns 5 to y and finally assigns 15. In for loops: for (n=1 , m=10; n,=, BITWISE SHIFT RIGHT RIGHT 6 < RELATIONAL OPERATORS LESSER GREATER THAN >= GREATER THAN OR EQUAL TO 7 == IS EQUAL TO LEFT TO != IS NOT EQUAL TO RIGHT 8 & BITWISE AND LEFT TO RIGHT 9 ^ BITWISE XOR LEFT TO RIGHT 10 | BITWISE OR LEFT TO RIGHT 11 && LOGICAL AND LEFT TO RIGHT 12 || LOGICAL OR LEFT TO RIGHT 13 ?: TERANARY LEFT TO RIGHT 14 = ASSIGNMENT OPERATOR SIMPLE += ASSIGNMENT BY SUM -= ASSIGNMENT BY DIFFERENCE *= ASSIGNMENT BY PRODUCT RIGHT TO LEFT /= ASSIGNMENT BY QUOTIENT %= ASSIGNMENT BY REMAINDER >= ASSIGNMENT BY BITWISE RIGHT SHIFT  &= ASSIGNMENT BY BITWISE AND ^= ASSIGNMENT BY BITWISE XOR |= ASSIGNMENT BY BITWISE OR 15 , COMMA LEFT TO RIGHT For Example: i= 2*3/4+4/4+8-2+5/8 i=6/4+4+8-2+5/8 i=1+4/4+8-2+5/8 i=1+1+8-2+5/8 i=1+1+8-2+0 i=2+8-2+0 i=10-2+0 i=8+0 i=8 Type conversion: It is a process of converting a variable value or a constant value temporarily from one data type to other data type for the purpose of calculation is known as type conversion. There are two types of conversions. Automatic type conversion (or) Implicit conversion. Type Casting (or) explicit conversion (or) manual conversion. Implicit: In this lower data type can be converted into higher data type automatically. The figure below shows the C conversion hierarchy for implicit –type conversion in an expression: The sequence of rules that are applied while implicit type conversion is as follows: All short and char are automatically converted into int then if one of the operands is long double the other will be converted to long double and the result will be long double. else, if one of the operand is double, the other will be converted to double and the result will be double. else, if one of the operand is float ,the other will be converted to float and the result will be float. else, if one of the operand is unsigned long int, the other will be converted to unsigned long int and the result will be unsigned long int. else, if one of the operand is long int, the other is unsigned int then if unsigned int can be converted into long int, the unsigned int operand will be converted as such and the result will be long int. else both operands will be converted to unsigned long int and the result will be unsigned long int. else if one of the operand is long int ,the other will be converted into long int and the result will be long int. else if one of the operand unsigned int ,the other will be converted into unsigned int and the result will be unsigned int. The final result of an expression is converted to the type of the variable on the left of the assignment sign before assigning the value to it. The following changes are introduced during the final assignment. float to int causes truncation of the fractional part double to float causes rounding of digits long int to int causes dropping of the excess higher order bits. Example : Consider the following variables along with their datatypes: int i,x; float f; double d; longint l; Explicit: In this type of conversion, the programmer can convert one data type to other datatype explicitly.Such conversions are also known as forced conversions or manual conversions or type casting. Syntax: (datatype) (expression) Expression can be a constant or a variable Ex:y = (int) (a+b) y= cos(double(x)) double a = 6.5; double b = 6.5; int result = (int) (a) + (int) (b); result = 12 instead of 13. int a=10; float(a)> 10.00000 Example: //converting fahrenheit to Celsius by type casting #include #include void main() { float c,f; clrscr(); printf("\n enter Fahrenheit:"); scanf("%f",&f); c=(float)5/9*(f-32); printf("\n c=%f",c); getch(); } Managing Input and Output: Managing input and output operations: Reading, processing and writing of data are the three essential functions of a computer program. Most programs take some data as input and display the processed data. We have two methods of providing data to the program variables. One method is to assign values to variables through the assignment statements like x=5, a=0 and so on. Another method is to use the input function scanf, which can read data from a keyboard. We have used both the methods in programs. For outputting results, we have used extensively the function printf, which sends results out to a terminal. Input – Output functions: The program takes some I/P- data, process it and gives the O/P.We have two methods for providing data to the program Assigning the data to the variables in a program. By using I/P-O/P statements. C language has 2 types of I/O statements. All these operations are carried out through function calls. 1.Unformatted I/O statements 2.Formatted I/O statements Unformatted I/O statements: i/p function o/p function getchar() putchar() gets() puts() getc() putc() getw() putw() getch() putch() getche() getchar ( ):- It reads single character from standard input device. This function don‘t require any arguments. Syntax : - char variable _name = getchar( ); Ex:- char x; x = getchar( ); putchar ( ):- This function is used to display one character at a time on the standard output device.Syntax:-putchar(variable_name); Ex:- char x; putchar(x); program: void main( ) { char ch; printf("enter a character:"); ch=getchar( ); printf("\ncharacter is:"); putchar(ch); } Output: enter a character: a character is a gets( ):- This function is used to read group of characters(string) from the standard I/P device. Syntax:-gets(string name); Ex:- gets(s); puts( ):- This function is used to display string to the standard O/P device. Syntax:-puts(string name); Ex:- puts(s); program: void main() { char s; puts(“enter name”); gets(s); puts(“print name:”); puts(s); } Output: enter name ramu print name : ramu getch():- This function reads a single character directly from the keyboard without displaying onthe screen. This function is used at the end of the program for displaying the output (without pressing (Alt- F5). Syntax: char variable_name = getch(); Ex:- char c; c = getch(); getche():- This function reads a single character from the keyboard and echoes(displays) it tothe current text window. Syntax:-char variable_name = getche(); Ex:- char c; c = getche(); Program: void main() { char ch, c; printf("enter char"); ch = getch(); printf("%c", ch); printf("enter char"); c = getche(); printf("%c",c); } Output :- enter character a enter character b b Character test functions: ctype.h Function Test isalnum(c) Is c an alphanumeric character? isalpha(c) Is c an alphabetic character isdigit(c) Is c a digit? islower(c) Is c alower case letter? isprint(c) Is c a character? ispunct(c) Is c a punctuation mark?  isspace(c) Is c a white space character? isupper(c) Is c an upper case letter? tolower(c) Convert c to lower case toupper(c) Convert c to upper case program: void main() { char a,x; printf(“enter char”); a = getchar(); if (isupper(a)) { x= tolower(a); putchar(x); } else putchar(toupper(a)); } Output:- enter char A a Formatted I/O Functions: Formatted I/O refers to input and output that has been arranged ina particular format. Formatted I/P functions scanf( ), fscanf() Formatted O/P functions printf( ) ,fprintf() scanf( ) :-scanf() function is used to read information from the standard I/P device. Syntax:-scanf(“controlstring”, &variable_names); Control string (also known as format string) represents the type of data that the user is going to accept and gives the address of variable. (char-%c , int-%d , float - %f , double-%lf). Control string and variables are separated by commas. Control string and the variables going to I/P should match with each other. Ex:-int n; scanf(“%d”,&n); Inputting Integer Numbers: The field specification for reading an integer number is: %w d The percentage sign(%) indicates that a conversion specification follows. w is an integer number that specifies the field width of the number to be read and d known as data type character indicates that the number to be read is in integer mode. Ex:-scanf(“%2d,%5d”,&a,&b); The following data are entered at the console: 50 31426 Here the value 50 is assigned to a and 31426 to b Inputting Real Numbers: The field width of real numbers is not to be specified unlike integers. Therefore scanf reads real numbers using the simple specification %f. Ex: scanf(“%f %f”,&x,&y); Suppose the following data are entered as input: 23.45 34.5 The value 23.45 is assigned to x and 34.5 is assigned to y. Inputting character strings: The field specification for reading character strings is %ws or %wc %c may be used to read a single character. Ex:scanf(“%s”,name1); Suppose the following data is entered as input:Griet Griet is assigned to name1. Formatted Output: printf( ): This function is used to output any combination of data. The outputs are produced insuch a way that they are understandable and are in an easy to use form. It is necessary for the programmer to give clarity of the output produced by his program. Syntax:- printf(“control string”, var1,var2……); Control string consists of 3 types of items Characters that will be printed on the screen as they appear. Format specifications that define the O/P format for display of each item. Escape sequence chars such as \n , \t and \b….. The control string indicates how many arguments follow and what their types are. The var1, var2 etc..are variables whose values are formatted and printed according to the specifications of the control string. The arguments should match in number, order and type with the format specifications Example Program: #include int main() { printf("%s\n","program"); printf("%3s\n","program") ; printf("%12s\n","program"); printf("%-12s\n","program"); printf("%12.3s\n","program"); return 0; } Output :- progra m progra m progra m program pro  UNIT-II Conditional Branching and Loops: Conditional branching with if, if-else, nested if else, else if ladder, switch-case, loops : for, while, do-while, jumping statements: goto, break, continue. Arrays: one and two dimensional arrays, creating, accessing and manipulating elements of arrays. Searching: Basic searching in an array of elements, linear and binary search. Conditional Branching and Loops: Writing and Evaluation of conditional statements (examples). In C, when a logical operation is being evaluated, if the result is known before all sub expressions have been evaluated, then the evaluation stops, or short circuits. The two situations where this can occur is when the first expression of a logical AND operation is FALSE (zero) or the first expression of a logical OR operation is TRUE (non-zero). In both of these cases, the result is already known. For AND, if either of the two expressions is FALSE, the result will be FALSE. For OR, if either of the two expressions is TRUE, then the result will be TRUE. Example : If we have two expressions being tested in a logical AND operation: expr1 && expr2 The expressions are evaluated from left to right. If expr1is 0 (FALSE), then expr2would not be evaluated at all since the overall result is already known to be false. Truth table for AND (&&) FALSE=0 TRUE=1 expr1 expr2 Result 0 X (0) 0 0 X (1) 0 1 0 0 1 1 1 Expr2 is not evaluated in the first two cases since its value is not relevant to the result. Examples: 1.if (5 || ++x) { printf("%d\n",x); } 2.int x=0; if(5||2&&++x) printf("%d", x); 3.(a >= 0) && (b < 10) 4.(a > b) || (b++ / 3) 5. (13 * a) * (b/13 –1) 6 if((a || b || c || d || e || f || g || h ||i|| j || k)==1) 7.while((x &&y)==1) 8. if ((x < 10) && (y > 3)) What are control structures: Control Structures / Statements In C Language A program is nothing but the execution of sequence of one or more instructions. Quite often, it is desirable to alter the sequence of the statements in the program depending upon certain circumstances. (i.e., we have a number of situations where we may have to change the order of execution of statements based on certain conditions) (Or)Repeat a group of statements until certain specified conditions are met. This involves a kind of decision making to see whether a particular condition has occurred or not and direct the computer to execute certain statements accordingly. Based on application, it is necessary / essential To alter the flow of a program Test the logical conditions Control the flow of execution as per the selection these conditions can be placed in the program using decision-making statements. “C” SUPPORTS MAINLY THREE TYPES OF CONTROL STATEMENTS. 1. Decision making statements Simple if Statement if – else Statement Nested if-else statement else – if Ladder switch statement 2. Loop control statements for Loop while Loop do-while Loop  3. Unconditional control statements goto Statement break Statement continue Statement return statement Conditional Branching: Conditional statements help you to make decision based on certain conditions. These conditions are specified by a set of conditional statements having Boolean expressions which are evaluated to a Boolean value true or false. When we need to execute a block of statements only when a given condition is true and skip some statements when the condition is false ,we then use branching or selection control structures in c. There are the following types of conditional statements in C. Simple if statement. if…else statement. Nested if…else statement. else if ladder switch case if statement if statement is used for branching when a single condition is to be checked. The condition enclosed in if statement decides the sequence of execution of instruction. If the condition is true, the statements inside if statement are executed, otherwise they are skipped. In C programming language, any non zero value is considered as true and zero or null is considered false. Syntax of if statement if (condition) { statements;......... } Stmt x; if is the keyword.is a relational expression or logical expression or any expression that returns either true or false. It is important to note that the condition should be enclosed within parentheses ‘(‘ and ’)’. The stmt block can be a simple statement or a compound statement or a null statement. stmt-x is any valid C statement. The flow of control using simple if statement is determined as follows: Whenever simple if statement is encountered, first the condition is tested. It returns either true or false. If the condition is false, the control transfers directly to stmt-x without considering the stmt block. If the condition is true,the control enters into the stmtblock.Once,the endof stmt block is reached, the control transfers to stmt-x.  Flowchart of if statement Example of if statement Example 1: C program to print the square of a number if it is less than 10. #include void main() { int age; printf("enter age\n"); scanf("%d",&age); if(age>=55) printf("person is retired\n"); printf(“END”); } Output: enter age 57 person is retired END Example 2: C program to print the square of a number if it is less than 10. #include int main() { int n; printf("Enter a number:"); scanf("%d",&n); if(n=55) printf("person is retired\n"); else printf("person is not retired\n"); return 0; } Output: enter age 47 person is not retired Example2:C program to find if a number is odd or even. #include int main() { int n; printf("Enter a number:"); scanf("%d",&n); if(n%2 == 0) printf("%d is even",n); else printf("%d is odd",n); return 0; } Output: Enter a number:5 5 is odd Nested if Statements: When a if statement is kept inside another if statement, it is called nested if statement. Nested if statements are used if there is a sub condition to be tested. The depth of nested if statements depends upon the number of conditions to be checked. Syntax of nested if statement if (condition 1) { statements; if (sub condition 1) { statements; } statements; } else if (condition 2) { statements; if (sub condition 2) { statements; } statements; }.................. else { statements; if (sub condition n) { statements; } statements; } Flow chart: Example Write a c program to print largest of three numbers: #include int main ( ) { int a, b,c; scanf("%d%d%d",&a,&b,&c); if(a>b) {  if(a>c) Printf(“%d is big\n”,a); else printf("%d is big\n", b); } else { if(c>b) { printf("%d is big\n" , c); else printf("%d is big\n" , b); }eturn 0; } Output: 10 20 30 30 is big Example: Write a c program if the number is even or odd, and then if it is even, whether it is divisible by 4 or not, and if it is odd, whether it is divisible by 3 or not. #include int main() { int n; scanf("%d",&n); if (n % 2 == 0) { printf("Even "); if (n % 4 == 0) { printf("and divisible by 4"); } else { printf("and not divisible by 4"); } } else {  printf("Odd "); if(n % 3 == 0) { printf("and divisible by 3"); } else { printf("and not divisible by 3"); } } return 0; } Output: 4 Even and divisible by 4 else if ladder statement It is used when more than one condition is to be checked. A block of statement is enclosed inside if, else if and else part. Conditions are checked in each if and else if part. If the condition is true, the statements inside that block are executed. If none of the conditions are true, the statements inside else block are executed. A if … else if … else statement must have only one if block but can have as many else if block as required. Else part is optional and may be present or absent. Syntax of else if ladder statement if (condition 1) { statements;......... } else if (condition 2) { statements;......... }.................. else if (condition n) { statements;......... }else { statements;......... } Flow chart: Example: #include int main() { int day; printf("Enter day number: "); scanf("%d", &day); if(day==1) { printf("SUNDAY."); } else if(day==2) { printf("MONDAY."); } else if(day==3) { printf("TUESDAY."); } else if(day==4) { printf("WEDNESDAY."); } else if(day==5) { printf("THURSDAY."); } else if(day==6) { printf("FRIDAY."); } else if(day==7) { printf("SATURDAY."); } else { Printf(“INVALID DAY”); } return(0); } OUTPUT: Enter day number: 4 WEDNESDAY Example Program: void main() { int m1,m2,m3,avg,tot; printf("enter three subject marks "); scanf("%d%d%d", &m1,&m2,&m3); tot=m1+m2+m3; avg=tot/3; if(avg>=75) { printf("distinction"); } else if(avg>=60 && avg=50 && avg