Problem Solving
Techniques
Unit 1 Chapter 2
Dr. Salini Suresh
Associate Professor ,DSCASC
Unit 1 Chapter 2 :Fundamental Algorithms:
• Exchanging the values of two variables
• Counting
• Summation of a set of numbers
• Factorial Computation
• Generating of the Fibonacci sequence
• Reversing the digits of an integer
• Character to number conversion
1. Exchanging the values of two variables
Algorithm Development :
Consider the variable a and b assigned values as below
Task is to replace contents of a with 463 and b with 721
Assignment operator can be used to change values
a:= b -------(1) and b:=a ----------(2)
assignment has changed the value of a but has left value of b unchanged
assignment does not change value of b ,because current value of a is 463 only
ie , in assignment we have lost original value of a (721)
Exchanging the values of two
variables
• thus to solve this exchange problem we need to find a way not destroying
“ the old value of a “ .
• we can introduce temporary variable t ,copy original value of a in t before
step(1)
Exchanging the values of two
variables
Exchanging the values of two
variables
• Use of Intermediate temporary variable allows proper exchange of
two variables
• A common application is exchange of two array elements
C program for Exchanging the values of two
variables
#include <stdio.h>
void main()
{
int x, y, temp;
printf("Enter the value of x and y: ");
scanf("%d %d", &x, &y);
printf("Before swapping x=%d, y=%d ", x, y);
/*Swapping logic */
temp = x;
x = y;
y = temp;
printf("\n After swapping x=%d, y=%d", x, y);
}
C program for Exchanging the values of two
variables
Output
Counting
Algorithm Development
we can see that
Counting
the above equations (1) and (2) can be written as
Algorithm : Counting
1. Read the number of marks (n)to be processed.
2. Initialize count to zero.
3. While there are still marks to be processed repeatedly do (ie,n>0)
(a) Read next mark,
b) If it is a pass (i.e. >=50) then add one to count.
4. Write out total number of passes
Write a C program for counting
#include<stdio.h> if(n>=0)
void main() {
{ count=0;
int count,a[50],i,m,n; i=0;
const int passmark=50;
while(i<n)
{
printf("Enter no of students :");
if(a[i]>=passmark)
scanf("%d",&n);
{
printf("enter marks");
count=count+1;
for(i=0;i<n;i++) }
{ i++;
scanf("%d",&a[i]); }
} printf("number of passes: %d",count);
}
getch();
}
Output
Write a C program for counting
#include<stdio.h>
#include<conio.h>
void main()
{ int count=0,a[50],i,n;
const int passmark=50;
printf("Enter no of students :");
scanf("%d",&n);
printf("enter marks:\n");
for(i=0;i<n;i++)
{ scanf("%d",&a[i]); }
for(i=0; i<n; i++)
{ if(a[i]>=passmark) count=count+1; }
printf("number of passes: %d",count);}
Problem
Given set of n numbers
• Design algorithm that add these numbers And returns resultant sum
Algorithm Development
Assume n ≥0
Consider the expression ,s:=a+b+c
it adds three variables a,b,c with previously assigned values
In general we can write
This method is not practical as
• we may need to change value of n
• And computer arithmetic unit can add only two numbers at a time
So ,start adding first two numbers a1 and a2
Then add a3 to s
Similarly
actually we are repeating the same process again with values of a and s
change with each step
For i th step we have
General step can be placed in a loop to iteratively , generate the sum of
n numbers
Algorithm : Summation of set of numbers
[Link] n numbers to be summed
[Link] sum=0, i=0
[Link] i< n do repeatedly
a) read next number
b)Compute Sum=Sum+a, where a is current number to be
summed .
[Link] sum of n numbers
Summation of set of numbers
#include <stdio.h>
#include <conio.h>
void main()
{
int num, i, sum = 0;
printf(" Enter a positive number: ");
scanf("%d", &num);
for (i = 0; i <= num; i++)
{
sum = sum + i; // at each iteration the value of i is added to the sum variable
}
printf("\n Sum of the first %d number is: %d", num, sum);
getch();
}
Output
Summation of set of numbers
#include<stdio.h>
int main()
{
int n, sum = 0, i, a[50];
printf("Enter the number of integers you want to add: ");
scanf("%d", &n);
printf("\n\nEnter %d integers \n\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
sum =sum + a[i];
}
printf("\nSum = %d\n", sum);
Factorial Computation
Factorial Computation
For general i+1 th step we can write
general step can be placed in loop and to iteratively generate n
Algorithm: Factorial of a number
1. Read number n whose factorial to be found
2. Initialize fact=1 and i=1
3: Repeat Until i<=n
fact=fact*i
i=i+1
4: Print fact
Note: Instead of variable p ,in algorithm variable fact is used
C program -Factorial of a
number
#include<stdio.h>
int main()
{ int i,fact=1,number;
printf("Enter a number: ");
scanf("%d",&number);
for(i=1;i<=number;i++)
{ fact=fact*i; }
printf("Factorial of %d is: %d",number,fact);
return 0; }
C program -Factorial of a number
#include <stdio.h>
int main() {
int n, i;
unsigned long long fact = 1;
printf("Enter an integer: ");
scanf("%d", &n);
// shows error if the user enters a negative integer
if (n < 0)
printf("Error! Factorial of a negative number doesn't exist.");
else {
for (i = 1; i <= n; ++i) {
fact *= i;
}
printf("Factorial of %d = %llu", n, fact);
}
return 0;
}
Generation of Fibonacci sequence
To generate the fourth term (next Fibonacci number ) apply same definition again
Fourth number is derived from
sum of second number (term before preceding term) +third number (preceding term)
Basic mechanism :
Algorithm: Generate Fibonacci
series
1: Declare variable a, b, c, n, i
2: Initialize variable a=0, b=1 and i=2
3: Read n from user
4: Print a and b
5: Repeat until i<=n :
c=a+b
print c
a=b, b=c
i=i+1
C program to Generate Fibonacci series
#include<stdio.h>
void main()
{
int a=0,b=1,c,i,n;
printf("Enter the number of elements:");
scanf("%d",&n);
printf("\n%d %d",a,b);//printing 0 and 1
for(i=2;i<n;++i)//loop starts from 2 because 0 and 1 are already printed
{
c=a+b;
printf(" %d",c);
a=b;
b=c ;
}
}
Consider n=27953
To reverse the number We need to iteratively access individual digits of
input no
for that we need to extract the LSD (rightmost digit) from the number
3 is the LSD of 27953
The mod function returns the remainder after division
So,
And
let variable dreverse used to build the reversed integer.
To build the reverse integer use we can use the construct:
dreverse= (previous value of dreverse *10) + most recently extracted rightmost digit
let variable dreverse used to build the reveresed integer. To build reversed integer we can use the construct:
Step 1:
r= 27953 mod 10=3 , n=27953 div 10 =2795
for step 1, dreverese=(0*10) + 3 =3
Now new number =2795
Step 2: r= 2795 mod 10=5, n=2795 div 10 =279
So extracted LSD (rightmost digit) =5
previous value of dreverse =3
dreverese=(3*10) + 5 =3 5
Now new number =279
Step(ite n r dreverse Reverse
ration) number being reversed extracted rightmost number
digit (LSD) dreverse= (previous value of constructed
n=n div 10 dreverse *10) + most
n mod 10 recently extracted rightmost
digit
1 27953 div 10 =2795 27953 mod 10=3 dreverese=(0*10) + 3 =3 3
2 2795 div 10 =279 2795 mod 10=5 dreverese=(3*10) + 5 =35 35
3 279 div 10 =27 279 mod 10= 9 dreverese=(35*10) + 9 =359 359
4 27 div 10 =2 27 mod 10= 7 dreverese=(359*10) + 7 3597
=3597
5 2 2 mod 10= 2 dreverese=(3597*10) + 2 35972
=35972
Continuing the process we get
Algorithm: To Reverse digits of an integer
[Link] n ,positive integer to be reversed
[Link]=0
[Link] n>0
a)extract rightmost digit of number using mod function, r=n mod 10
b)reverse= (reverse *10) + most recently extracted rightmost digit
c)use integer division by 10 to remove rightmost digit from number
n=n div 10
d) dreverse=reverse
C program to Reverse digits of an
integer
#include <stdio.h>
int main() {
int n, reverse = 0, r;
printf("Enter an integer: ");
scanf("%d", &n);
while (n>0) {
r = n % 10;
reverse = reverse * 10 + r;
n =n / 10;
}
printf("Reversed number = %d", reverse);
return 0;
}
Algorithm Development
task is to accept input character representation of an integer
and convert to conventional decimal representation
one of the most widely used coding systems for characters is
8 bit code ASCII code .
American Standard Code for Information Interchange.
in many applications numbers are represented as sequence of characters
for eg:
23 april 1984
some times it is required to perform arithmetic calculations on numbers represented
as sequence of 8 bit characters
here 23 does not have value of 2 tens and 3 units
but
Decimal values 50 and 51 in successive 8 bit bytes
Also
Arithmetic operations cannot be performed on character code
So the solution is to convert character representations to decimal representation
Consider
1984
to get decimal digit ,
1) subtract 48 (ascii value of character 0 ) from ascii value of each character
49-48=1
57-48=9
56-48=8
52-48=4
2)use the digits to construct corresponding decimal no
start processing from leftmost character
multiply previous decimal value by 10 and adding current decimal digit
Ie ,we shift current decimal value to left one digit and add digit for current character
Algorithm: Character to number Conversion
[Link] character string of length n to convert to decimal
[Link] decimal value to 0
[Link] base0 value to ascii
4. while n>0
a)convert next character to decimal digit
b)shift current decimal value to left one digit and add digit for
current character
5. Return decimal integer corresponding to input character