przekroczenie limitu czasowego
Ostatnio zmodyfikowano 2014-01-06 22:13
szirot Temat założony przez niniejszego użytkownika |
przekroczenie limitu czasowego » 2014-01-06 17:38:33 tresc: Agnieszka tak polubiła ciągi rekurencyjne, że nie zastanawia się już dłużej nad królikami, tylko analizuje same wzory. Tym razem prosi o obliczenie wartości elementów ciągu określonego wzorami: A(0)=4, A(1)=7, A(n)=2A(n-1)+5A(n-2) dla n>=2. Agnieszka zdaje sobie sprawę, że taki ciąg rośnie bardzo szybko, a więc chciałaby poznać tylko reszty z dzielenia jego wyrazów przez 2011.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita t<=10 oznaczająca liczbę testów.
W kolejnych liniach znajdują się poszczególne testy. Każdy z nich składa się z jednej liczby całkowitej n (0<=n<=100).
Wyjście
Dla każdego testu wypisz w osobnej linii resztę z dzielenia wartości A(n) przez 2011.
Przykład
Wejście:
3
0
1
2
Wyjście:
4
7
34 |
moj kod : #include <iostream>
using namespace std;
int fib( int n )
{
if( n == 0 ) return 4;
if( n == 1 ) return 7;
return 2 * fib( n - 1 ) + 5 * fib( n - 2 );
}
int main()
{
int x;
cin >> x;
for( int i = 0; i < x; i++ )
{
int n;
cin >> n;
cout << fib( n ) % 2011;
}
return 0;
} kod ogolnie dziala, tylko kiedy wrzucam na sprawdzarke nie akceptuje ona tego i wyskakuje ze przekroczono limit czasowy. Prosilbym o pomoc. Z gory dzieki. |
|
pekfos |
» 2014-01-06 17:48:53 Przede wszystkim, w tego typu zadaniach nie używa się strumieni C++, bo są za wolne. Użyj biblioteki standardowej C. Implementacja ciągu też nie jest optymalna. Najlepiej zaimplementuj w oparciu o programowanie dynamiczne. |
|
Monika90 |
» 2014-01-06 22:13:16 najlepsze są rozwiązania najprostsze main = do
putStr "#include <stdio.h>\nint a[] = {\n"
let a = 4 : 7 : zipWith (\a0 a1 -> 2 * a1 + 5 * a0) a (tail a)
mapM_ (putStr . (++ ",") . show . (`mod` 2011)) $ take 101 a
putStr "\n};\n\
\int main() {\n\
\ int n;\n\
\ scanf(\"%i\", &n);\n\
\ for (int i = 0; i < n; ++i) {\n\
\ int j;\n\
\ scanf(\"%i\", &j);\n\
\ printf(\"%i\\n\", a[j]);\n\
\ }\n\
\}"
|
|
| « 1 » |