Embedded Files
Algorithm Design (II)
First Term Exam (Up to P.67)
Practical 1
Prepare raptor flowcharts for the following
Example 2 (P.56)
Activity 1 (P.57)
Activity 2 (P.58)
Capture the image with Prt Scr and paste it in a word .
Submit the file s5XYY_Practical1.doc and submit in eclass
Try to complete Activity 1 & 2 with C++, you can reference http://codepad.org/TZmMKLSs
Practical 2
Prepare a raptor flowchart for
- Example 4 (P.60) http://codepad.org/kIG3qVIP
- Example 5 (P.61)
- Activity 3 (P.61)
Copy and paste it into a doc file and submit in eclass "S5XYY_Practical2.doc"
Practical 3 on Dec 15, 2014
Solve quadratic equation. Refer to the C++ code http://codepad.org/00e39Bsp
Instruction
1. Draw an IPO chart, flowchart and pseudo code in your exercise book.
2. Draw a flow chart with Raptor and submit in eclass.
Pseudo code
Input a,b,c
d = b* b - 4 * a * c
if d>0 then
s1 = (-b -sqrt(d)) /(2*a)
s2 = (-b -sqrt(d)) /(2*a)
output s1 and s2
else if d=0 then
s1 = (-b -sqrt(d)) /(2*a)
output s1
else output "No solution"
endif
endif
Notes
IPO chart
Input
Coefficient of Quadratic equation A, B, C
Process
Calculate the discriminant D
Find 2 solutions, 1 solution, no solution depends on D.
Output
Discriminant D
s1, s2
P.52 - 54
Case Expression in C++
switch(expression){
case constant-expression : statement(s); break; //optional case constant-expression : statement(s); break; //optional // you can have any number of case statements. default : //Optional statement(s);}
Example 6
C++ examples of Example 6 (P.66 of textbook) using CASE http://codepad.org/aNemm2VM
Common type of Looping
Common Application of Iteration statements
- validation (e.g. Enter a value until it is acceptable)
- summation (sum up N numbers, sum up until a negative number is inputted)
- multiplication of N numbers.
Exercise
1. Find the sum of an Arithmetic progression of N terms, the first term is A and the common difference is D.
- using FOR loop
- using While Do loop
2. Find the sum of geometric progression of N terms, the first term is A and the common ratio is M.
- using FOR loop
- using While Do loop
3. Find the sum of first N square number. (i.e. 1, 4, 9, 16 ...)
FOR LOOP
Pseudo code of example 9 using FOR..LOOP
For i = 1 to N do
begin
s = i * i
output S
endfor
Implementation of For loop using WHILE..LOOP
For I:= A to B
Loop Body
next I
I ¬ A – 1
While I < B do
I ¬ I + 1
Loop body
endwhile
Implementation in C++
I ¬ A
While I <= B do
Loop body
I ¬ I + 1
endwhile
i = i - 1
Manipulating Arrays:
Array is a collection of data items (objects, record) of the type. Usually, we manipulate numbers.
e.g. Read 10 data items into an array
For i:=1 to 10 do read(Mark[i])
Examples: Read Data until 999 is entered.
max = MaxSize
i:=0;
Repeat
i = i + 1
Input age[i]
until (age[i]=999) and i<max
N = i - 1
Disadvantage: e.g. Max size is N, we can only store N-1 value in it.
max = MaxSize
i:=0;
Repeat
Input Temp
If temp<>999 then
i = i + 1
age[i] = temp
endIF
until (temp=999) and i=max
N = i
Print an array using a for loop
Initialize an array:
M: max size of an array
A[1..M]: array of integer
N: number of elements in an array
Using a FOR loop to print an array
For i = 1 to N
begin
output A[i]
end
Search an array
Initialize an array:
M: max size of an array
A[1..M]: array of integer
N: number of elements in an array
Input a target_value and perform a sequential/linear search.
Input target_value
target_index = 0
For i = 1 to N do
begin
If A[i] = target_value then target_index = i
endfor
If target_index <> 0 then
Output "Found at position", target_index
else Output "Not found'
ENDIF
What happen when the target_value appears more than 1 times in the array?
answer: It found the last element.
What is the disadvantage of the above method?
After you found the target, it will continuous to search the rest of the array.
Alternative:
If we want to find all the elements contains the target_value
Input target_value
target_index = 0
For i = 1 to N do
begin
If A[i] = target_value then
begin
target_index = i
Output "Found at position", target_index
endIF
endfor
If target_index = 0 then
Output "Not found'
ENDIF
Example 16 (P.78) in textbook (using while..DO)
What happen when the taget_value appears more than 1 times in the array?
BRIEF explanation of Binary search.
Compare two search method
Deleting an item from an array. (Array are not sorted)
Search the element
Move the last element to take its place,
update N
Deleting an item from an array. (For an sorted array) P.79
Search the element
Move the elements below 1 position upwards.
Update N
P.79 Activity 8
(May 4, 2015)
Insert an item from an array (unsorted array)
Input element
Update N = N + 1;
Insert A[N]= element
Insert an item from an array (unsorted array)
Input element
Find the position T of the element
Move A[T]..A[N] one position downwards
A[T] = element
P.80 Activities 9
23.4 Advantages of using modular approach in programming
Modular approach: split up a program into a series of manageable, self-contained modules.
Self-contained:
using parameter passing in module.
reduce the use of global variable
Advantages
Standard procedures can be reused.
It is easier to read/understand and debug
Programmers can be work in team
module can be tested separately
Suitable for larger project
Page updated
Report abuse