60-140
Introduction to Algorithms and Programming I
Dr. Christie Ezeife
Lab
Exercises #2 Solution (Lab Date: Week 4 of Classes)
Objectives are to:
1. Practise on solving problems and writing simple algorithmic and C
program solutions for the problems by going through the problem solving steps
as taught in chapter 2 of text book.
2. Practise on the use of arithmetic, logical, relational, bitwise,
increment and decrement operators in C’s expressions and assignment
instructions as taught in chapter 3 of book.
Que. 1.
Solve the following problem by going through the problem solving steps.
Write a program to accept two 4-digit integer numbers and generates one new integer number where each corresponding digit of the output number is the sum of the two corresponding digits of the two input numbers divided by 2. For example, if the input numbers are 3155 and 4998, the output number to be printed by your program is 3576. Hint: Note that to solve, the digits of each integer number have to first be extracted using the integer modulus and division arithmetic and later, the digits of the resulting integer number have to be put together.
Solution
to Que 1
Step
1: Problem Requirements Definition:
Given two 4 digit numbers, print an output number where the corresponding
digits of output number are obtained as the sum of the corresponding digits of
the input numbers divided by 2. For example, with the input numbers 3155 and
4998, the output number is 3576.
Step
2: Problem Components Identification: Identify all input, output data and their types as well as relationships
between input and output data in equations:
Input
data are:
number1 (integer)
number2 (integer)
Output data are:
number3 (integer)
Intermediate data:
digit1of1,
digit2of1, digit3of1, digit4of1, digit1of2, digit2of2, digit3of2, digit4of2 (integer)
digit1of3,
digit2of3, digit3of3, digit4of4 (integer)
new_num1,
new_num2 (integer)
Relationships
Equations that link output data
variables on the left hand side with input data variables on the right hand
side in the correct logical order they will work are:
Separate
digits of input numbers using integer division and modulus operations.
new_num1 =
number1
/* make a copy
of num1 */
digit4of1 = new_num1 %
10 /* this has the last digit of num1 */
new_num1 = new_num1 / 10 /* now has the
first three digits of num1 */
digit3of1 = new_num1 %
10 /* this has the 3rd digit of num1 */
new_num1 = new_num1 / 10 /* now has the
first two digits of num1 */
digit2of1 = new_num1 %
10 /* this has the 2nd digit of num1 */
digit2of1 = new_num1 / 10 /*
now has the first digit of num1 */
Do the
same for the second number2
new_num2 =
number2 /* make a copy of num2 */
digit4of2 = new_num2 %
10 /* this has the last digit of num2 */
new_num2 = new_num2 / 10 /* now has the
first three digits of num2 */
digit3of2 = new_num2 %
10 /* this has the 3rd digit of num2 */
new_num2 = new_num2 / 10 /* now has the
first two digits of num2 */
digit2of2 = new_num2 %
10 /* this has the 2nd digit of num2 */
digit2of2 = new_num2 / 10 /*
now has the first digit of num2 */
Now, get
the digits of the
number3, which is the result and put them together as one integer.
digit1of3
= (digit1of1 + digit1of2)/2
digit2of3
= (digit2of1 + digit2of2)/2
digit3of3
= (digit3of1 + digit3of2)/2
digit4of3
= (digit4of1 + digit4of2)/2
number3 =
(digit1of3 * 1000) + (digit2of3 * 100) + (digit3of3 * 10) + digit4of3
Step
3: No need to break the problem
solution into smaller modules now.
Step 4: Algorithm Design: Write the algorithmic solution
using the template for an algorithm similar to the formal algorithmic structure
in Figure 3.1 of text book. Use the following template now.
Main
Module
{
Input data are:
number1 (integer)
number2 (integer)
Output data are:
number3 (integer)
Intermediate data:
digit1of1,
digit2of1, digit3of1, digit4of1, digit1of2, digit2of2, digit3of2, digit4of2 (integer)
digit1of3,
digit2of3, digit3of3, digit4of4 (integer)
new_num1,
new_num2 (integer)
/*
Instructions follow: */
Read (number1, number2);
Separate
digits of input numbers using integer division and modulus operations.
new_num1 =
number1
/* make a copy
of num1 */
digit4of1 = new_num1 %
10 /* this has the last digit of num1 */
new_num1 = new_num1 / 10 /* now has the
first three digits of num1 */
digit3of1 = new_num1 %
10 /* this has the 3rd digit of num1 */
new_num1 = new_num1 / 10 /* now has the
first two digits of num1 */
digit2of1 = new_num1 %
10 /* this has the 2nd digit of num1 */
new_num1 = new_num1 / 10 /* now has the
first digit of num1 */
Do the
same for the second number2
new_num2 =
number2 /* make a copy of num2 */
digit4of2 = new_num2 %
10 /* this has the last digit of num2 */
new_num2 = new_num2 / 10 /* now has the
first three digits of num2 */
digit3of2 = new_num2 %
10 /* this has the 3rd digit of num2 */
new_num2 = new_num2 / 10 /* now has the
first two digits of num2 */
digit2of2 = new_num2 %
10 /* this has the 2nd digit of num2 */
new_num2 = new_num2 / 10 /* now has the
first digit of num2 */
Now, get
the digits of the
number3, which is the result and put them together as one integer.
digit1of3
= (digit1of1 + digit1of2)/2
digit2of3
= (digit2of1 + digit2of2)/2
digit3of3
= (digit3of1 + digit3of2)/2
digit4of3
= (digit4of1 + digit4of2)/2
number3 =
(digit1of3 * 1000) + (digit2of3 * 100) + (digit3of3 * 10) + digit4of3
Print
(number3);
}
Step 5: Coding: Now, translate the algorithm you have written in
step 4 above into a C program using the following template that is similar to
the general structure of a C program presented in Figure 3.2 of text book.
#include <stdio.h>
int main(void)
{
/* Problem Definition: Given two 4 digit numbers,
print an output number where
the corresponding digits of output
number are obtained as the sum of the
corresponding digits of the input numbers
divided by 2. For example, with the
input numbers 3155 and 4998, the
output number is 3576.
*/
/* Now declare the input and output variables using int or float */
/* Remember to end every
instruction with a semi-colon.*/
/* input
and output variables */
int number1, number2,
number3;
/*
Intermediate variables
*/
int digit1of1, digit2of1,
digit3of1, digit4of1, digit1of2, digit2of2, digit3of2, digit4of2;
int digit1of3, digit2of3,
digit3of3, digit4of3;
int new_num1, new_num2;
/* Executable Instructions follow: */
scanf ("%d %d",
&number1, &number2);
/* Separate digits of input numbers using integer division and modulus
operations*/
new_num1 = number1;
/* make a copy of num1
*/
digit4of1 = new_num1 % 10; /* this has the last
digit of num1 */
new_num1 = new_num1 / 10; /* now has the
first three digits of num1 */
digit3of1 = new_num1 % 10; /* this has the 3rd
digit of num1 */
new_num1 = new_num1 / 10; /* now has the first two digits of
num1 */
digit2of1 = new_num1 % 10; /* this has the 2nd
digit of num1 */
digit1of1 = new_num1 / 10; /* now has the first
digit of num1 */
/* Do the same for the second number2 */
new_num2 = number2;
/* make a copy of
num2 */
digit4of2 = new_num2 % 10; /* this has the last
digit of num2 */
new_num2 = new_num2 / 10; /* now has the
first three digits of num2 */
digit3of2 = new_num2 % 10; /* this has the 3rd
digit of num2 */
new_num2 = new_num2 / 10; /* now has the
first two digits of num2 */
digit2of2 = new_num2 % 10; /* this has the 2nd
digit of num2 */
digit1of2 = new_num2 / 10; /* now has the first
digit of num2 */
/* Now, get the digits of the number3, which is the result
and put them together as
one integer.*/
digit1of3 = (digit1of1 + digit1of2)/2;
digit2of3 = (digit2of1 + digit2of2)/2;
digit3of3 = (digit3of1 + digit3of2)/2;
digit4of3 = (digit4of1 + digit4of2)/2;
number3 = (digit1of3 * 1000) + (digit2of3 * 100) +
(digit3of3 * 10) + digit4of3;
printf ("The resulting number is
%d \n", number3);
return 0;
}
Step 6: Testing and Verification (also by Tracing): Now, type the program in 5,
compile and run with a set of test input data. You may use the following set of
test data:
Number1 = 3155
and Number2=
4998
Number1 = 1234 and Number2=
5679
Show the results of your program in a script file.
There are two ways to test and verify a
program. One is by running the
program and showing the results of the runs in a script file and the other is
by tracing through the program with hand and showing the result of the
run.
a. The script file run of the program is shown
below.
sol:~/bk2010/programs>script
lab2script
Script started, file is lab2script
sol:~/bk2010/programs>cc
lab2slnq1.c
sol:~/bk2010/programs>a.out
3155 4998
The resulting number is 3576
sol:~/bk2010/programs>!a
a.out
1234 5679
The resulting number is 3456
sol:~/bk2010/programs>exit
exit
Script done, file is lab2script
sol:~/bk2010/programs>
b.Tracing through the program with sample data number1
= 3155 and number2 = 4998 which are read with the scanf
instruction after the declaration of variables in the program.
The
instructions of the program executed in sequence with these input data are:
new_num1 = number1; => new_num1 = 3155
digit4of1 = new_num1 % 10 ; => digit4of1 = 3155 % 10 = 5
new_num1 = new_num1 / 10; => new_num1 = 3155 / 10 = 315
digit3of1 = new_num1 % 10; => digit3of1 = 315 % 10 = 5
new_num1
= new_num1 / 10; => new_num1 = 315 / 10 =
31
digit2of1 = new_num1 % 10; => digit2of1 = 31 % 10 =
1
digit1of1 = new_num1 / 10; => digit1of1 = 31 /
10 = 3
/* Do the same for the second
number2 */
new_num2 = number2;
=> new_num2 = 4998
digit4of2 = new_num2 % 10; => 4998 % 10 = 8
new_num2 = new_num2 / 10; => 4998 / 10 = 499
digit3of2 = new_num2 % 10; => digit3of2 = 499 % 10 =
9
new_num2
= new_num2 / 10; => new_num2 = 49
digit2of2 = new_num2 % 10; => digit2of2 = 49 % 10 = 9
digit1of2 = new_num2 / 10; => 49 / 10 = 4
/* Now, get the digits of the number3,
which is the result and put them together as
one integer.*/
digit1of3 = (digit1of1 +
digit1of2)/2; => (3 + 4)/2 = 3
digit2of3 = (digit2of1 + digit2of2)/2;
=> (1 + 9)/2 = 5
digit3of3 = (digit3of1 +
digit3of2)/2; => (5 + 9)/2 = 7
digit4of3 = (digit4of1 +
digit4of2)/2; => (5 + 8)/2 = 6
number3 = (digit1of3 * 1000) +
(digit2of3 * 100) + (digit3of3 * 10) + digit4of3;
= (3
* 1000) + (5 * 100) + (7 * 10) + 6 = 3000 + 500 + 70 + 6= 3576
printf ("The resulting number is
%d \n", number3);
The correct number3 value of 3576 is
printed.
End of tracing.
Que. 2. Solve
the version of problem of Exercise 2.4, question 3 of course book which computes
and prints the temperature in degrees Fahrenheit (oF)
given the temperature in degrees Celsius, by going through the problem solving
steps (hint: ºF = (9.0/5.0 *
ºC) +32.0).
Solution to Que 2:
Step 1: Problem is clear enough
Step 2: Input: degreeC
(real)
Output:
degreeF (real)
Relationships: degreeF = (9/5 * degreeC) + 32
Step 3: Since this problem is simple enough, we solve using only one module (one
solution part).
Step 4: We now write the algorithm:
Main () {
Input: degreeC
(real)
Output: degreeF (real)
Read (degreeC);
degreeF = (9.0/5.0 * degreeC)
+ 32;
Print (degreeF);
}
Step 5: Implementation and Coding in C:
/*Given temperature in degrees celsius
*Output temperature in degrees fahrenheit
*/
#include
<stdio.h>
void
main() {
float degreeC, degreeF;
scanf
("%f", °reeC);
degreeF
= degreeC*9.0/5.0 + 32; /*compute the temperature in
degrees fahrenheit*/
printf
("%f\n", degreeF); /*output*/
}
Step 6: Testing with test data 20C, -40C, 0C
From the algorithm degreeC = 20, then degreeF is computed as (9/5*20)+32 =
68F (printed). With -40C, algorithm prints -40F and with input 0C, algorithm prints 32F. These results correspond to the results we get if we did it with a calculator and when we execute the C program in step 5.
Que.
3. Do questions 3, 5, 6, and 7 from Section
3.4 of course book.
Exercise 3.4, Q. 3: Evaluate the following expressions:
B/A, A/B, B%A, A%B
given the following values of A and B respectively:
a) 6, 21 b) 3, 21
c) 8, 18 d) –3, -16
Solution to Q. 3:
a) 21/6 = 3, 6 /21 = 0, 21%6 = 3, 6 %21 = 6
b) 21/3 = 7, 3 /21 = 0, 21%3 = 0, 3 %21 = 3
c) 18/8 = 2, 8/18 = 0, 18%8 = 2, 8 %18 = 8
d) –16/-3 = 5, -3/-16 = 0, -16 %–3 = -1, -3 %– 16 = -3
Exercise 3.4, Q. 5. Evaluate
the following expressions:
a) true && false
b) true || true && false
c) !
(true) || true
d) 40
% 5
e) 5
% 40 / 8
f) !
false
g) 15
< 1
h)
100 >
15
Solution:
a) false
b) true
c) true
d) 0
e) 0
f) true
g) false
h) true
Exercise 3.4, Q. 6.
a) What
is the difference between an expression and an assignment instruction?
b) With
A = 15, B = 3, C = 6 and D = 3; evaluate the following equations:
i)
Q =
A+B/C-D*D
ii)
Q =
(A+B)/C-D*D
iii)
Q =
A+B/(C-D*D)
iv)
Q =
(A+B) % C
v)
Q =
(A+B) / D*D
vi)
Q =
5*(A+B)-4*B(D+6)
vii)
Q =
A-2>B
c) For each equation
in (b) above, state the data type of Q.