Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Using A Map For Dynamic Programming In C++

DZone's Guide to

Using A Map For Dynamic Programming In C++

·
Free Resource
// A solution to the "Three N + 1" Problem for the UVa Online Judge
// The difference between the DP solution and the brute-force solution is dramatic -- 
// a run-time of 1.030 seconds drops to 0.370 


#include 
  
   
#include 
   
using namespace std;

int main() {
    map
    
      results;
    map
     
      ::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
      
       (j, cycles));
            } else {
                cycles = it->second;
            }
            if (cycles > maxcycles) maxcycles = cycles;
            cycles = 1;
        }
        
        cout << maxcycles << endl;
        maxcycles = 0;
        cycles = 1;
    }
	
	return 0;
}


      
     
    
  
Topics:

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}