szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 cze 2018, o 14:52 
Użytkownik

Posty: 8
Lokalizacja: Bydgoszcz
Witam, otrzymałem takie oto zadanie:

Podaj, w jaki sposób zostanie obliczona wartość potęgi x^{n} za pomocą możliwie najmniejszej liczby mnożeń dla wykładnika, który jest dany jako liczba w systemie trójkowym: n = (1212)_{3}. Zapisz ciąg kolejno wykonywanych mnożeń w tym przypadku. Ile ich jest?

Znam algorytm na potęgowanie, który działa dla wykładnika zapisanego w systemie binarnym, szukałem jakiejś analogii, którą można by się posłużyć dla systemu trójkowego, jednak na razie nie znalazłem nic takiego.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 29 cze 2018, o 16:30 
Użytkownik
Avatar użytkownika

Posty: 6336
Ponieważ ilość mnożeń nie zależy od systemu liczbowego w jakim jest podany wykładnik to przejdź na system decymalny lub binarny i wskaż liczbę mnożeń.

W dziesiętnym x^{50} wymaga siedmiu mnożeń:
x \cdot x=x^2\\
x^2 \cdot x^2=x^4\\
x^4 \cdot x^4=x^8\\
x^8 \cdot x^8=x^{16}\\
x^{16} \cdot x^{16}=x^{32}\\
x^{32} \cdot x^{16}=x^{48}\\
x^{48} \cdot x^{2}=x^{50}

W binarnym 1212_3=50_{10}=110010_2 ilość mnożeń ustal wg swojego algorytmu.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Algorytmy][C++] Warcaby czlowiek-komputer  dav123  8
 [Algorytmy] Kolejka dwustronna w tablicy  elbargetni  2
 [Algorytmy] NWD, NWW wielu liczb - zadanie 2  panczo12d  6
 Algorytmy i struktury danych - zadanie 2  fro  4
 [Algorytmy] Podział graniastosłupów w kierunku pionowym  xyz_zyx  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl