Ciąg Fibonnaciego - do 100 000

0

Witam.
Potrzebuję pomocy z zadaniem, którego nie potrafię rozwiązać. Nie można wykorzystywać bibliotek typu gmp. :/ Trzeba napisać program w C++, który oblicza wartość n-tego wyrazu ciągu Fibonnaciego. To ma przejść przez sprawdzarkę, która nie przepuszcza programów, których czas przekracza 77,10 s i pamięć 10 000 kb.
Z góry dziękuję.

2

co to, jakieś zadanie wam dowalili na studiach i nikt sobie nie radzi? To już trzeci taki temat w ciągu ostatnich dni.

0

Kilka osób zrobiło z tego co wiem. :D

0

A próbowałeś https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego#Wz.C3.B3r_Bineta?

0

Tak, pisze, że zła odpowiedź.

0

Daj dokładną treść zadania i tą sprawdzarkę.

0

"Ciąg Fibonacciego zdefiniowany jest w następujący sposób: F1 = 1, F2 = 1, Fn = Fn−2 + Fn−1, dla n > 2.

Napisz program, który otrzymawszy numer wyrazu ciągu obliczy jego wartość.

Wejście

W pierwszej (i jedynej) linii wejścia znajduje się liczba n (1 ≤ n ≤ 100000) — numer wyrazu ciągu.

Wyjście

Na wyjściu należy wypisać wartość n-tego wyrazu ciągu.

Przykład

Wejście

500
Wyjście

139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125"

0

Tworząc własny typ przechowujący liczby w systemie o podstawie 259 fib(100000) liczy sekundę (+ wypisywanie O(n^2)).

0

poszukaj innych wątków. Tak jak już wspomniał @pingwindyktator już ktoś poruszał temat dostał podpowiedzi (i pewnie to on zaliczył zadanie).

0
unsigned int fib(unsigned int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1)+fib(n-2);
}

Przyda się?

0
  1. Do wyliczenia n-tej liczby użyj macierzy i szybkiego potęgowania: https://pl.wikipedia.org/wiki/Ciąg_Fibonacciego#Macierze_liczb_Fibonacci.27ego
  2. Ponieważ liczby są duże, zaimplementuj własną artymetykę. Możesz opierać się na http://main.edu.pl/pl/user.phtml?op=lesson&n=32 lub wziąć gotowca ze Stańczyka (aczkolwiek jeżeli nigdy tego nie pisałeś, to polecam przynajmniej raz to zaklepać samemu).
0

Do optymalności daleko ale masz... Tym bardziej że kodowanie "na stringach" to taki sobie wybór...
Zastanawiałem się czy da się to napisać bez jawnych if'ów. Da się :-)

#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <vector>
#include <cassert>

using namespace std;

class StringValue {
public:
    StringValue(const string& src = "0") : m_str{src} {}
    StringValue& operator+(const StringValue& string_val) {
        size_t result_size = max(m_str.length(), string_val.get_string().length());
        vector<int> vec(result_size);
        div_t div_result = {0, 0};

        // Wypełnienie wektora wartościami.
        transform(m_str.rbegin(), m_str.rend(), vec.rbegin(), vec.rbegin(),
            bind(minus<int>(), placeholders::_1, '0'));
        // Dodanie wartości z 2'iego stringu.
        transform(string_val.get_string().rbegin(), string_val.get_string().rend(), vec.rbegin(), vec.rbegin(),
            [](int chr_val, int val) {
                return val + (chr_val - '0');
            });

        transform(vec.rbegin(), vec.rend(), vec.rbegin(),
            [&div_result](int val) {
                // Sumowanie wraz z przeniesieniem.
                div_result = div(val + div_result.quot, 10);
                return div_result.rem;
        });

        // Wynik ma rozmiar zależny od pozostałej reszty.
        m_str = string(result_size + div_result.quot, '0');
        // Zamiana wartości liczbowych na ascii.
        //
        transform(vec.rbegin(), vec.rend(), m_str.rbegin(),
            bind(plus<int>(), placeholders::_1, '0'));
        m_str.front() += div_result.quot;
        
        return *this;
    }
    const string& get_string() const {
        return m_str;
    }
private:
    string m_str;
};

// A taki inny .. bo chciałem bez if'a .. "bo tak"  :-)
StringValue fibonacci(size_t n) {
    assert(n > 0);
    auto x1 = StringValue("1");
    auto x2 = StringValue("1");
    StringValue result, temp;
    result = x1;
    for(size_t i = 1; i <= n; ++i) {
        result = x1;
        temp = x1 + x2;
        x1 = x2;
        x2 = temp;
    }
    return result;
}

int main(void) {
    cout << 500 << ": " << fibonacci(500).get_string() << endl;
}

Oczywiście lepiej jak radzili koledzy. Metodą mnożenia macierzy oraz z implementacją typów długich..

0

Karatsuba + mnożenie macierzy: VS2008 WM fibonacci duże liczby

W Javie BigInteger jest w standardzie, w C++ pewnie trzeba zaimplementować samemu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1