Я пытаюсь решить проблему 3n + 1, используя VS2010 c ++, при небольших входах он работает хорошо, но когда он достигает 113383, он переполняется.
Здесь проблемная ссылка.
Вот код, который я использую для решения этой проблемы:
#include <iostream>
using namespace std;
int main(void) {
while (!cin.eof()) {
int i, j, maxCycle = 0, tmaxCycle = 0;
cin >> i >> j;
for (int x = i; x <= j; x++) {
int n = x;
tmaxCycle = 0;
while (n != 1) {
if ((float)(n/2) != (n/2.0)) {
n = 3*n + 1;
}
else {
n /= 2;
}
tmaxCycle += 1;
if (n < 0) {
int blah = 0; //just for the breakpoint
}
}
tmaxCycle += 1;
if (tmaxCycle > maxCycle) {
maxCycle = tmaxCycle;
}
}
cout << i << "\t" << j << "\t" << maxCycle << endl;
}
system("pause");
}
Я сделал точку останова в строке 15, и в этой точке значения переполняются
n=-1812855948
Используйте 64-битные целые числа без знака. Если они переполнены, используйте библиотеку bignum, такую как Библиотека многократной точности GNU. Bignums дает вам неограниченную точность и размер.
это
if((float)(n/2)!=(n/2.0))
дает неверные результаты задолго до int
переполняется. Измените это на
if ( n & 1)