Transcript Final Review

1
3.3
Math Library Functions
• Perform common mathematical calculations
– Include the header file <cmath>
• Functions called by writing
– functionName (argument);
or
– functionName(argument1, argument2, …);
• Example
cout << sqrt( 900.0 );
– sqrt (square root) function The preceding statement would
print 30
– All functions in math library return a double
 2003 Prentice Hall, Inc. All rights reserved.
2
3.3
Math Library Functions
• Function arguments can be
– Constants
• sqrt( 4 );
– Variables
• sqrt( x );
– Expressions
• sqrt( sqrt( x ) ) ;
• sqrt( 3 - 6x );
 2003 Prentice Hall, Inc. All rights reserved.
3
M e tho d
ceil( x )
De sc rip tio n
Exa m p le
rounds x to the smallest integer ceil( 9.2 ) is 10.0
not less than x
ceil( -9.8 ) is -9.0
cos( x )
trigonometric cosine of x
cos( 0.0 ) is 1.0
(x in radians)
exp( x )
exponential function ex
exp( 1.0 ) is 2.71828
exp( 2.0 ) is 7.38906
fabs( x )
absolute value of x
fabs( 5.1 ) is 5.1
fabs( 0.0 ) is 0.0
fabs( -8.76 ) is 8.76
floor( x )
rounds x to the largest integer
floor( 9.2 ) is 9.0
not greater than x
floor( -9.8 ) is -10.0
fmod( x, y )
remainder of x/y as a floating- fmod( 13.657, 2.333 ) is 1.992
point number
log( x )
natural logarithm of x (base e) log( 2.718282 ) is 1.0
log( 7.389056 ) is 2.0
log10( x )
logarithm of x (base 10)
log10( 10.0 ) is 1.0
log10( 100.0 ) is 2.0
pow( x, y )
x raised to power y (xy)
pow( 2, 7 ) is 128
pow( 9, .5 ) is 3
sin( x )
trigonometric sine of x
sin( 0.0 ) is 0
(x in radians)
sqrt( x )
square root of x
sqrt( 900.0 ) is 30.0
sqrt( 9.0 ) is 3.0
tan( x )
trigonometric tangent of x
tan( 0.0 ) is 0
(x in radians)
Fig . 3.2 M a th lib ra ry func tio ns.
 2003 Prentice Hall, Inc. All rights reserved.
4
3.4
Functions
• Functions
– Modularize a program
• Divide and conquer facilitates program construction
– Software reusability
• Call function multiple times, thus avoiding code repetition
• Pre-existing functions can be used to create new programs
• Local variables
– Known only in the function in which they are defined
– All variables declared in function definitions are local
variables
• Parameters
– Local variables passed to function when called
– Provide outside information
 2003 Prentice Hall, Inc. All rights reserved.
5
3.5
Function Definitions
• Function prototype
– Tells compiler argument type and return type of function
– int square( int );
• Function takes an int and returns an int
• Calling/invoking a function
– square(x);
– Parentheses an operator used to call function
• Pass argument x
• Function gets its own copy of arguments
– After finished, passes back result
 2003 Prentice Hall, Inc. All rights reserved.
6
3.5
Function Definitions
• Format for function definition
return-value-type function-name( parameter-list )
{
declarations, statements and return value
}
– Parameter list
• Comma separated list of arguments
– Data type needed for each argument
• If no arguments, use void or leave blank
– Return-value-type
• Data type of result returned (use void if nothing returned)
 2003 Prentice Hall, Inc. All rights reserved.
7
3.5
Function Definitions
• Example function
int square( int y )
{
return y * y;
}
• return keyword
– Returns data, and control goes to function’s caller
• If no data to return, use return;
– Function ends when reaches right brace
• Control goes to caller
• Functions cannot be defined inside other functions
 2003 Prentice Hall, Inc. All rights reserved.
8
3.6
Function Prototypes
• Function prototype contains
–
–
–
–
Function name
Parameters (number and data type)
Return type (void if returns nothing)
Only needed if function definition after function call
• Prototype must match function definition
– Function prototype
• Does not include parameter names, ie. x, y, z)
double maximum( double, double, double );
– Definition
double maximum( double x, double y, double z )
{
…
}
 2003 Prentice Hall, Inc. All rights reserved.
9
3.6
Function Prototypes
• Function signature
– Part of prototype with name and parameters
• double maximum( double, double, double );
• Argument Coercion
Function signature
– Force arguments to be of proper type
• Converting int (4) to double (4.0)
cout << sqrt(4)
– Conversion rules
• Arguments usually converted automatically
• Changing from double to int can truncate data
– 3.4 to 3
– Mixed type goes to highest type (promotion)
• Int * double
 2003 Prentice Hall, Inc. All rights reserved.
10
3.6
Function Prototypes
Da ta typ es
long double
double
float
unsigned long int
(synonymous with unsigned long)
long int
(synonymous with long)
unsigned int
(synonymous with unsigned)
int
unsigned short int
(synonymous with unsigned short)
short int
(synonymous with short)
unsigned char
char
bool
(false becomes 0, true becomes 1)
Fig . 3.5 Pro m o tio n hiera rc hy fo r b uilt-in d a ta typ es.
 2003 Prentice Hall, Inc. All rights reserved.
11
3.7
Header Files
• Header files contain
– Function prototypes
– Definitions of data types and constants
• Header files ending with .h
– Programmer-defined header files
#include “myheader.h”
• Library header files
– Each standard library has a corresponding header file
#include <cmath>
 2003 Prentice Hall, Inc. All rights reserved.
12
3.8
Random Number Generation
• rand function (<cstdlib>)
– i = rand();
– Generates unsigned integer between 0 and RAND_MAX
(usually 32767)
• Scaling and shifting
– Modulus (remainder) operator: %
• 10 % 3 is 1
• x % y is between 0 and y – 1
– Example
i = rand() % 6 + 1;
• “Rand() % 6” generates a number between 0 and 5 (scaling)
• “+ 1” makes the range 1 to 6 (shift)
– Next: program to roll dice
 2003 Prentice Hall, Inc. All rights reserved.
13
3.8
Random Number Generation
• Calling rand() repeatedly
– Gives the same sequence of numbers
• Pseudorandom numbers
– Preset sequence of "random" numbers
– Same sequence generated whenever program run
• To get different random sequences
– Provide a seed value
• Like a random starting point in the sequence
• The same seed will give the same sequence
– srand(seed);
• <cstdlib>
• Used before rand() to set the seed
 2003 Prentice Hall, Inc. All rights reserved.
14
3.8
Random Number Generation
• Can use the current time to set the seed
– No need to explicitly set seed every time
– srand( time( 0 ) );
– time( 0 );
• <ctime>
• Returns current time in seconds
• General shifting and scaling
– Number = shiftingValue + rand() % scalingFactor
– shiftingValue = first number in desired range
– scalingFactor = width of desired range
 2003 Prentice Hall, Inc. All rights reserved.
15
3.10 Storage Classes
• Variables have attributes
– Have seen name, type, size, value
– Storage class
• How long variable exists in memory
– Scope
• Where variable can be referenced in program
– Linkage
• For multiple-file program (see Ch. 6), which files can use it
 2003 Prentice Hall, Inc. All rights reserved.
16
3.10 Storage Classes
• Automatic storage class
– Variable created when program enters its block
– Variable destroyed when program leaves block
– Only local variables of functions can be automatic
• Automatic by default
• keyword auto explicitly declares automatic
– register keyword
•
•
•
•
Hint to place variable in high-speed register
Good for often-used items (loop counters)
Often unnecessary, compiler optimizes
Compiler may ignore even when specified
– Specify either register or auto, not both
• register int counter = 1;
 2003 Prentice Hall, Inc. All rights reserved.
17
3.10 Storage Classes
• Static storage class
– Variables exist for entire program
• For functions, name exists for entire program
– May not be accessible, scope rules still apply (more later)
• static keyword
– Local variables in function
– Keeps value between function calls
– Only known in own function
• extern keyword
– Default for global variables/functions
• Globals: defined outside of a function block
– Known in any function that comes after it
 2003 Prentice Hall, Inc. All rights reserved.
18
3.12 Recursion
• Recursive functions
– Functions that call themselves
– Can only solve a base case
• If not base case
– Break problem into smaller problem(s)
– Launch new copy of function to work on the smaller
problem (recursive call/recursive step)
• Slowly converges towards base case
• Function makes call to itself inside the return statement
– Eventually base case gets solved
• Answer works way back up, solves entire problem
 2003 Prentice Hall, Inc. All rights reserved.
19
3.12 Recursion
• Example: mystery number
int mystery ( int number)
{
if ( number <= 1 )
return 1;
else
return number * mystery( number – 1);
}
 2003 Prentice Hall, Inc. All rights reserved.
20
3.15 Functions with Empty Parameter Lists
• Empty parameter lists
– void or leave parameter list empty
– Indicates function takes no arguments
– Function print takes no arguments and returns no value
• void print();
• void print( void );
 2003 Prentice Hall, Inc. All rights reserved.
21
3.16 Inline Functions
• Inline functions
– Keyword inline before function
– Asks the compiler to copy code into program instead of
making function call
• Reduce function-call overhead
• Compiler can ignore inline
• Increases program size
– Good for small, not large, often-used functions
• Example
inline double cube( double s )
{ return s * s * s; }
 2003 Prentice Hall, Inc. All rights reserved.
22
3.17 References and Reference Parameters
• Call by value
– Copy of data passed to function
– Changes to copy do not change original
– Prevent unwanted side effects
• Call by reference
– Function can directly access data
– Changes affect original
– Referring to a const variable prohibits changes to original
 2003 Prentice Hall, Inc. All rights reserved.
23
3.19 Unitary Scope Resolution Operator
• Unary scope resolution operator (::)
– Access global variable if local variable has same name
– Not needed if names are different
– Use ::variable
• y = ::x + 3;
– Good to avoid using same names for locals and globals
 2003 Prentice Hall, Inc. All rights reserved.
24
4.2
Arrays
• Array
– Consecutive group of memory locations
– Same name and type (int, char, etc.)
• To refer to an element
–
–
–
–
Specify array name and position number (index)
Format: arrayname[ position number ]
Position number is referred to as subscript
First element at position 0
• N-element array c
c[ 0 ], c[ 1 ] … c[ n - 1 ]
– Nth element as position N-1
 2003 Prentice Hall, Inc. All rights reserved.
25
4.2
Arrays
• Array elements like other variables
– Assignment, printing for an integer array c
c[ 0 ] = 3;
cout << c[ 0 ];
• Can perform operations inside subscript
– The subscript can be an expression
c[ 5 – 2 ] same as c[3]
 2003 Prentice Hall, Inc. All rights reserved.
26
4.2
Name
that
this
same
Arrays
of array (Note
all elements of
array have the
name, c)
c[0]
-45
c[1]
6
c[2]
0
c[3]
72
c[4]
1543
c[5]
-89
c[6]
0
c[7]
62
c[8]
-3
c[9]
1
c[10]
6453
c[11]
78
Position number of the
element within array c
 2003 Prentice Hall, Inc. All rights reserved.
27
4.3
Declaring Arrays
• When declaring arrays, specify
– Name
– Type of array
• Any data type
– Number of elements
– type arrayName[ arraySize ];
int c[ 10 ]; // array of 10 integers
float d[ 3284 ]; // array of 3284 floats
• Declaring multiple arrays of same type
– Use comma separated list, like regular variables
int b[ 100 ], x[ 27 ];
 2003 Prentice Hall, Inc. All rights reserved.
28
4.4
Examples Using Arrays
• Initializing arrays
– For loop
• Set each element
– Initializer list
• Specify each element when array declared
int n[ 5 ] = { 1, 2, 3, 4, 5 };
• If not enough initializers, rightmost elements 0
• If too many syntax error
– To set every element to same value
int n[ 5 ] = { 0 };
– If array size omitted, initializers determine size
int n[] = { 1, 2, 3, 4, 5 };
• 5 initializers, therefore 5 element array
 2003 Prentice Hall, Inc. All rights reserved.
29
4.4
Examples Using Arrays
• Array size
– Can be specified with constant variable (const)
• const int size = 20;
– Constants cannot be changed, reduces scalability
– Constants must be initialized when declared
– Also called named constants or read-only variables
 2003 Prentice Hall, Inc. All rights reserved.
30
4.4
Examples Using Arrays
• Strings (more in ch. 5)
– Arrays of characters
– All strings end with null ('\0')
– Examples
• char string1[] = "hello";
– Null character implicitly added
– string1 has 6 elements
• char string1[] = { 'h', 'e', 'l', 'l',
'o', '\0’ };
– Subscripting is the same
String1[ 0 ] is 'h'
string1[ 2 ] is 'l'
 2003 Prentice Hall, Inc. All rights reserved.
31
4.5
Passing Arrays to Functions
• Specify name without brackets
– To pass array myArray to myFunction
int myArray[ 24 ];
myFunction( myArray, 24 );
– Array size usually passed, but not required
• Useful to iterate over all elements
• Unless passed the function cannot know array size
 2003 Prentice Hall, Inc. All rights reserved.
32
4.5
Passing Arrays to Functions
• Arrays passed-by-reference
– Functions can modify original array data
– Value of name of array is address of first element
• Function knows where the array is stored
• Can change original memory locations
• Individual array elements passed-by-value
– Like regular variables
– square( myArray[3] );
 2003 Prentice Hall, Inc. All rights reserved.
33
4.5
Passing Arrays to Functions
• Functions taking arrays
– Function prototype
• void modifyArray( int b[], int arraySize );
• void modifyArray( int [], int );
– Names optional in prototype
• Both take an integer array and a single integer
– No need for array size between brackets
• Ignored by compiler
– If declare array parameter as const
• Cannot be modified (compiler error)
• void doNotModify( const int [] );
 2003 Prentice Hall, Inc. All rights reserved.
34
4.7
Case Study: Computing Mean, Median
and Mode Using Arrays
• Mean
– Average (sum/number of elements)
• Median
– Number in middle of sorted list
– 1, 2, 3, 4, 5 (3 is median)
– If even number of elements, take average of middle two
• Mode
– Number that occurs most often
– 1, 1, 1, 2, 3, 3, 4, 5 (1 is mode)
 2003 Prentice Hall, Inc. All rights reserved.
35
4.8
Searching Arrays: Linear Search and
Binary Search
• Search array for a key value
• Linear search
– Compare each element of array with key value
• Start at one end, go to other
– Useful for small and unsorted arrays
• Inefficient
• If search key not present, examines every element
 2003 Prentice Hall, Inc. All rights reserved.
36
4.8
Searching Arrays: Linear Search and
Binary Search
• Binary search
– Only used with sorted arrays
– Compare middle element with key
• If equal, match found
• If key < middle
– Repeat search on first half of array
• If key > middle
– Repeat search on last half
– Very fast
• At most N steps, where 2N > # of elements
• 30 element array takes at most 5 steps
5
2 > 30
 2003 Prentice Hall, Inc. All rights reserved.
37
4.9
Multiple-Subscripted Arrays
• Multiple subscripts
– a[ i ][ j ]
– Tables with rows and columns
– Specify row, then column
– “Array of arrays”
• a[0] is an array of 4 elements
• a[0][0] is the first element of that array
Row 0
Column 0
a[ 0 ][ 0 ]
Column 1
a[ 0 ][ 1 ]
Column 2
a[ 0 ][ 2 ]
Column 3
a[ 0 ][ 3 ]
Row 1
a[ 1 ][ 0 ]
a[ 1 ][ 1 ]
a[ 1 ][ 2 ]
a[ 1 ][ 3 ]
Row 2
a[ 2 ][ 0 ]
a[ 2 ][ 1 ]
a[ 2 ][ 2 ]
a[ 2 ][ 3 ]
Column subscript
Array name
Row subscript
 2003 Prentice Hall, Inc. All rights reserved.
38
4.9
Multiple-Subscripted Arrays
• To initialize
– Default of 0
– Initializers grouped by row in braces
int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } };
Row 0
Row 1
int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } };
 2003 Prentice Hall, Inc. All rights reserved.
1
2
3
4
1
0
3
4
39
4.9
Multiple-Subscripted Arrays
• Referenced like normal
cout << b[ 0 ][ 1 ];
– Outputs 0
1
0
3
4
– Cannot reference using commas
cout << b[ 0, 1 ];
• Syntax error
• Function prototypes
– Must specify sizes of subscripts
• First subscript not necessary, as with single-scripted arrays
– void printArray( int [][ 3 ] );
 2003 Prentice Hall, Inc. All rights reserved.