Collatz Conjecture c ++ странный вывод с большими числами
Итак, мне было скучно, и я решил сделать что-то совершенно случайное, а затем натолкнулся на гипотезу Коллатца: начать с любого положительного числа и, если оно четное, разделить на два. Если это нечетно, умножьте на три и добавьте один. Повторяя это, вы окажетесь на первом месте. Итак, я сделал этот код:
// Гипотеза Коллатца Лукаса Кнука
#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
Это немного странно, не правда ли? (не смотрите на разрывы строк, они отлично сложены, просто не отображаются, потому что я скопировал вывод)
Может кто-нибудь объяснить, пожалуйста, почему это происходит и как это исправить?
Решение
Вы превысили пределы 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;
}
}