Omówienie zadania Kulki – Szybkie potęgowanie

Omówienie zadania Kulki – Szybkie potęgowanie

Szczegółowe omówienie zadania Kulki (szybkie potęgowanie):

Link do powyższego omówienia zadania Kulki:
https://youtu.be/7-gL_oWdX18?t=1144


Link do treści zadania Kulki:
https://szkopul.edu.pl/problemset/problem/kulki/site/


Zadanie Kulki pomaga w opanowaniu algorytmu szybkiego potęgowania.

Odnośniki  do poszczególnych punktów (algorytm, kod, złożoność) znajdują się na stronie:
https://www.facebook.com/2247317372200511/posts/2599070430358535

Jak się uczyć na podstawie takiego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019

——-
Kod C++ programu Kulki, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int ILORAZ_WARTOSC = 1e9+7;

long long SzybkiePotegowanie (long long podstawa, long long wykladnik) {
 long long potega_polowy;
 long long wynik;
 
 if (wykladnik == 0)
    return 1;
 
 potega_polowy = SzybkiePotegowanie (podstawa, wykladnik/2);
 wynik = potega_polowy * potega_polowy;
 wynik = wynik % ILORAZ_WARTOSC;

 if ( (wykladnik%2) == 1 ) {
    wynik = wynik * podstawa;
    wynik = wynik % ILORAZ_WARTOSC;
 }
 
 return wynik;
}

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int liczba_pytan, liczba_kulek;
 long long int wynik;
 int i;

 cin >> liczba_pytan;

 for (i=1; i<=liczba_pytan; ++i) {
    cin >> liczba_kulek;
    wynik = SzybkiePotegowanie (liczba_kulek,liczba_kulek);
    wynik = wynik - liczba_kulek;
    wynik = wynik + ILORAZ_WARTOSC;
    wynik = wynik % ILORAZ_WARTOSC;
    cout << wynik << "\n";
 }

 return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Kulki 
——–
——–
——–
——–
Poniżej dodatkowo kod C++, który wykonuje szybkie potęgowanie bez udziału rekurencji – również otrzymuje 100% z zadania.
#include <bits/stdc++.h>
using namespace std;

const int ILORAZ_WARTOSC = 1e9+7;

long long SzybkiePotegowanie (long long podstawa, long long wykladnik) {
 long long wynik;
 long long potega_podstawy;
 
 potega_podstawy = podstawa;
 wynik = 1;
 while (wykladnik > 0) {
    if ( (wykladnik%2) == 1 ) {
       wynik = wynik * potega_podstawy; 
       wynik = wynik % ILORAZ_WARTOSC;
	}
    potega_podstawy = potega_podstawy * potega_podstawy;
    potega_podstawy = potega_podstawy % ILORAZ_WARTOSC;
    wykladnik = wykladnik / 2;
 }
 return wynik;
}

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int liczba_pytan, liczba_kulek;
 long long int wynik;
 int i;

 cin >> liczba_pytan;

 for (i=1; i<=liczba_pytan; ++i) { cin >> liczba_kulek;
    wynik = SzybkiePotegowanie (liczba_kulek,liczba_kulek);
    wynik = wynik - liczba_kulek;
    wynik = wynik + ILORAZ_WARTOSC;
    wynik = wynik % ILORAZ_WARTOSC;
    cout << wynik << "\n";
 }

 return 0;
}
——–
——–
——–
——–
Poniżej dodatkowo kod Python, który wykonuje szybkie potęgowanie rekurencyjne
def szyb_modpot(liczba, pot):
    potega_liczby = liczba
    wynik = 1
    while pot > 0:
        if pot % 2 == 1:
            wynik = wynik * potega_liczby
           # wynik %= 1000000007
        potega_liczby = potega_liczby * potega_liczby
        potega_liczby = potega_liczby % 1000000007
        pot = pot // 2
    return wynik
    
for x in range(int(input())):
    n = int(input())
    wynik = szyb_modpot(n, n) -n + 1000000007
    wynik %= 1000000007
    print(wynik)

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz