Collatz Conjecture c ++ странный вывод с большими числами - PullRequest
Новая
       20

Collatz Conjecture c ++ странный вывод с большими числами

0 голосов
/ 25 апреля 2018

Итак, мне было скучно, и я решил сделать что-то совершенно случайное, а затем натолкнулся на гипотезу Коллатца: начните с любого положительного числа, а если оно будет четным, разделите на два.Если это нечетно, умножьте на три и добавьте один.Повторяя это, вы окажетесь на первом месте.Итак, я сделал этот код:

// Collatz Conjecture от Lucas Knook 

#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

Эмм, это немного странноне так ли?(не смотрите на разрывы строк, они отлично сложены, здесь просто не видно, потому что я скопировал вывод)

Может кто-нибудь объяснить, почему это происходит и как это исправить?

Ответы [ 2 ]

0 голосов
/ 25 апреля 2018

В основном, как говорили другие люди, вы не проверяете переполнение. Но я хотел бы отметить другое: ваш код по-прежнему недействителен, так как вы не проверяете, попали ли вы в бесконечный цикл, когда последовательность умножения и деления генерирует одинаковые числа, ваше время никогда не закончится.

Это правильный код с простым обнаружением переполнения: 

#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;
    }
}
0 голосов
/ 25 апреля 2018

Вы превысили пределы long long целочисленных значений.Первое значение в вашем выводе усекается, чтобы быть намного меньше, чем ваш ввод, а затем, когда вы получаете 4611686018427387903, оно умножается на 3, поскольку оно не является четным.Именно тогда он переполняет тип и оборачивается в отрицательные значения.Вам нужно будет использовать библиотеку BigInteger, например TTMath .

...