Transcript Week 7 Class activities

Lecturer’s slides
http://www.comp.nus.edu.sg/~cs1010/
WEEK 7
Class Activities
© NUS
CS1010 (AY2014/5 Semester 1)
Week 7
 Revision (or materials that were earlier
skipped due to lack of time)
 Unit #7: Testing and Debugging
 Taking Stock
 Discussion of PE1
 Surveys
Week7 - 2
© NUS
CS1010 (AY2014/5 Semester 1)
Testing and Debugging
 We will go through Unit #7 Testing and
Debugging now
Week7 - 3
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 4
Taking Stock
 We are mid-way in the semester!
 Let’s take stock of what you have learned so
far
© NUS
CS1010 (AY2014/5 Semester 1)
Topics in C covered so far
 Control structures
 Basic C program
structure





main() function
Variable declarations
Data types (int, float,
Arithmetic operations

(+,-,*,/,%)

Input/output functions
(scanf(), printf())
 Preprocessor
directives


#include
#define
 Relational operators (<,




double, char)

Sequential statements
Selection statements
<=, >, >=, ==, !=)
Logical operators (&&, ||, !)
Conditional operator (? :)
Integer as boolean
if, if-else, switch
Repetition statements
 while, do-while, for
 Functions




Return type
Parameters
Function prototypes
Scope of
variables/parameters
 Pointers
 Arrays
Week7 - 5
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 6
Description and Objectives
Introduces the fundamental concepts of problem
solving by computing and programming using an
imperative programming language.
Outcomes
Solve simple
algorithmic
problems
Write good
small
programs
C as a tool
Not just
about C
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 7
Skills
Language
constructs
Problem
solving
Coding
© NUS
CS1010 (AY2014/5 Semester 1)
Topics in C covered so far
 Control structures
 Basic C program
structure





main() function
Variable declarations
Data types (int, float,
Arithmetic operations

(+,-,*,/,%)

Input/output functions
(scanf(), printf())
 Preprocessor
directives


#include
#define
 Relational operators (<,




double, char)

Sequential statements
Selection statements
<=, >, >=, ==, !=)
Logical operators (&&, ||, !)
Conditional operator (? :)
Integer as boolean
if, if-else, switch
Repetition statements
 while, do-while, for
 Functions




Return type
Parameters
Function prototypes
Scope of
variables/parameters
 Pointers
 Arrays
Week7 - 8
© NUS
CS1010 (AY2014/5 Semester 1)
Topics in C covered so far
 Control
Basic
Basic
Control
 C
Control
CControl
C
 Control
 Control
 Control
 Control
Basic
 Control
 Control
 structures
Control
structures
 structures
Control
structures
 structures
Control
structures
Basic
C
program
Basic
C
program
structure
structures
program
Basic
C
structures
structures
structures
program
Basic
CC
structures
structures
program
Basic
program
program
Basic
C
program
Sequential
Sequential statements
 Sequential
Sequential
Sequential

Basic
C
program
sstructure

Sequential


Basic
C
program
structure

Seque
program

Basic
C
program
structure
Sequent
structure
Basic
C program
structure
Sequenti
Sequential
Sequential
Sequential
structure
statements
statements
Selection statements
structure
statements
structure
main
statements
statements
structure
main()
Sequ
structure
ntial
ial
 structure
main()
structure
al statements
 Relational operators (<,
main()
main()
structure
statements
statements
main()
main()
()

main()
function
ential

Selection
functio
main()
<=, >, >=, ==, !=)
 Selection
statem
main()
main()
function
Selection
stateme
function


Selection
statemen

Selection

main()
function

main()
function
function
function
functi
 Logical operators (&&, ||, !)
 Selection
function
function
Selection
Selection
nVariabl
function
Variable
statements
ents
statements
nts
state

Variable
statements
function
ts

Variable
declarations
statements
 Conditional operator (? :)
statements
Variable
Variable
Variable
statements
Variable

Variable
statements
ment
 on
Variab
statements

Variable
declarations

Relational
 Integer as boolean
 Relational

Data
types (int, float,
Selecti
edeclarati
Variable

Relational
declarations

Selectio

Relational
 Varia
Selection

Relational
declarations
declarations
 char)
Relatio
declaratio
 if, if-else, switch
sledeclara
 Relation
declarations

Relational
double,
declaration
operators

Data
types
(int,
on
operators
(<, (<, (<, (<, <=,
declarations
operators
nData
Data
types
(int,
ons
ble
operators
statemen

types
operators
Data
types
(int,
nal
ns
declar

Repetition
statements
al

Arithmetic
operations

Data
types
operators
 Sele
sData
tions
(<,
<=,
>,
float,
double,
statem
<=,
>,
>=,

types
stateme
decla
Data
<=,
>,
>=,
==,
float,
double,
ts
>,>=,
while,
do-while,
<=,>,
>=,==,
==,!=) for
(int,
float,
(+,-,*,/,%)
operato
Data
ations
float,
double,
operator
(int,
float,
(<,
<=,
>,

Data
types
 ction
Data
ents
>=,
==,
!=)
char)
==,!=)
!=)
(int,
float,
types
 Relati
nts
Input/output
functions
char)
!=)
rs
(<,
double,
char)
 ratio
Data
types
(int,

Functions
 Logical
char)
s
(<,
<=,
state
double,
char)
>=,
==,
!=)
types
(int,
float,

Rel

Logical

Rela
ns

Arithmetic
(scanf(),
printf())
(int,
double,

Logical
onal
 Logical
Return
type (&&,
Arithmetic
Arithmetic
types
<=,>,>,>=,
float,
 Logical
operators
Arithmetic
(int,
Arithmetic
atio
Logical
double,
 ment
Data
operators
tiona
float,
operations
(+, Parameters
char)
operators
operat
(int,
operators
char)
Preprocessor
>=,
==,
operations
(+,double,
operations
stypes
operators
(&&,
==,
!=)
float,
nal
||, !)
operations
(+,operators
operations

Function
prototypes
l
(&&,
||,
!)
double,

Arithmetic
,*,/,%)
ors
(<,
(&&,
||,
!)
float,
!=)
(&&,
||,
!) of
char)
R
directives
,*,/,%)
(+,-,*,/,%)
 Logical
||,
!)
op

Scope
double,
Arithmetic
(&&,
||,
!)
(int,

Conditional
,*,/,%)
(+,-,*,/,%)
oper
char)
 Conditional
<=,
>,
operations
Input/output
doubl
 Conditional
 Logical
el
era
#include
float,
 Conditional
variables/parameters
Arithmetic
Input/output
Input/output
operator
char)

Conditional
operations

Condition
ators
Input/output
operator
(? :)

Input/output
 e,Arithmeti
operator
(?
>=,operato
tor
#define
functions
operator
(?
:)
at(+,-,*,/,%)
operation
operator
(?
:)
functions
 doub
Arithme
s
(&&,
||,
functions
 Pointers
operator
(?as
:)
(+,-,*,/,%)
(<, ==, !=) al :)
functions
cio

Integer
functions
char)
tic
Input/output
(scanf(),

Integer
as
rs
(&&,
sInput/outpu
(+,s(scanf(),
 Integer
as as
(scanf(),
!) operator
le,operatio
printf())
<=,
as
Integer

Arrays
(scanf(),
 Arithm

Logic
boolean
(scanf(),
printf())

Integer
n
functions
||, !)Conditio boolean
,*,/,%)
printf())
(<,
operati
char)
printf())
boolean
>,
t
functions
(?
:)
boolean
ns
(+,etic
al
printf())

Preprocessor
al
boolean
 if, if-else, switch
(scanf(),

Conditi
Input/outp
<=,

if,
if-else,

Preprocessor
ons
(+, Arith
nal

if,
if-else,
>=,

Preprocessor
,*,/,%)
 operat
Preprocessor
o(scanf(), operat  Integer as if, if-else,
Week7 - 9
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 10
So, what else did you learn besides C?
Topics in C
Program development
 Writing pseudocodes
 Edit – compile – execute” cycle
 Step-wise refinement
 Hand-tracing codes
 Incremental coding
 Testing
 Debugging
Programming environment/tools
 Operating system: UNIX
 Editor: vim
 Debugger: gdb
Problem solving
 Class exercises
 Practice exercises
 Lab assignments
© NUS
CS1010 (AY2014/5 Semester 1)
What Lies Ahead?
 Week 8: (1) More about pointers – using
address parameters in functions; (2) File
Processing
 Week 9: Characters and Strings
 Week 10: Recursion
 Week 11: Searching and Sorting
 Week 12: Structures
 (Note: the above order may be subject to
change)
Week7 - 11
© NUS
CS1010 (AY2014/5 Semester 1)
Discussion of PE1
 We will go through PE1 questions now
Week7 - 12
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 13
Q1. Parking Fee: Task Statement (1/12)

Based on the following parking rate table, calculate the
parking fee given day, time-in and time-out.


Day: an integer between 1 (Monday) and 7 (Sunday)
Time-in/time-out: an integer representing time in 24-hr format.
Weekday
Saturday
Sunday
4am ~ 7am
$2.00 / hr
$2.50 / hr
$5.00 / entry
7am ~ 6pm
$1.20 / 30 mins
$1.50 / 30 mins
6pm ~ midnight
$5.00 / entry
$7.00 / entry


Grace period: 10 minutes
Surcharge for parking for more than 10 hours


Weekdays: 10%, Saturday: 20%, Sunday: 0%
Additional fee for exiting after 10pm on any day: $3.00
 Surcharge is not applicable on this fee.
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 14
Q1. Parking Fee: Examples (2/12)

Example 1: Tuesday, 4:29am to 7:50am.

4:29am to 7am  3 * 1-hour slots: $2.00 * 3 = $6.00

7am to 7:50am  2 * 30-minute slots: $1.20 * 2 = $2.40

Total fee = $6.00 + $2.40 = $8.40
4am ~ 7am
7am ~ 6pm
6pm ~ midnight
Weekday
$2.00 / hr
$1.20 / 30 mins
$5.00 / entry
Saturday
Sunday
$2.50 / hr
$5.00 / entry
$1.50 / 30 mins
$7.00 / entry
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 15
Q1. Parking Fee: Examples (3/12)

Example 2: Saturday, 7:01am to 7:49pm.

7:01am to 6pm  22 * 30-minute slots: $1.50 * 22 = $33.00

6pm to 7:49pm  one entry: $7.00

Surcharge: ($33.00 + $7.00) * 20% = $8.00

Total fee = $33.00 + $7.00 + $8.00 = $48.00
4am ~ 7am
7am ~ 6pm
6pm ~ midnight

Weekday
$2.00 / hr
$1.20 / 30 mins
$5.00 / entry
Saturday
Sunday
$2.50 / hr
$5.00 / entry
$1.50 / 30 mins
$7.00 / entry
Surcharge for parking for more than 10 hours

Weekdays: 10%, Saturday: 20%, Sunday: 0%
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 16
Q1. Parking Fee: Examples (4/12)

Example 3: Sunday, 3pm to 10:01pm.

3pm to 10:01pm  one entry: $5.00

Additional fee: $3.00

Total fee = $5.00 + $3.00 = $8.00
4am ~ 7am
7am ~ 6pm
6pm ~ midnight

Weekday
$2.00 / hr
$1.20 / 30 mins
$5.00 / entry
Saturday
Sunday
$2.50 / hr
$5.00 / entry
$1.50 / 30 mins
$7.00 / entry
Additional fee for exiting after 10pm on any day: $3.00
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 17
Q1. Parking Fee: Examples (5/12)

Example 4: Thursday, 11:49pm to 11:59pm.

Grace period: no charge

Total fee = $0.00
4am ~ 7am
7am ~ 6pm
6pm ~ midnight

Weekday
$2.00 / hr
$1.20 / 30 mins
$5.00 / entry
Grace period: 10 minutes
Saturday
Sunday
$2.50 / hr
$5.00 / entry
$1.50 / 30 mins
$7.00 / entry
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 18
Q1. Parking Fee: Examples (6/12)

Example 5: Monday, 12pm to 10:01pm.





12pm to 6pm  12 * 30-minute slots: $1.20 * 12 = $14.40
6pm to 10:01pm  one entry: $5.00
Surcharge: ($14.40 + $5.00) * 10% = $1.94
Additional fee: $3.00
Total fee = $14.40 + $5.00 + $1.94 + $3.00 = $24.34
4am ~ 7am
7am ~ 6pm
6pm ~ midnight

Saturday
Sunday
$2.50 / hr
$5.00 / entry
$1.50 / 30 mins
$7.00 / entry
Surcharge for parking for more than 10 hours


Weekday
$2.00 / hr
$1.20 / 30 mins
$5.00 / entry
Weekdays: 10%, Saturday: 20%, Sunday: 0%
Additional fee for exiting after 10pm on any day: $3.00
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 19
Q1. Parking Fee: Grace Period (7/12)

This problem is similar to the Taxi Fare problem
(Practice Exercise #6)

As described in that exercise, time-in (timeIn) should be
converted to minutes since 0:00, using the formula:



timeIn = timeIn / 100 * 60 + timeIn % 100
We can do the same for time-out (timeOut)
After the conversion, it is straightforward to check for
the grace period

if (timeOut – timeIn <= 10) totalFee  0
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 20
Q1. Parking Fee: Base Fee (8/12)

Otherwise, totalFee = baseFee + surcharge (if any) +
additionalFee (if any)

baseFee
if (day == 7) baseFee  5.00 // Flat rate for Sunday
else baseFee  period1Fee + period2Fee + period3Fee

period 1: 4am to 7am

period 2: 7am to 6pm

period 3: 6pm to midnight
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 21
Q1. Parking Fee: 4 – 7am (9/12)

period1Fee (4am to 7am)
If timeOut is later than 7am,
we take 7am as the cut-off
for calculating period1Fee.
if (timeIn < 420)
if (day == 6) period1Fee  ceil ( (min(timeOut, 420) – timeIn) /
60) * 2.50 // Saturday
else period1Fee  ceil ( (min(timeOut, 420) – timeIn) / 60) * 2.00
// Weekdays
else period1Fee  0
ceil rounds up the calculated number
of 60-min slots to an integer.
 If timeIn is before 7am, period1Fee is charged based on day and
the number of 60-minute slots chargeable.
 Here 420 is converted from 7am (i.e., 700 in 24-hr format).
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 22
Q1. Parking Fee: 7am – 6pm (10/12)

period2Fee (7am to 6pm)
We take 6pm as the cut-off for
ending point and 7am as the cutoff for the starting point for
calculating period2Fee
if (timeIn <= 1440 && timeOut >= 420)
if (day == 6) period2Fee  ceil ( (min(TimeOut, 1440) - max(timeIn,
420) ) / 30) * 1.50 // Saturday
else period2Fee  ceil ( (min(TimeOut, 1440) - max(timeIn, 420) ) /
30) * 1.20 // Weekdays
else period2Fee  0
 If timeIn is before 6pm and timeOut is after 7am, period2Fee is
charged based on day and the number of 30-minute slots
chargeable.
 Here 420 is converted from 7am (i.e., 700 in 24-hr format), while
1440 is converted from 6pm (i.e., 1800 in 24-hr format).
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 23
Q1. Parking Fee: 6pm – midnight (11/12)

period3Fee (6pm to midnight)
if (timeOut > 1440)
if (day == 6) period3Fee  7.00 // Saturday
else period3Fee  5.00 // Weekdays
else period3Fee  0
 If timeOut is after 6pm,a per-entry fee is charged based on day.
 Here 1440 is converted from 6pm (i.e., 1800 in 24-hr format).
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 24
Q1. Parking Fee: Surchage/Additional Fee (12/12)

surcharge
if (day >= 1 && day <= 5) surcharge  baseFee * 0.1 // Weekday
else if (day == 6) surcharge  baseFee * 0.2 // Saturday
else surcharge  0 // Sunday

additionalFee
if (timeOut > 1320) additionalFee  3.00

Here 1320 is converted from 10pm (i.e., 2200 in 24-hr format).
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 25
Q2. Happy Numbers: Task Statement (1/5)

For a positive integer S, if we sum up the squares of all
digits in S, we get another (possibly different) integer S1.

We can always repeat this process to get more integers.
 Example: 3  3*3 = 9  9*9 = 81  8*8 + 1*1 = 65  …

The integers generated in this way always eventually
reach one of these 10 numbers:
 0, 1, 4, 16, 20, 37, 42, 58, 89, or 145.
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 26
Q2. Happy Numbers: Task Statement (2/5)

A positive integer S is said to be happy if one of the
integers generated this way is 1.


Examples:

7 is a happy number since 7  7*7 = 49  4*4 + 9*9 = 97
 9*9 + 7 *7 = 130  1*1 + 3*3 + 0*0 = 10  1*1 + 0*0  1 (which
is one of the 10 terminating numbers)

5 is not a happy number since 5  5*5 = 25  2*2 + 5*5 = 29
 2*2 + 9*9 = 85  8*8 + 5*5 = 89 (which is one of the 10
terminating numbers)
Given two ranges, compute and compare the number
of happy numbers in them.
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 27
Q2. Happy Numbers (3/5)

This problem is similar to the square-free numbers
exercise (Lab #2 Ex2)

The only difference is that now we are checking for
happy numbers instead of square-free integers.

Therefore, all you need is to replace is_square_free() in
your program for Lab #2 Ex2 with isHappyNumber()
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 28
Q2. Happy Numbers (4/5)

How to write isHappyNumber()?

Key observations:
If one of the numbers
generated is…
The numbers generated
afterwards are…
0
0
1
1
4, 16, 20, 37, 42, 58, 89, 145
4, 16, 20, 37, 42, 58, 89, 145

We can stop generating numbers once the generated number is
one of 0, 1, 4, 16, 20, 37, 42, 58, 89 or 145.

If the generated number is 1, the original number is happy,
otherwise it is not.
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 29
Q2. Happy Numbers (5/5)

Algorithm
isHappyNumber(num){
while (num is not 0, 1, 4, 16, 20, 37, 42, 58, 89 or 145)
num  sumOfDigitSquares(num)
return (num == 1)
sumOfDigitSquares(num) {
}
sum  0
while (num > 0) {
sum  sum + (num % 10)*(num % 10)
num  num / 10
}
return sum
}
© NUS
CS1010 (AY2014/5 Semester 1)
Week7 - 30
Surveys

Please do the IVLE surveys now


Very important for us to know your needs and how you are
doing
There are 3 surveys
1. For all CS1010 students – everybody must do
2. Only for those who have attended the “Introduction to
Programming” workshop in July
3. Only for those who have attended the “Refresher Workshop
for Polytechnic Graduates” workshop in July
© NUS
CS1010 (AY2014/5 Semester 1)
Things-To-Do

Deadline for Lab #3


Deadline: 4 October 2014, Saturday, 9am
Continue to do practice exercises on
CodeCrunch
Week7 - 31
© NUS
CS1010 (AY2014/5 Semester 1)
End of File
Week7 - 32