所以,我很无聊,决定做一些完全随机的东西,然后我遇到了Collatz的猜想:以任何正数开头,如果是任何正数,如果是,则偏向两个。如果很奇怪,请乘以三,然后添加一个。重复此操作时,您将以第一名结束。所以我制作了此代码:
//卢卡斯·诺克(Lucas knook(的collatz猜想
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
long long n;
cin >> n;
cout << setw(5) << n;
while(true){
if(n % 2 == 0 && n != 1){
//is even
cout << " E" << endl;
n /=2;
cout << setw(5) << n;
}
else if(n != 1){
//is odd
cout << " O" << endl;
n = n * 3 + 1;
cout << setw(5) << n;
}
else break;
}
cout << " O" << endl << endl << "end loop";
return 0;
}
我仍在学习C (我刚刚完成了SoloLearn课程,我将获得" c 为假人多合一"的书(,但是我认为这对我来说是一个很好的开始,它可以正常运行。
只有一个小问题:如果我使用大数字,它确实会停止,并且变得奇怪甚至正确,但是...
输入时查看输出的第一部分" 1000000000000000000000000
":
9223372036854775807 O
9223372036854775806 E
4611686018427387903 O
-4611686018427387906 E
-2305843009213693953 O
-6917529027641081858 E
-3458764513820540929 O
8070450532247928830 E
4035225266123964415 O
-6341068275337658370 E
-3170534137668829185 O
8935141660703064062 E
4467570830351532031 O
-5044031582654955522 E
-2522015791327477761 O
-7566047373982433282 E
-3783023686991216641 O
7097673012735901694 E
3548836506367950847 O
-7800234554605699074 E
ehm,有点奇怪,不是吗?(不要看线路断裂,它是完美的堆叠,只是在这里没有显示,因为我复制了输出(
有人可以向我解释为什么会发生这种情况以及如何解决?
您超出了long long
整数值的限制。输出中的第一个值被截断为要比输入小得多,然后当您到达4611686018427387903
时,它乘以3,因为它甚至没有。那是当它溢出类型并将其包裹成负值时。您需要使用biginteger库,例如ttmath。
基本上,正如其他人指出的那样,您不会检查溢出。但是我想指出的是,您的代码仍然没有有效,因为您不检查是否进入无尽的循环,当乘法和除法序列生成相同的数字时,您的时代将永远不会结束。
这是正确的代码,具有简单的溢出检测:
#include <iostream>
#include <unordered_set>
bool colatazConjecture(int n) {
std::unordered_set<int> localComputed;
int newN = 0;
while (n != 1) {
if (!localComputed.emplace(n).second) {
throw "Cycle detected";
}
newN = n;
if (n & 0x1) {
newN = 3*n + 1;
if (newN <= n) {
throw std::overflow_error("Overflow for " + std::to_string(newN));
}
} else {
newN >>= 1;
}
n = newN;
}
}