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ę.
- Rejestracja:ponad 9 lat
- Ostatnio:ponad 9 lat
- Postów:4
0
C++ 
- Rejestracja:ponad 12 lat
- Ostatnio:25 dni
- Lokalizacja:Kraków
- Postów:1055
2
co to, jakieś zadanie wam dowalili na studiach i nikt sobie nie radzi? To już trzeci taki temat w ciągu ostatnich dni.
- Rejestracja:ponad 9 lat
- Ostatnio:ponad 9 lat
- Postów:4
0
Kilka osób zrobiło z tego co wiem. :D
- Rejestracja:ponad 9 lat
- Ostatnio:ponad 9 lat
- Postów:4
0
Tak, pisze, że zła odpowiedź.
- Rejestracja:ponad 9 lat
- Ostatnio:ponad 9 lat
- Postów:4
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"
Zobacz pozostałe 3 komentarze
Heheczek
faktycznie, racja. Maksymalnie udało mi się obliczyć 23000 wyraz ciągu na ideone a to jeszcze za mało. Wzór Bineta też jest ciężki więc jaką masz propozycje @kaczus? Użyć macierzy ? :P
Heheczek
http://ideone.com/g0eiAZ
kaczus
Zapomnij o lioczbach zmiennoprzecinkowych, one tu nie ulatwia, a utrudnia... Pomyśl na początku o tablicy znakowej (można to zoptymalizować.... Informacja, by nie uzywać gmp, podpowiada, ze trzeba napisac wlasne, uproszczone gmp....
Heheczek
heh pisałem to ale usunałem tego posta xd To może być przydatne: http://www.codeproject.com/Articles/1202/A-class-for-operations-with-Large-Integer-Numbers
Sopelek
@Heheczek 23000 na double? Przy jakichś 100 pewnie już miałeś złe wyniki
- Rejestracja:około 17 lat
- Ostatnio:3 minuty
0
poszukaj innych wątków. Tak jak już wspomniał @pingwindyktator już ktoś poruszał temat dostał podpowiedzi (i pewnie to on zaliczył zadanie).
- Rejestracja:prawie 17 lat
- Ostatnio:prawie 5 lat
- Rejestracja:prawie 18 lat
- Ostatnio:20 dni
0
- Do wyliczenia n-tej liczby użyj macierzy i szybkiego potęgowania: https://pl.wikipedia.org/wiki/Ciąg_Fibonacciego#Macierze_liczb_Fibonacci.27ego
- 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).
- Rejestracja:około 10 lat
- Ostatnio:około 2 godziny
- Lokalizacja:Tam gdzie jest (centy)metro...
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..
edytowany 1x, ostatnio: Mokrowski
- Rejestracja:prawie 20 lat
- Ostatnio:około 12 godzin
0
Karatsuba + mnożenie macierzy: VS2008 WM fibonacci duże liczby
W Javie BigInteger jest w standardzie, w C++ pewnie trzeba zaimplementować samemu.
