Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Ostatnia cyfra szybkiego potęgowania

Ostatnio zmodyfikowano 2015-09-24 17:43
Autor Wiadomość
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
P-137863
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 !!!;
C/C++
#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)
C/C++
#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:)
C/C++
#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

C/C++
char pow_cyfra( int base, unsigned p )
{
    if( !p ) return '1'; // i tutaj też masz dodane
   
    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 ); // tutaj masz dodane 48 :P
}

//nie analizowałem algorytmu i nie starałem się zbytnio go zrozumieć ale jeśli chodzi o twoje pytanie odnośnie 48 to widzę je tak :P

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;
}
P-137881
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ć.
P-137885
mateczek
:)
» 2015-09-24 12:24:01
dla 5 zawsze 5 :)
P-137886
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.
P-137887
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.
C/C++
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ć.
P-137890
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
P-137892
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.

pow(a%10,b%4)
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.
P-137893
« 1 » 2
  Strona 1 z 2 Następna strona