Lỗi khi cài đặt thuật toán fibonacci

tại vì số nguyên kiểu int chỉ chứa được tới giá trị 2 tỷ, quá 2 tỷ nó tràn số thành số âm

À ra là vậy ạ, vậy giờ cho mình xin hỏi là mình phải thay kiểu int thành kiểu khác hả bạn @@??

muốn bự hơn thì xài long long, giá trị nó chứa được tới 9 tỷ tỷ (2⁶³ - 1), đủ sức chứa tới n = 90.

muốn bự hơn nữa thì đáng tiếc thư viện chuẩn của C++ ko có kiểu BigInteger, phải xài thư viện ngoài, cài đặt khó khăn với newbie, thôi chấp nhận đỡ long long đi

Oh, cảm ơn bạn nhiều nhé, mình đã thay đổi và làm dc rồi, nhưng mình muốn tới n=100 thì giờ phải xài thêm thư viện ngoài và cài đặt kiểu khác hả bạn . Bạn gợi ý thêm cho mình cách làm dc ko, mình sẽ lên mạng và tìm hiểu thêm ạ @@

n=100 thì dùng kiểu bignum.

mất công lắm, bạn phải hiểu trình biên dịch là gì, rồi hiểu các giai đoạn biên dịch và liên kết, rồi mới biên dịch thư viện tương ứng cho trình biên dịch… @_@

thôi bạn gu gồ đỡ Boost.Multiprecision với MPIR

nếu chỉ xài phép cộng thì bạn tự viết class BigInteger cũng được, coi như làm bài tập

Cho mình xin hỏi kiểu bignum là sao ạ , mình mới là newbie thôi ạ @@

Ok, cảm ơn bạn nhiều ạ đã giúp đỡ mình tận tình ạ, mình sẽ tìm hiểu mấy cái bạn hướng dẫn cho mình ạ

Bignum lưu trữ và tính bao nhiêu chữ số cũng được, do kích thước không bị cố định.

Chưa xài new[] được thì lấy int[20] cũng được (cơ số 10^9).

Cảm ơn bạn nhé, để mình làm thử xem sao @@

hàng cùi bắp tự chế nè

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

struct BigInt {
    static const int E9 = 1e9;
    std::vector<int> data;
    BigInt() : data(1, 0) {}
    BigInt(int n) : data(1, n)
    {
        if (n >= E9)
        {
            data.push_back(n / E9);
            data[0] %= E9;
        }
    }
    BigInt& operator+=(const BigInt& rhs)
    {
        size_t minLen = std::min(data.size(), rhs.data.size());
        for (size_t i = 0; i < minLen; ++i)
            data[i] += rhs.data[i];
        for (size_t i = data.size(); i < rhs.data.size(); ++i)
            data.push_back(rhs.data[i]);
        for (size_t i = 0; i < data.size() - 1; ++i)
        {
            data[i+1] += data[i] / E9;
            data[i] %= E9;
        }
        if (end(data)[-1] >= E9)
        {
            data.push_back(end(data)[-1] / E9);
            end(data)[-2] %= E9;
        }
        return *this;
    }
    BigInt operator+(const BigInt& rhs)const
    {
        BigInt n = *this;
        n += rhs;
        return n;
    }
    void swap(BigInt& rhs)
    {
        data.swap(rhs.data);
    }
};

std::ostream& operator<<(std::ostream& out, const BigInt& n)
{
    out << end(n.data)[-1];
    for (size_t i = n.data.size() - 1; i--; )
        out << std::setw(9) << std::setfill('0') << n.data[i];
    return out;
}

int main()
{
    BigInt a = 0, b = 1;
    std::cout << "0 -> " << a << "\n";
    std::cout << "1 -> " << b << "\n";
    for (int i = 2; i <= 300; ++i)
    {
        a.swap(b);
        b += a;
        std::cout << i << " -> " << b << "\n";
    }
}

kiểm tra ở http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html thấy 300 số Fibo đầu tiên in ra đúng

Oh, cảm ơn bạn nhiều nhé. Mà hình như mình có chạy thử thì nó phát sinh lỗi ạ :’( . Bạn coi giùm mình vs :’(

fib2.PNG1322x624 117 KB

end(data) là cái gì hả bạn? Mà sao truy cập mảng lại có chỉ số -1, -2 thế kia?

Đừng screenshot màn hình code thế này, hãy up code lên.

Phải là data.end() chứ http://en.cppreference.com/w/cpp/container/vector/end

Thớt copy nguyên con thì 99% là sẽ bị hỏi vặn.

Thêm include <iterator> vô nữa @_@

Ehehe độc chiêu này chôm từ Python qua đó, vector::end là valid iterator, có điều ko truy cập đc, nhưng phần tử trước nó [-1] sẽ truy cập đc nếu vector ko empty. Thành ra viết kiểu end(data)[-1] để truy cập phần tử cuối cùng cho nó giống Python p[-1]

Ấy, chuẩn C++ nào thế anh? Vụ này mới quá. Thảo nào em cứ thấy có mùi Python đâu đấy ~~

C++11 mà thôi dùng C++03 là làm được bài này rồi.

Thêm include <iterator> vô nữa @_@

C++11

Chuẩn thì vector::end() - 1 trả về iter hợp lệ nếu vector ko empty, nên end§[-1] cũng hợp lệ nếu p ko empty. Truy cập phần tử cuối cùng xài back() cũng đc nhưng phang -1 cho nó Pythonista, với lại -2 nữa cũng đẹp.