lab08_functions.h #ifndef COLLATZ_MAP The Problem You remember the Collatz seque

Question

lab08_functions.h

#ifndef COLLATZ_MAP

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 33,10, 5, 16, 8, 4, 2,1 4 4,2,1 55, 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 of3 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 lab08 functions. cpp to Mimir for testing Data structure, map of lona 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 »

Explanation / Answer

Notice:
Execute it on your pc and send me comments if anything goes wrong.

**Explanation for each line in code comments.**

Cheers, have a great day mate!

Code:

Lab09_functions.h

#pragma once

#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> >;

long collatz_next(long n);
string Collatz_to_string(const Collatz &p);
string sequence_in_map_to_string(map<long, vector<long> > &m, long number);
vector<long> collatz_sequence(map<long, vector<long> > &m, long number);
void collatz_range(map<long, vector<long> > &m, long low, long high);

Lab08_functions.cpp

#include "stdafx.h"
#include "Lab08_functions.h"
#include <iostream>

int main()
{
    return 0;
}

/**
* gives the next collatz number
*/
long collatz_next(long n)
{
    // if number is 0 or less, throws range_error;
    if (n < 1) { throw std::range_error("Number should be positive (1 or greater)!"); }

    if (n % 2) { return n / 2; }
    else { return 3 * n + 1; }
}

/*
* display format for collatz
*/
string Collatz_to_string(const Collatz & p)
{
    std::string out{};
    // output is a string of the format number :
    out += std::to_string(p.first) + " : ";

    // sequence(comma separated)
    for (int i{ 0 }; i < p.second.size(); ++i)
    {
        out += p.second.at(i) + ", ";
    }

    // ending in 1 no trailing comma
    out += "1";
  
    return out;
}

string sequence_in_map_to_string(map<long, vector<long>>& m, long number)
{
    // if the number exists as a key in the map
    for (std::map<long, vector<long>>::iterator it = m.begin(); it != m.end(); ++it)
    {
        if (number == it->first) { return Collatz_to_string(*it); }
    }

    return string{};
}

/**
* returns the collatz sequence for that number
*/
vector<long> collatz_sequence(map<long, vector<long>>& m, long number)
{
    Collatz collatz;

    std::map<long, vector<long>>::iterator iterator{ m.find(number) };

    if (iterator != m.end())
    {
        // copies the sequence(collatz?) from the map           
        collatz.first = number;
        collatz.second = iterator->second;

        // to the end of the current sequence and ends.
        m.insert(collatz);
        return iterator->second;
    }

    // only init this vector if seq is not found!
    std::vector<long> collatz_seq{};

    collatz_seq.push_back(number);
    // uses collatz_next if the element in question is not in the map
    while (1)
    {
        number = collatz_next(number);

        if (number < 2) { break; }
        else { collatz_seq.push_back(number); }
    }

    collatz.first = number;
    collatz.second = collatz_seq;
    m.insert(collatz);

    return collatz_seq;
}

/*
* 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)
{

    for (long i{ low }; i < high + 1; ++i)
    {
        collatz_sequence(m, i);
    }
}

If this answer was helpful please Like / Vote Thumbs up!

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.