Advanced Search

Return to Snippet

Revision: 61177
at December 2, 2012 12:34 by rtperson
Initial Code 
#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;
}
Initial URL 

                                

                                                            

                                    

                                        

                                        Initial Description
                                        

                                    

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

                                

                                                            

                                    

                                        

                                        Initial Title
                                        

                                    

                                    
Using a Map for Dynamic Programming in C++

                                

                                                            

                                    

                                        

                                        Initial Tags
                                        

                                    

                                    
c++

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
C++