Using A Map For Dynamic Programming In C++
Join the DZone community and get the full member experience.
Join For Free// 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
โ
โ
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;
}
โ
โ
Opinions expressed by DZone contributors are their own.
Comments