Dziwne potęgowanie

0

Witam, mam taki dziwny problem. Robię zadanie na spoj "Czy umiesz potęgować" i o dziwo problemy przyszły bardzo szybko.
Nie wiem czym to jest spowodowane, ale kiedy potęguję np. 2 do potęgi trzeciej to wynik jest dobry ale już 11 do drugiej wypisuje 120 zamiast 121, tak samo 13 do drugiej. Niżej kod

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int a, b, liczba;

    cin >> a >> b;

    liczba = pow(a, b);

    cout << liczba;
}

screenshot-20201029192644.png

2

Liczby zmiennoprzecinkowe są prawie zawsze obliczane w przybliżeniu (link: http://kaczus.ppa.pl/art/liczbyzmiennoprzecinkowe,19.html ) ale że to się dzieje dla 13² to aż mi się nie chce wierzyć

Ale tak przy okazji: to w tym zadaniu nie potrzebujesz użyć funkcji pow() do obliczenia wyniku. A nawet nie możesz.

0
kq napisał(a):

Liczby zmiennoprzecinkowe są prawie zawsze obliczane w przybliżeniu (link: http://kaczus.ppa.pl/art/liczbyzmiennoprzecinkowe,19.html ) ale że to się dzieje dla 13² to aż mi się nie chce wierzyć

Po drodze przelatuje przez logarytm/exp. A podstawienie pod integera to (chyba) obcięcie a nie zaokrąglenie. Wystarczy końcówka .99 i leci jeden w dół.

0

Ja rozumiem jak to może się stać, ale potęga jest naturalna, a zarówno 13, 2 jak i 169 są w pełni dokładnie wyrażalne za pomocą liczb zmiennoprzecinkowych (a nawet przez 16-bitowe floaty), stąd moje zdumienie. No i nie umiem powtórzyć tego błędu u siebie.

0

Napisz własną funkcję do potęgowania, albo dodawaj 0.5 do wyniku przed rzutowaniem na int

0

No więc napisałem swoją funkcję do potęgowania, i niby wszystko jest okej, ale sędzia odrzuca bo przekroczono limit czasu.

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int a, b, ile, ostatnia_cyfra;
    int wynik = 1;

    cin >> ile;

    for(int i = 0; i < ile; i++)
    {

    cin >> a >> b;

    for(int i = 0; i < b; i++)
    {
        wynik *= a;
    }

    ostatnia_cyfra = wynik % 10;

    cout << ostatnia_cyfra << endl;

    }
}

1

Nie napisałeś żadnej funkcji poza main() ;​)

Musisz wziąć kilka rzeczy pod uwagę:

  • liczby w komputerze mają ograniczony zbiór wartości. Najczęściej dla int jest to od -2³¹ do 2³¹-1. Prawie na pewno wychodzisz tu poza ten zakres i masz bzdurne wyniki
  • jeśli przyjrzysz się wynikom, możesz zauważyć, że wcale nie musisz wykonywać tak wielu obliczeń - to jest zadanie na myślenie.
1

Najlepiej wklej tu treść zadania, pełną, będzie łatwiej prognozować ;)

0

Przecież tu nie można nic potęgować, liczby są za duże. Problem był na tym forum, poszukaj.

0

Nie jest źle. Jak pierwszy raz usiadłem do C++ to używałem operatora:

^

Myślałem, że służy do potęgowania :D

1

Treść zadania:
https://pl.spoj.com/problems/PA05_POT/

Algorytm:
https://en.wikipedia.org/wiki/Modular_exponentiation

Lista znalezionych w tym wątku błędów:

  • liczenie potęgi przy pomocy liczb zmienno-przecinkowych (szybko straci się dokładność)
  • liczenie w pętli (zarówno a jak i b mogą być 1E9)
  • brak modulo na początku
  • nie zastosowanie ww. podstaw matematycznych
1

Ech, wiecie, że potęgowanie w tym zadaniu powinno być wykonane w O(1)?

1

Z tego co pamietam, to z potęgowaniem modularnym rozwiązanie przechodziło, złożoność O(30); @enedil czemu O(10)? Potęgowanie modularne jest O(log(n)), (z miliarda 30). Ale można to zrobić lepiej:
https://duckduckgo.com/?t=canonical&q=last+digit+of+exponeneation&atb=v219-1&ia=web

0

Ja zrobiłem to tak:

#include <iostream>
#include <vector>
#include <utility>

int pow(int a, int b)
{
    int p = 1;
    
    for (int i = 0; i < b; i++)
        p *= a;
    
    return p;
}

int main()
{
    using namespace std;
    
    long long ile;
    cin >> ile;
    
    vector<pair<int, int> > ab;
    
    for (int i = 0; i < ile; i++)
    {
        int a, b;
        cin >> a >> b;
        ab.push_back(make_pair(a, b));
    }
    
    long long potegi[31] = {1}; // potegi[0] -> ^1
    
    for (int i = 1; i < 31; i++)
        potegi[i] = potegi[i - 1] * 2;
    
    for (int i = 0; i < ile; i++)
    {
        int reszty[31] = {0};
        
        reszty[0] = pow(ab[i].first, 1) % 10;
        
        for (int j = 1; j < 31; j++)
        {
            reszty[j] = pow(reszty[j - 1], 2) % 10; // reszty[0] -> a ^ 1
        }
        
        long long sumaPoteg = 0;
        long long reszta = 1;
        
        for (int k = 30; sumaPoteg < ab[i].second; k--)
        {
            if (sumaPoteg + potegi[k] > ab[i].second)
                continue;
            
            sumaPoteg += potegi[k];
            reszta = (reszta * reszty[k]) % 10;
        }
        
        cout << reszta << endl;
    }
    
    
    return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1