aplikacja Matura google play app store

zadania z informatyki - Analiza algorytmów

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 4.
Wiązka zadań Silniowy system pozycyjny

Pojęcie silni dla liczb naturalnych większych od zera definiuje się następująco:

n! = 1·2·3 · ... · (n – 1) n

Silniowy system pozycyjny to pozycyjny sposób zapisu liczb naturalnych, w którym mnożniki dla kolejnych pozycji są definiowane przez silnie kolejnych liczb naturalnych, tzn.

(x)! = (xnxn1 xn2 ... x2x1)!

xn · n! + xn1 · (n – 1)! + ... + x2 · 2! + xx · 1!

W systemie silniowym współczynnik xi, który odpowiada mnożnikowi i!, spełnia zależność

0 ≤ xi ≤ i 

Zapis każdej liczby w silniowym systemie pozycyjnym jest jednoznaczny, tzn. każdą liczbę naturalną można zapisać tylko w jeden sposób i każdą liczbę naturalną można zapisać dokładnie w jeden sposób.

Uwaga: W poniższych zadaniach będziemy mieć do czynienia tylko z takimi liczbami, dla których współczynniki xi spełniają zależność 0 ≤ xi ≤ 9.

Przykład

(1220)! = 1 · 4! + 2 · 3! + 2 · 2! + 0 · 1! = 

24 + 12 + 4 + 0 = 40.

Zadanie 4.1.
Uzupełnij tabelę. Zamień zapis liczby w systemie silniowym na jej zapis w systemie dziesiętnym.

liczba w systemie silniowym

liczba w systemie dziesiętnym

(310)!


(2011)!


(54211)!


Zadanie 4.2.
Podaj zapis w systemie silniowym największej liczby, jaką można w tym systemie zapisać na pięciu pozycjach.
Zadanie 4.3.
Zamiana zapisu liczby w systemie dziesiętnym na zapis w systemie silniowym może przebiegać według następującego schematu: Szukamy największej liczby k, której silnia nie przekracza liczby x. Pierwsza jej cyfra to wynik dzielenia całkowitego x przez k!. Kolejne cyfry zapisu silniowego (zaczynając od cyfr najbardziej znaczących) otrzymujemy przez wyznaczanie wyników dzielenia liczby x przez (k – 1)!, (k –2)!, ..., 2!, 1!. Po wyznaczeniu cyfry xi , odpowiadającej współczynnikowi i!, zmniejszamy wartość x o liczbę odpowiadającą cyfrze xi , czyli xi ⋅ i!. Oznacza to, że x przyjmuje wartość x mod k!.

Przykład

Liczba dziesiętna 1548 w zapisie silniowym: (204200)!

Wykonaj zamianę liczby 5489 z systemu dziesiętnego na silniowy zgodnie z opisanym powyżej algorytmem. Uzupełnij poniższą tabelkę oraz podaj zapis silniowy liczby 5489.

x

k

x div k!

x mod k!

5489





























Liczba dziesiętna 5489 w zapisie silniowym: ........................................
Zadanie 4.4.
Poniżej przedstawiono algorytm z lukami, który zamienia zapis liczb z systemu dziesiętnego na system silniowy. Uzupełnij luki w tym algorytmie.

Specyfikacja

Dane:
x — liczba całkowita dodatnia zapisana w systemie dziesiętnym,
Wynik:
s — napis reprezentujący liczbę x zapisaną w systemie silniowym.

silnia ← 1
k ←1
dopóki (silnia < x) wykonuj
k ← k + 1
silnia← silnia* k
jeżeli ..........................................
silnia ← silnia div k
k ← k – 1
s ←” ”
dopóki (k>0) wykonuj
cyfra ← ............................................
s ← s ◦ tekst (cyfra)
x ← ..................................................
silnia ← ...........................................
k ←k – 1

Uwaga
tekst (x) oznacza funkcję zamieniającą liczbę x na jej zapis tekstowy
” ” oznacza napis pusty
u ◦ v oznacza sklejenie dwóch napisów: u oraz v

Poprzednia strona Następna strona

źródło: CKE
Polityka Prywatności