Przekroczenie limitu czasu - silnia
Ostatnio zmodyfikowano 2012-11-17 18:15
Kentox Temat założony przez niniejszego użytkownika |
Przekroczenie limitu czasu - silnia » 2012-11-17 17:37:35 Wysłałem na sprawdzaczkę internetową mój kod rozwiązujący zadanie dwie cyfry silni. Jednak program przekroczył limit czasowy (1 minuta). Jak można zoptymalizować mój kod ??? Treść zadania: Niech n będzie nieujemną liczbą całkowitą. Liczbę n! (czytaj n-silnia) definiuje się następująco. Jeśli n ≤ 1, to n! = 1. Dla n > 1, n! jest równe iloczynowi wszystkich liczb od 1 do n, czyli n! = 1 * 2 * ... * n. Na przykład 4! = 1*2*3*4 = 24.
Zadanie
Napisz program, który:
wczyta ze standardowego wejścia nieujemną liczbę całkowitą n,
policzy cyfrę dziesiatek oraz cyfrę jedności w zapisie dziesiętnym liczby n!,
wypisze wynik na standardowe wyjście.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowia D (1≤D≤30), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku składa się z jednej linii, w której znajduje się jedna nieujemna liczba całkowita n (0 ≤ n ≤ 1 000 000 000).
Wyjście
Dla każdego przypadku z wejścia. Twój program powinien wypisać w osobnej linii dokładnie dwie cyfry (oddzielone pojedynczą spacją): cyfrę dziesiątek i cyfrę jedności liczby n! zapisanej w systemie dziesiętnym.
Przykład
Dla danych wejściowych:
2
1
4
poprawną odpowiedzią jest:
0 1
2 4 |
Mój kod: #include <iostream>
using namespace std;
int main() {
int d;
long long int a, silnia;
cin >> d;
for( int j = 0; j < d; j++ ) {
cin >> a;
silnia = 1;
for( int i = 0; i < a; i++ ) {
silnia =( silnia *( i + 1 ) ) % 100;
}
cout <<(( silnia % 100 ) / 10 )
<< silnia % 10 << endl;
}
} |
|
ison |
» 2012-11-17 17:43:31 Nie możesz iterować tyle razy. Hint: policz sobie kilkanaście kolejnych wartości silni i zobacz jakie powinny być dla nich odpowiedzi. |
|
wybraniec |
Optymalizacja » 2012-11-17 17:51:07 To że można rozwiązać ten problem szybciej to rozumiem, ale czemu Twoim zdaniem nie można iterować tyle razy (pomijając że 'i' musiałoby być long long)? Jest jakiś limit iteracji dla pętli for? |
|
anonim |
» 2012-11-17 18:01:28 wszystkie silnie powyżej 9! kończą się dwoma zerami (bo mają dwie piątki i dwie dwójki w rozkładzie) Policz sobie wartości n! dla n = 1 ... n = 9 i wypisuj je za pomocą if np: cin >> n;
if( n == 1 or n == 0 )
cout << 01;
else if( n == 2 )
cout << 02;
else if( n == 3 )
cout << 06
...
else if( n > 19
cout << 00; |
|
Kentox Temat założony przez niniejszego użytkownika |
Dzięki wszystkim !!! » 2012-11-17 18:15:18 Dziękuję wszystkim za pomoc. Mój ostateczny kod : #include <iostream>
using namespace std;
int main() {
int d;
long long int a, silnia;
cin >> d;
for( int j = 0; j < d; j++ ) {
cin >> a;
silnia = 1;
if( a < 10 ) {
for( int i = 1; i <= a; i++ ) {
silnia = silnia * i;
}
} else {
silnia = 0;
}
cout <<(( silnia % 100 ) / 10 ) << " " << silnia % 10 << endl;
}
} |
|
Kentox Temat założony przez niniejszego użytkownika |
Dzięki wszystkim !!! » 2012-11-17 18:15:35 Dziękuję wszystkim za pomoc. Mój ostateczny kod : #include <iostream>
using namespace std;
int main() {
int d;
long long int a, silnia;
cin >> d;
for( int j = 0; j < d; j++ ) {
cin >> a;
silnia = 1;
if( a < 10 ) {
for( int i = 1; i <= a; i++ ) {
silnia = silnia * i;
}
} else {
silnia = 0;
}
cout <<(( silnia % 100 ) / 10 ) << " " << silnia % 10 << endl;
}
} |
|
| « 1 » |