Posted By

rtperson on 12/02/12

Tagged

Versions (?)

Last Edited at 12/02/12 12:34pm

Statistics

Viewed 1534 times

Favorited by 0 user(s)

Related snippets

Using a Map for Dynamic Programming in C++

/ Published in: C++

Really DP-lite. Memoize the solution for a recursive problem so it can be looked up on subsequent iterations.

Highlighted TextExpand

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> results;
    map<int, int>::iterator it;
    int i, j, x, temp;
    int cycles = 1;
    int maxcycles = 0;
    while (cin >> i >> j) {
        cout << i << " " << j << " ";
        if (i > j) {
            temp = i;
            i = j;
            j = temp;
        }
        
        for (; j >= i; --j) {
            x = j;
            it = results.find(x);
            if (it == results.end()) {
                while (x != 1) {
                    if (x % 2 != 0) {
                        x = (3*x) + 1;
                    } else {
                        x /= 2;
                    }
                    ++cycles;
                }
                results.insert(pair<int, int>(j, cycles));
            } else {
                cycles = it->second;
            }
            if (cycles > maxcycles) maxcycles = cycles;
            cycles = 1;
        }
        
        cout << maxcycles << endl;
        maxcycles = 0;
        cycles = 1;
    }
	
	return 0;
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.