The Problem

You remember the Collatz sequence, don't ya? Here is a little reminder in case you didn't. http://en.wikipedia.org/wiki/Collatz_conjecture One of the problems is that, by doing the calculation over from the beginning for every number, you waste a lot of time redoing work that already has been done. Look at the first 6 sequences:

Subsequences, whose value we already know, are recalculated. For example, the entire sequence of 3 is already known, but we recalculate the entire sequence when starting from 6.

Memoization

Memoization (note the spelling, no "r") is a simple optimization technique used in algorithms where repeat calculations occur (http://en.wikipedia.org/wiki/Memoization ). The idea is simple. We remember a sequence when we first calculate it. Subsequently, for any value we calculate we check first to see if we already know the remaining sequence. If so, we stop the calculation and just copy the known sequence in.

For this lab, we will use a map to memorize Collatz sequences. Pay attention to this technique, it comes up in many guises and is very useful!

Programming Task

Make a new project directory. The project will have three files in it:

main.cpp functions.cpp

functions.h

Store all functions except main in functions.cpp. Create a header functions.h for the function declarations. Place a declaration of each function in the header.

Data structure, map of long to vector The data structure you will use for the lab is a map that has:

as a key, a long representing the first number in the Collatz sequence

as a value, a vector representing the Collatz sequence. The declaration of such a map would look like:

map> collatz_map; Maps store their elements as an STL pair. When you iterate through a map you iterate through a sequence of pair. The pair type for the map above would be:

pair> collatz_element; Remember that, given such a pair, collatz_element.first is the key (the long) and collatz_element.second is the value (the vector sequence).

Function collatz: long collatz(long n);

The function takes a long parameter, returns the next value in the Collatz Sequence.

Function pair_to_string: string pair_to_string(const pair> &p);

The function takes in a const pair and returns a string representing the pair. It is intended to be used as part of a transform algorithm to print the map to cout. No trailing comma at the end of the string!!

Function void fill_vector(map> &m, vector &v, long start);

Takes in a collatz_map (to check for memoization) and a vector to fill. The start is the first value in the Collatz sequence. The purpose is to fill the vector with the Collatz sequence starting from start. It has the following loop:

Loop until the vector is filled (the last value is 1)

check the collatz_map, using find, to see if the present number in the

sequence is in collatz_map o if yes, copy the sequence from collatz_map to the end of the vector we

are filling. Write a message saying you found the remaining sequence so

you can debug (see sample output below).

o if no, calculate the next value using collatz Main Main program goes in main.cpp.

main.cpp includes functions.h as described. This function:

prompts for a the low value in the Collatz range to calculate

prompts for the high value in the Collatz range to calculate

for each long in the range from low to high:

o call fill_vector on the Collatz starting value o set the collatz_map, key is the starting Collatz number, vector is what

is returned by fill_vector print your map using transform and pair_to_string to see how you did.

Example

Look at the table again

Calculate values from 2 to 6

collatz of 2 is 1, collatz_map[2] has sequence {2,1}

collatz of 3. Calls collatz on 3,10,5,16,8,4

o it finds 2 in the collatz_map, fills the rest of the sequence based on collatz_map[2]

collatz of 4: Calls collatz on 4

o finds 2 in the collatz_map and fills the rest of the sequence based on

collatz_map[2] collatz of 5: Calls collatz on 5,16,8

o finds 4 in the collatz map and fills the rest of the sequence based on collatz_map[4]

collatz of 6: Calls collatz on 6 o finds 3 in the collatz_map and fills the rest of the sequence based on

 collatz_map[3] 

Assignment Notes

Usefind or count, not[ ]to see if a key is in the map

remember that, by using the [ ] to search a map, you always find the key

because it will insert that key if it is not there. To see if something is in a map

you have to use find.

find returns either an iterator to the found element or

collatz_map.end() if it did not find it.

The iterator that find returns is a pointer to a pair. Remember the fun syntax

I showed you: (*itr).first is the same as itr->first

To append something to the end of a vector:

you could write a loop

you could use copy and a back_inserter

2 2, 1 3 3, 10, 5, 16, 8, 4, 2, 1 4 4, 2, 1 5 5, 16, 8, 4, 2, 1 6 6, 3, 10, 5, 16, 8, 4, 2, 1 2 2, 1 3 3, 10, 5, 16, 8, 4, 2, 1 4 4, 2, 1 5 5, 16, 8, 4, 2, 1 6 6, 3, 10, 5, 16, 8, 4, 2, 1