Output bài toán Collatz conjecture

Hong_Minh_Tran · November 23, 2021, 3:05pm

Mọi người cho em hỏi về cách giải bài Collatz conjecture ạ. Yêu cầu nhập vào 1 số tự nhiên khác 0, nếu số đó là số lẻ thì nhân 3 rồi cộng 1, nếu là số chẵn thì chia 2 cho đến khi gặp được số 1. Viết chương trình C++ cho biết cần bao nhiêu bước để tới được số 1.
Đây là code C++ của mình, khi nhập vào các số trên 2 nghìn tỉ thì kết quả bị sai.
Ví dụ nhập vào số 2 081 751 768 559 thì output đúng phải là 1437 nhưng code của mình chỉ cho ra output là 682.

#include <iostream>
#include <stdint.h>
using namespace std;
typedef unsigned long long uint64;

uint64_t CollatzConjecture(uint64_t n)
{
    uint64_t dem = 0;
    while (n != 1)
    {
        n= (n&1) ? n*3+1 : n/2;
        cout << n << " ";
        dem++;
    }
    cout<<endl;
    return dem;
}
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL) ; 
    uint64_t n;
    cin>>n;
    cout<<CollatzConjecture(n);
    return 0;
}

kisuluoibieng · November 23, 2021, 3:30pm

làm sao bạn biết được đáp án là 1437 mà không phải là số như của bạn đã tính ra?
bạn đã biết in số ra để kiểm tra, vậy bạn đã tự tính toán bằng tay để so thử vài bước đầu chưa?

Hong_Minh_Tran · November 23, 2021, 3:38pm

1437 là output mẫu mà thầy mình cho ạ. Mình tính tay vài bước đầu thì thấy code chạy đúng nên mình không biết bị sai ở đâu ạ

kisuluoibieng · November 23, 2021, 5:47pm

không loại trừ trường hợp sai đề

bạn có thể kiểm tra bằng file excel bằng công thức và kéo công thức ra 1437 dòng để ra cột đáp án
bạn có thể in ra n dòng bằng code, sau đó quét chuột copy đáp án hoặc ghi đáp án ra file
rồi sau đó bạn sẽ có 2 cột excel, một cột được tính bằng excel, một cột được tính bằng code chẳn hạn
thêm 1 cột điền công thức if bằng thì in ra yes, khác thì in ra no
rồi tìm chữ no nằm ở đâu, dòng nào trong file excel thôi

đại loại là so kết quả từ tính bằng excel và kết quả tính bằng code thôi
bạn cũng có thể viết code bằng ngôn ngữ khác để đối chiếu (python chăc chưa đầy 10 dòng code, hay js bật chrome/edge chạy luôn, cũng chưa tới chục dòng code)

tntxtnt · November 23, 2021, 6:39pm

có lẽ bị tràn số ở bước nào đó, nhân 3 nhiều quá 64-bit integer

có 3 cách giải quyết

1 là xem compiler có support int 128 bit ko: thử xài __int128 trong <cstdint>, nhưng lỡ nhân 3 vẫn vượt quá 128-bit int thì cũng ko được :V
2 là tự viết class số lớn riêng (chỉ có nhân 3 và chia 2 thì dễ)
3 là xài boost::multiprecision::cpp_int, thử #include <boost/multiprecision/cpp_int.hpp> coi có ko :V

Stanley00 · November 24, 2021, 2:44am

Bài dạng này thì có thể dùng thêm std::bitset nữa nha. Tham khảo tại wiki.

Code mẫu:

#include <iostream>
#include <bitset>
#include <tuple>

using X = std::bitset<1024>;

auto operator+(X a, const X& b){
	const auto adder = [](auto c, auto x, auto y){
		return std::make_tuple((x&y) | (y&c) | (c&x), x^y^c);
	};

	bool c = false;
	for (size_t i=0; i<a.size(); ++i){
		bool tmp;
		std::tie(c, tmp) = adder(c, a[i], b[i]);
		a[i] = tmp;
	}
	return a;
}

constexpr X ONE{1};

int main(){
	uint64_t tmp;
	std::cin >> tmp;
	
	X n{tmp};

	int count=0;
	while (n!=ONE){
		if ((n & ONE) != ONE){
			n >>= 1;
		}
		else{
			n = (n<<1) + n + ONE;
		}

		++count;
	}
	std::cout << count;
}