Here is the functions.h The Problem You remember the Collatz sequence, don\'t ya
ID: 3599616 • Letter: H
Question
Here is the functions.h
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 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 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 called lab08. Copy lab08_functions.h to your directory. You need to write both lab08 functions.cpp and lab08 main.cpp You will turn in 1lab08 functions.cpp to Mimir for testing 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 sequenceExplanation / Answer
the code so far i changed
#ifndef COLLATZ_MAP
#define COLLATZ_MAP
#include<vector>
using std::vector;
#include<string>
using std::string;
#include<map>
using std::map;
#include<utility>
using std::pair;
using Collatz = pair<long, vector<long> >;
/*
input is a positive (1 or greater) integer
returns the next collatz number
if number is 0 or less, throws range_error;
*/
long collatz_next(long n);
/*
input is a Collatz pair (pair<long, vector<long > >)
output is a string of the format
number: sequence (comma separated) ending in 1
no trailing comma
*/
string Collatz_to_string(const Collatz &p);
/*
input is a collatz map (map<long, vector<long> >)and a long
if the number exists as a key in the map
returns the Collatz_to_string of that pair
otw returns an empty string
*/
string sequence_in_map_to_string(map<long, vector<long> > &m, long number);
/*
input is a collatz map (map<long, vector<long> >)and a long
returns a vector<long>, the collatz sequence for that number
Operation. As you iterate through the collatz sequence
- uses collatz_next if the element in question is not in the map
- if the element *is* in the map, copies the sequence from the map
to the end of the current sequence and ends.
*/
vector<long> collatz_sequence(map<long, vector<long> > &m, long number);
/*
input is a collatz map (map<long, vector<long> >)and a low and high long
fills the map from low to high inclusive with each element's collatz sequence
using the function collatz_sequence
*/
void collatz_range(map<long, vector<long> > &m, long low, long high);
#endif