patox Temat założony przez niniejszego użytkownika |
Ostatnia cyfra szybkiego potęgowania » 2015-09-23 21:44:39 Witam Próbowałem zrobić zadanie na spoju http://pl.spoj.com/problems/PA05_POT/ Starałem się to zaimplementować na wiele sposobów w krótszym sposobie zarówno rekurencyjnie jak i iteracyjnie, ale pokazywało mi albo przekroczenie czasu, albo błędna odpowiedź mimo dobrych testów, które wpisywałem. Znalazłem coś takiego w necie dla char, wiem, że jak odejmę 48 to wyświetli mi się poprawny wynik i zadanie zostanie zaliczone, ale chciałbym zrozumieć jak to samemu zrobić w incie. Nie chcę gotowców, a zrozumieć tą funkcje, a jak na tą chwilę wydaje mi się podobne do tego co ja pisałem z wyjątkiem "p>>=1" bo nie bardzo rozumiem co to znaczy char pow_cyfra(int base,unsigned p) { if(!p) return '1'; if(base<0) base=-base; int pow=1; for(base%=10;p;p>>=1) { if(p&1) pow=(pow*base)%10; base=(base*base)%10; } return (char)('0'+pow); }
EDIT: Głównie kierowałem się tym https://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania |
|
mateczek |
Pytane czy chcesz na nowo wynaźć koło?? » 2015-09-24 11:26:09 funkcja potęgująca jest dostępna w bibliotece c++ nazywa się pow. jeśli interesuje Cię jak jest napisana to zawsze można zajrzeć i przeanalizować kod. Ale jeśli obchodzi cię wynik to po prostu z niej skorzystaj !!!; #include <iostream> using namespace std; #include"math.h" #include<string>
int main() { int a, b; cin >> a; cin >> b; int c = pow( a, b ); string temp = to_string( c ); cout << "ostania cyfra potęgowania " << temp[ temp.size() - 1 ] << " a wynik potęgi to " << c << endl; }
"p>>=1" bo nie bardzo rozumiem co to znaczy |
przesuń p w prawo o jeden bit. Lub jak wolisz dzielenie na dwa :)(coś jak przesuwanie przecinka w systemie dziesiętnym gdy mnożysz lub dzielisz przez 10) #include <iostream> using namespace std; int main() { unsigned a; cin >> a; cout << "wynikiem a>>=1" <<( a >> 1 ) << endl; }
Ale dlaczego gdy wprowadzę 100 to dostaje wynik 150 dalibóg nie wiem :P według mnie powinno być 50 :P Skąd mi się ta stówka dodaje nie mam pojęcia !!!! Tak czy siak ta wersja kodu chyba też zadziała:) jak ci rotacja bitowa nie podchodzi:) #include <iostream> using namespace std; int pow_cyfra( int base, unsigned p ) { if( !p ) return 1; if( base < 0 ) base = - base; int pow = 1; for( base %= 10; p; p = p / 2 ) { if( p & 1 ) pow =( pow * base ) % 10; base =( base * base ) % 10; } return pow; }
int main() { cout << "wynikiem " << pow_cyfra( 4, 4 ) << endl; }
że jak odejmę 48 to wyświetli mi się poprawny wynik |
nie musisz odejmować wystarczy byś nie dodawał :P char pow_cyfra( int base, unsigned p ) { if( !p ) return '1'; if( base < 0 ) base = - base; int pow = 1; for( base %= 10; p; p >>= 1 ) { if( p & 1 ) pow =( pow * base ) % 10; base =( base * base ) % 10; } return( char )( '0' + pow ); }
int pow_cyfra( int base, unsigned p ) { if( !p ) return 1; if( base < 0 ) base = - base; int pow = 1; for( base %= 10; p; p >>= 1 ) { if( p & 1 ) pow =( pow * base ) % 10; base =( base * base ) % 10; } return pow; }
|
|
Monika90 |
» 2015-09-24 12:18:40 Funkcja pow nie nadaje się do rozwiązania tego zadania, a algorytm szybkiego potęgowania nie jest potrzeby. Znaeleźć ostatnią cyfrę xy można za pomocą jednej linii trywialnego kodu, ale trzeba pomyśleć. |
|
mateczek |
:) » 2015-09-24 12:24:01 dla 5 zawsze 5 :) |
|
patox Temat założony przez niniejszego użytkownika |
» 2015-09-24 14:31:43 pow się nie sprawdza, oprócz szybkiego potęgowania jeszcze switch działa, ale to za długie, a uparłem się na jak najkrótsze rozwiązanie. Dziękuję Monika90, jeszcze pokombinuje to może znajdę ten sposób o którym mówisz. |
|
1aam2am1 |
» 2015-09-24 15:40:53 Tworzymy tabelkę, ostatnich liczb: 0*0->0 : 1 1*1->1 : 1 2*2->4*2->8*2->6*2->2 : 4 3*3->9*3->7*3->1*3->3 : 4 4*4->6*4->4 : 2 5*5->5 : 1 6*6->6 : 1 7*7->9*7->3*7->1*7->7 : 4 8*8->4*8->2*8->6*8->8 : 4 9*9->1*9->9 : 2 A oto fragment programu. switch( liczba % 10 ) { case 2: if( potega % 4 == 0 ) { koncowa = 2; } if( potega % 4 == 1 ) { koncowa = 4; } if( potega % 4 == 2 ) { koncowa = 8; } if( potega % 4 == 3 ) { koncowa = 6; } break; };
Możesz sprawdzić. |
|
patox Temat założony przez niniejszego użytkownika |
» 2015-09-24 16:23:31 1aam2am1 wiem jak to zrobić na switchu, według mnie switch to jedno z gorszych rozwiązań, próbowałem też to zrobić wyliczając pow(a%10,b%4), które jeżeli przekraczało 9 wyliczało modulo z 10, aby została tylko liczba jedności, ale wyskakuje błędna odpowiedź mimo, że testy, które wpisywałem były poprawne, robiłem to też rekurencyjnie i iteracyjnie szybkim potęgowaniem to miałem, przekroczony limit czasu, albo bład pewnie związany z przepełnieniem stosu, widziałem też sposób na liczenie bitów i ta funkcja chyba to robi o ile dobrze rozumiem, ale samemu jakoś tak opornie mi szła implementacja i po znalezieniu tego kodu odpuściłem tamto, jeszcze nie rozumiem tego sposobu na tyle, teraz wiem tylko jak zapisać tą funkcje i wydaje mi się, że mniej więcej wiem co robi, ale nie potrafię jeszcze tego w pełni zrozumieć, teraz staram się rozgryźć to co powiedziała Monika90 |
|
Monika90 |
» 2015-09-24 16:50:49 Miałam na myśli to co pokazał 1aam2am1, tylko zapisane w bardzo zwięzły sposób. Tak też się da, ale drugi argument musi być trochę inny. Kiedy b jest równe 4 (lub 8,12,...) to b % 4 jest równe zero, a powinno być 4. |
|
« 1 » 2 |