Xử lý số lớn tính Catalan Number

Tuan_Cris · May 5, 2020, 6:23am

bài này e nộp thì bị sai,lỗi do e chưa xử lý số lớn mà e chưa hiểu lắm xử lý kiểu gì,các a giúp e.
code của e: https://www.ideone.com/o4aQwh

tntxtnt · May 5, 2020, 2:47am

em xài vector<unsigned long int> dp(n+1) thay vì unsigned long int dp[n+1]; :V

và truyền n vào solve(): gọi solve(n) bộ vất vả lắm sao? :V

và đặt tên hàm solve cho có nghĩa tí: solve cái gì? Solve là động từ sao lại cout/nhìn thấy nó được? :V Nó trả về catalan number thứ n sao ko đặt tên nó là danh từ catalanNumber(int n) luôn :V

còn số lớn thì em có thể thử cpp_int trong Boost :V và cầu cho trình biên dịch em nộp nó có thêm thư viện Boost :V

#include <boost/multiprecision/cpp_int.hpp> 
using boost::multiprecision::cpp_int;

...
std::vector<cpp_int> dp(n + 1);

https://www.geeksforgeeks.org/advanced-c-boost-library/ trang này cùi bắp mà được chỗ cái gì cũng có :V

Tuan_Cris · May 5, 2020, 3:18am

về phần đặt tên hàm e sẽ sửa ạ,nhưng trình biên dịch e ko có thư viện Boost ạ

tntxtnt · May 5, 2020, 3:46am

trình biên dịch lúc em nộp bài hay là ở máy của em ko có?

nếu chỉ là máy của em thì em viết code kiểu này:

using BigInt = int64_t;

còn khi nộp thì em sửa dòng đó lại thành

#include <boost/multiprecision/cpp_int.hpp> 
using BigInt = boost::multiprecision::cpp_int;

code ở dưới xài std::vector<BigInt> dp(n+1); bình thường :V

còn ko có thì chuyển sang ngôn ngữ khác như Python mà nộp cho có số lớn =]

Tuan_Cris · May 5, 2020, 5:09am

a ơi,e viết using BigInt = int64_t; vào mà máy e vẫn lỗi là do e viết sai,a xem rồi sửa lại giúp e a;:

#include <bits/stdc++.h>
using BitInt = int64_t;
using namespace std;

unsigned long in catalanNumber(int n) {
    vector<BigInt> dp(n+1);
    dp[0] = dp[1] = 1;
    for (int i=2; i<=n; i++) {
        dp[i] = 0;
        for (int j=0; j<i; j++)
            dp[i] += dp[j] * dp[i-j-1];
    }
    return dp[n];
}

rogp10 · May 5, 2020, 4:27am

Ca 100 tới 57 chữ số đấy

896519947090131496687170070074100632420837521538745909320

Làm 1 cái cấu trúc nho nhỏ vậy

Tuan_Cris · May 5, 2020, 4:25am

e thấy bạn e nó dùng python nhưng mà e chưa học python,

Tuan_Cris · May 5, 2020, 4:26am

hàm như thế nào vậy a

rogp10 · May 5, 2020, 6:31am

Nhầm, cấu trúc.

Xử lí số lớn thì dùng cơ số 10^9 là dễ nhất một slot int32_t là 9 chữ số thập phân.
Từ slot 0 đến slot 7 có độ lớn tăng dần (tức là đọc ngược viết xuôi).
Thêm 4 byte ghi số slot nữa là có bignum để dùng

Thuật toán nhân thì slot 2 nhân slot 3 ra slot 5, thương cộng thêm cho slot 6. Phép chia mới là thốn, chưa bao h thấy code free dùng cơ số 2^32 vì từ nhị phân đổi ra số thập phân rất là thốn.

noname00 · May 5, 2020, 6:24am

N = 100 tính ngoài rồi gọi mảng hằng đi cho dễ

string catalan_number[100] = {
    "1", "1", "2", "5", "14", "42",...
};

tntxtnt · May 5, 2020, 2:21pm

using BitInt là cái gì đây :V BigInt chứ :V
kiểu trả về của hàm catalanNumber unsigned long in là gì đây :V Trả về BigInt luôn chứ :V

sửa 2 cái lại rồi chạy thấy tới 36 thì ngủm =]

C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14
C(5) = 42
C(6) = 132
C(7) = 429
C(8) = 1430
C(9) = 4862
C(10) = 16796
C(11) = 58786
C(12) = 208012
C(13) = 742900
C(14) = 2674440
C(15) = 9694845
C(16) = 35357670
C(17) = 129644790
C(18) = 477638700
C(19) = 1767263190
C(20) = 6564120420
C(21) = 24466267020
C(22) = 91482563640
C(23) = 343059613650
C(24) = 1289904147324
C(25) = 4861946401452
C(26) = 18367353072152
C(27) = 69533550916004
C(28) = 263747951750360
C(29) = 1002242216651368
C(30) = 3814986502092304
C(31) = 14544636039226909
C(32) = 55534064877048198
C(33) = 212336130412243110
C(34) = 812944042149730764
C(35) = 3116285494907301262
C(36) = -6486945687849098124

nhưng code vậy đúng rồi, chỉ còn sửa lại thành cpp_int rồi đem nộp là được :V Ko được gì phải viết số lớn gì đó thôi xài Python đi =] hay tạo mảng 100 chuỗi số đó mà in ra =]