Functions - itzjac/cpplearning GitHub Wiki

Useful compiler flags for this chapter

-Wall

-Wextra

-Wconversion (warns of any implicit conversion)

-pedantic

-Wdiv-by-zero

-std=c++0x

Functional programming

The general form when declaring and defining a function (also known as implementing)

return_type function_name(parameters)
{
    statement(s)
}

In functional programming is also very convenient to divide a set of functionally in modules, typically in .h (stands for headers) and .cpp files. For such purposes is necessary to explicitly declare and later define a function, as two separated steps.

Function declaration are located in the header files, files that serve as the interface for the users that will use our module or library.

Declaring a function only contains the necessary information for its later definition, only its signature is needed and is written as:

return_type function_name(parameters);

Function definition are typically located in the cpp files, here we fully implement the function.

In order to bind the previously declared function of header files and our implementation, it is necessary to include the header

#include "MyHeader.h"

return_type function_name(paramters)
{
    statement(s)
}

Note that is also possible to declare and define the function in the header file, but we generally want to hide the implementation details to the user, limiting the access to only the declaration or signature of the function.

Compiling this set of functions won't produce an executable, instead an obj file will be used to link to the program being used. As for the main program, it will use our set of functions (a super tiny library), again the header inclusion will be needed to actually expose the functions to the user and make calls to the functions.

Suppose our set of functions stored in a pair of .cpp and .h files names series.

To avoid multiple inclusion, header files should always use a guard of statements (preprocessor instructions) that handles the problem.

series.h #ifndef SERIES_H #define SERIES_H

int sum_numbers(int n); // the declaration of the function, no body is specified and ends with semicolon

#endif // _SERIES_H_

series.cpp #include "series.h"

// arithmetic series
// implementing of declaring the sum_number function, should exactly match as defined in the header
// function contains a return type integer, a name sum_number, and only one parameter n
// given an integer number n, 10 it will return the value of sum of 10+9+8+7...+1
int sum_number(int n) 
{
    return n*(n+1)/2;
}

ere it comes the main program, where we call the functions declared in series header.

The function here is called using a n= 898;

functiontest.cpp

#include "series.h"
int main()
{
    std::cout<<"Adding numbers "<< sum_number(898)<< std::endl;"
}

To properly compile this two modules, we need two consider the two modules and later link them producing the final executable:

Compile the series module

$g++ -c series.cpp

An object file series.o will be produced

Compile the main module

$g++ -c functiontest.cpp

Another object file functiontest.o will be produced.

With the two modules now we can produce the final executable

$g++ functiontest.o series.o -o functiontest

EXERCISES

1. Create another function called factorial, mathematically the factorial of a number is expressed as n!, finding the factorial on 10 is expressed as

1098765432*1 = 3, 628, 800

• Implement the function in the appropriate module
• Call this function from main and identify the greatest factorial number your PC can compute
• Declare and implement another series number known as an harmonic series. Given the number n > 0, for the case n = 6 the result of this series is computed as:
  • 1/6+1/5+1/4+1/3+1/2+ 1
  • The function should receive the n input, and return the computer value of the harmonic series of the input n

2. Create another module charsmanip (character manipulation), this should be in other set of header and a cpp files. Declare and implement a function:

• return true if a character is Capital or not
• returns true if a character is a vowel or not
• return true if a character is a number

Recursive functions

Consider the function to compute the factorial of non-negative integer number n: expressed as n!.

long factorial(unsigned n)
{
    long result = 1;
    for(int i = n; i >0; i--)
    {
        result *= n;
    }        
    return n;
}

Computing a factorial using this method is known as the iterative. The name stands to the fact that the result of the expression will be obtained through an iterative or looping instruction, in this case the for.

Alternatively to the iterative method it comes the recursive, in this case the result won't be obtained through an iterative instruction but to sequence of calls of the same function until it find the basic answer to the problem.

For the factorial function we can verify that the basic solution is when n=1, where factorial will return 1. We use this basic solution to stop the recursion.

long recursive_factorial(unsigned n)
{
    if(n ==1 || n == 0) // our basic solution notice 0 is included due to 0! = 1
    {
        return 1;
    }
    return n*recursive_factorial(n-1);
}

To visualize the function calls, when the recursive function is called from main or other function, it is recommended to elaborate the function calls until it reaches the base case. Consider an arbitrary n= 4 to compute the recursive_factorial.

factorial(4) --------> 4 * factorial ( 4 -1 ) ----------> 3 * factorial(3-1) --------> 2 * factorial(2-1)-------> 1
          24 <-------- 4 * 6                  <---------- 3 * 2              <-------- 2 * 1             <------- 1

Notice we reach our base case in the call factorial(2-1), this will pass a n = 1, therefore return 1. A rolling back process will be produced from the base case (1) to the n value (n).

Choosing the iterative over the recursive method depends on the complexity of the algorithm, the desire performance and memory space. Every problem must be carefully analyzed to make a decision. For the purpose of this example, there is no real performance advantage from one method to another.

What it is more important is to consider that an algorithm will usually contain some recursive notations, it will be the work of the programmer to adapt it to an iterative method.

HOMEWORK

1. In the series module create the following functions using recursion

2. Fibonnaci numbers sequence http://en.wikipedia.org/wiki/Fibonacci_number

3. Tower of Hanoi: investigate what it is and analyze why is so computationally heavy

4. Extend the series module implementing the following functions using a max number as the parameter and print to screen:

5. All even numbers bellow the max number

6. All odd numbers bellow the max number

7. All prime numbers bellow the max number

string

String variables are part of the C++ standard library and they contain several "ready to use" methods which allows programmer to avoid knowing the details of the function implementation:

• size (length)
• empty
• clear
• find_first_of
• c_str

Math library

cmath header

• sinf
• cosf
• tanf
• asinf
• acosf
• atanf
• sqrtf
• logf
• expf
• powf
• fabsf
• floorf
• ceilf

Random (pseudo-random)

cstdlib

rand

int r = rand() % n; // return random number in [0, n-1]

ctime

• time

• srand

  srand( time(0) );

EXERCISES

1. Using the string standard library and the following string

   std::string myString = "People have the right to be stupid. Some people abuse that privilege";

• Create a function that return the number of certain letter: if called number_of_letter('u'), this would return 2.
• Create a function that prints the string in Capitals
• Create a function that prints the string in reverse order

Arrays

Using std:strings is a very convenient way to save programming time and promote code reusability. Operations like copy string, find a character on a string, identify the kind of characters, transform characters among several other operations are all ready to use functions that hide the details of string manipulation in the computers.

To further understand how strings are stored we will introduce character arrays, also known as C-Strings.

The importance of the character arrays goes beyond strings, because any other kind of data type can use the concept of arrays.

C-String

The name comes from the C language, in which the type of variable string wasn't part of a standard. To manipulate strings or collection of characters in C, contiguous memory addresses were used to store characters, a type of variable that guarantees this specification is the array. C++ preserves C-arrays mainly for compatibility and performance reasons.

Notice that by moving away from the string type, all capabilities provided by the string standard library, are lost: any manipulation or functionality to the what we called strings, now arrays of characters is delegated to the programmer.

Declare an array of characters

int main()
{
    char myArray[25];
    return 0;
}

The declaration of the array has the following syntax

type_of_variable name_of_array[size_of_array];

As any other local variable the contents in memory of this array are unknown, we only have allocated 25 characters of contiguous elements.

The size_of_array expression must always be a constant value.

Initialize an array of characters

Now we will show how to initialize this array with a collection of characters "Betrayers are casted out"

int main()
{
    char myArray[25]; = "Betrayers are casted out";
    return 0;
}

Each element in the memory is now defined and contains each of the characters inside the double quotes.

The actual information of characters is up to the 24th character, an extra character NULL or '\0' is needed to indicate the end of the collection. This yields the 25 total of characters needed.

It is possible to declare the above array using more than 25 elements to store the characters, in that situation we will be wasting memory, the position of the NULL character is what will determine what is to be interpreted as the end the characters collection. For this reason the C-Strings are also known as NULL-terminated strings.

Indexing an array of characters

char array[100] = "Betrayers are casted out"; // allowed but wasted 75 elements of memory
char array[24] =  "Betrayers are casted out"; // ERROR! not enough space to allocate this string

We can also use the [ ] square brackets operator to index one element of the array at a time and manipulate each character if needed.

Invalid index values like array[-1], array[9000] will be accepted by the compiler but will be run time errors. It will be the responsability of the programmer to avoid using invalid index values, a problem known as out of bounds/out of range indexing.

#include 

main()
{
    char myArray[25] = "Betrayers are casted out";
    std::cout<<"Print the entire array content to screen" << myArray< < std::endl;
}

An alternate way, sometime more convenient way to declare and initialize a char array is using empty square brackets [ ], for this scenario the compiler computes the right amount of characters needed to for the array.

#include 

main()
{
    char myArray[] = "Betrayers are casted out";
    std::cout<<"Print the entire array content to screen" << myArray<< std::endl;
}

Functions parameters using arrays

Using the [ ] operator, we are going to create a function that prints the contents of an array. For this purpose we will need to pass the entire array to the function.

void printArray(char s[])
{
    int i = 0;
    while(s[i] != '\0') 
    { 
        std::cout<< // TODO(isaveg): missing
    }
}

Notice the notation of the parameter in the function printArray(..), we use the [ ] appended next to the parameter name, to specify an array of chars will be passed to this function. The are better ways to specify this, using pointers or references, a topic we will cover later. But now we are going to stick to the [ ] notation.

Copying an array of characters

Copying from one array or characters to another is possible. To do this, use the strcpy function from the standard library, the assigning operation we used for strings, doesn't work for arrays of characters.

#include 

int main()
{
   	char myArray[25] = "Betrayers are casted out";
    char myCopiedArray[25];
std::strcpy(myArray, myCopiedArray);
std::cout<< // TODO(isaveg): missing
}

The array to which we are copying the contents, myCopiedArray, should be enough large to contain the source array otherwise we will produce an undefined behavior. As a good practice, consult the official documentation strcpy.

String to C-String

A string can be converted to a C-String calling a member function c_str(), this returns an array of characters.

Again, the copy operation using the assign operator (=), from the string to myArray is not possible for obvious reason, they are different type of variables.

We will use another library, cstring, that will help use copying from a string to an array of chars.

#include 

int main()
{
   	std::string s1 = "Betrayers are casted out";
	char myArray[25];
	std::strncpy(myArray, s1.c_str(), 25);
	std::cout< // TODO(isaveg): missing code from old space
}

Creating own version strcpy

Let's take a step further and remove the cstring header to reduce dependencies.

For this situation we will need to provide our own version of strncpy.

Our version is not going to be as robust as the version we used from the standard library, but will give us a grasp on how we can manipulate the elements of an array.

Let's try first copying from one array of chars to another array of chars, the function will need two parameters: one character array as the source and another character array as the destiny which will contain a copy of the source contents.

#include void mystrcpy(char source[], char dest[]) { int i =0; while(source[i] != '\0') { dest[i] = source[i]; i++; } dest[i] = '\0'; } int main() { char mySource[25] = "Betrayers are casted out"; char myDestiny[25]; mystrcpy(mySource, myDestiny); std::cout<<"Source was copied to destiny "<< myDestiny<

Const function parameters

Let's return to our original problem, copy a string into an array. Can our mystrcpy version handle this situation?

Passing a string in the first parameter of our function, won't be accepted: their types are no correct ... std::string s = "Betrayers are casted out"; char myDestiny[25]; mystrcpy(s, myDestiny); ...

But that doesn't work either!!!

The reason for this error is the value that c_str() member returns, a const char [ ], the type of this variable is enough different, due to its constness, to be considered of a different type than the one accepted by our function.

We need to change our function to accept const arrays

#include void mystrcpy(const char source[], char dest[]) { int i =0; while(source[i] != '\0') { dest[i] = source[i]; i++; } dest[i] = '\0'; } int main() { std::string s = "Betrayers are casted out"; char myDestiny[25]; mystrcpy(s.c_str(), myDestiny); std::cout<<"Source was copied to destiny "<< myDestiny<

Function overloading

TODO

Default parameters

TODO

QUIZ

• two function foo and bar both declare a local variable of the same name and type called x. The xin foo and the x in bar are different?
• which statement is true, a function definitionhas a return type, a name, a parameter list, and a body
• evaluate a math function, floor(3.95)
• scope, value of a variable across function calls
• parts of the signature of a function
• what is a function and what is not, true or false
• how to use rand range
• correct default parameter usage
• how to properly use the random number generator
• another math evaluation

EXERCISES

1. Given a initialized array of chars like this

   char myCharArr[] = "I stepped on a Corn Flake, now I'm a Cereal Killer";

2. Create a function that returns the number of characters in the array

3. Create a function that returns the number of vowels in the array

4. Factorial, using functions

5. ToUpper, ToLower, character/string

6. arctangent2, implement base

7. Interactive Calculator program, enter values and operation

8. Slot machine, random number generator get win/loose money

9. Binary Search,

10. Bubble Sort

Final exercises

To solve the following problems, use whatever of the techniques we have learned so far.

1. Create a half pyramid shape
2. User inputs the height of a half pyramid, the range of the height can be from 0-100.
3. Out of range height should ask the user until a valid height valid is input

A half pyramid of

size 0 (empty pyramid)

size 1

**

size 2

 **
***

size 3

  **
 ***
****

size 4

   **
  ***
 ****
*****

etc.

2. Where is it taken the name 'bool'?

3. What is the table of truth of the XOR operation? What is the C++ operand that represents this operation?

4. Write a program that converts Fahrenheit to Celsius degrees, prompt the user to provide the value to be converted

5. Write a function to compute the exponential of a number (base) . Program should prompt for the base and exponential

   $Base: 10 Exp= 2 Result = 100

6. Create a program that prints the smallest and largest number that built-in types can hold (int, long long, float, double, char, unsigned char)

7. Encapsulate this in a function called mylimits()

8. Investigate if the std library provides a mechanism to compute the smallest and largest number of the built-in variables. Use library facilities and encapsulate the results in a function called stdlimits()

9. Implement the greedy algorithm using quarters(25¢), dimes(10¢), nickels(5¢) and pennies (1¢)

According to the National Institute of Standards and Technology (NIST), a greedy algorithm is one "that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems."

What’s all that mean? Well, suppose that a cashier owes a customer some change and on that cashier’s belt are levers that dispense quarters, dimes, nickels, and pennies. Think of a "greedy" cashier as one who wants to take, with each press, the biggest bite out of this problem as possible.

For instance, if some customer is owed 41¢, the biggest first (i.e., best immediate, or local) bite that can be taken is 25¢. (That bite is "best" inasmuch as it gets us closer to 0¢ faster than any other coin would.) Note that a bite of this size would whittle what was a 41¢ problem down to a 16¢ problem, since 41 - 25 = 16. That is, the remainder is a similar but smaller problem. Needless to say, another 25¢ bite would be too big (assuming the cashier prefers not to lose money), and so our greedy cashier would move on to a bite of size 10¢, leaving him or her with a 6¢ problem. At that point, greed calls for one 5¢ bite followed by one 1¢ bite, at which point the problem is solved. The customer receives one quarter, one dime, one nickel, and one penny: four coins in total.

It turns out that this greedy approach (i.e., algorithm) is not only locally optimal but also globally so for America’s currency (and also the European Union’s). That is, so long as a cashier has enough of each coin, this largest-to-smallest approach will yield the fewest coins possible.

Write, in a file called greedy.c, a program that first asks the user how much change is owed and then spits out the minimum number of coins with which said change can be made. Assume that the only coins available are quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢).

Examples:

*Customer is owed $9.75, assume that your program’s input will be 9.75 and not $9.75 or 975. However, if some customer is owed $9 exactly, assume that your program’s input will be 9.00 or just 9 but, again, not $9 or 900. Of course, by nature of floating-point values, your program will likely work with inputs like 9.0 and 9.000 as well; you need not worry about checking whether the user’s input is "formatted" like money should be. And you need not try to check whether a user’s input is too large to fit in a float. But you should check that the user’s input makes sense.

Incidentally, do beware the inherent imprecision of floating-point values. For instance, 0.01 cannot be represented exactly as a float. Try printing its value to, say, 50 decimal places, with code like the below:

float f = 0.01f;
std::cout< // TODO(isaveg): missing code from old platform

Before doing any math, then, you’ll probably want to convert the user’s input entirely to cents (i.e., from a float to an int) to avoid tiny errors that might otherwise add up! And be careful to round and not truncate your pennies!

• The program should only print the minimum number of coins needed

If owed 0.41, it results in 4 coins:case 1 quarter, 1 dime, 1 nickel and 1 pennie.

How much change is owed?
0.41
4

• If an invalid input is entered (negative values, characters, etc.), the program should again prompt for the input until a valid one is found
• The program most be tested and yield correct result for the following input/output values
• 0.41 ----> 4 coins
• 0.15 ----> 2 coins
• 0.01 ----> 1 coins
• 1.6 ----> 7 coins
• 23 ----> 92 coins
• 4.2 ----> 18 coins
• -1 ----> will again prompt for another input
• "abcd" ----> will again prompt for another input
• "" ----> will again prompt for another input

7. Write Caesar encryption algorigthm

8. Write vigenere encryption algorithm (uses strings instead of numbers as in Caesar)

PROJECTS

For the following projects please consider:

• Write clean, well indented and organized code
• Use names for variables and functions that makes the code easy to read and understand
• Design the program taking into consideration modularity (by using functions) and headers
• Try to use as many of the language features we have covered so far

1. Hangman ( 5 days week aprox 3 hours at day)

Description:

• The computer picks a secret word and the player tries to guess it one letter at a time.

• The player is allowed eight incorrect answers at a time

• If the player fails to guess the word in time, the player is hanged and the game is over displayed the message 'You were hanged! Game over'

• If the player guesses all letters the game is over displaying the message 'You were saved!'

• The game overs displaying the message Thanks you for playing 'Hangman'!

-The following image demonstrate the functionality of the program when guessing the 4 letter word 'EASY'

Guidelines:

• Use an array of strings use the following words (all in Capitals): GUESS, HANGMAN, DIFFICULT
• Use the character '-' to display unknown characters
• The application will get one a letter at a time, which will be translated to the Capital version if necessary
• For the simplest version of the program, the application can run once
• Optional: validate input so that application doesn't crash on wrong values
• Optional: provide a menu option so that we can run application indefinitely

2. Guess my number (computer and player can switch roles)

Description:

Select between two different game modes: Player vs Computer, Computer vs Player

• Player vs Computer: The computer chooses a random number between 1 and 100, the player tries to guess the number in as few attempts as possible.

• Computer vs Player: The player chooses a random number between 1 and 100, the computer tries to guess the number in as few attempts a possible.

• Each time the player(computer) enters a guess, the computer(player) tells her whether this guess is too high, too low, or correct. Once the player(computer) guesses, the number of attempts is displayed. The round is over and the player is prompted to the game mode selection (the application never stops until player types the 'q' character on this prompt)

• The player can enter the option 'q' during game mode selection to end the game and display the message Thank you for playing 'guess my number'!

The image illustrate the execution of the two game modes.

Guidelines:

• Create random numbers using the function srand() and rand(): investigate which library they belong to and how to use it
• Only generate pseudo-random numbers between 1 and 100
• Optional: you can validate input so that application doesn't crash on wrong values