Matematyka dyskretna 2004 02 Arytmetyka

[ Pobierz całość w formacie PDF ]

w postaci dwójkowej i ósemkowej.
7. Jak liczby 4, 20, -4, -20 będą reprezentowane w komputerze jako stałe typu inte-
ger (byte, word)?
8. Liczby $B1, $FF przedstaw w postaci dziesiętnej, dwójkowej i ósemkowej.
1.15. Problemy 19
9. Liczby (80)10, (120)10 przedstaw w postaci trójkowej.
10. Liczby (10001101)2, (100101)2, przedstaw w postaci: dziesiętnej, szesnastkowej i
ósemkowej.
11. Liczby (1023)8, (713)8 przedstaw w postaci dwójkowej i dziesiętnej.
12. Ułamki (0.5625)10, (0.140625)10 przedstaw w postaci dwójkowej.
13. Ułamki (0.1101)2, (0.01101)2, (0.0011)2 przedstaw w postaci dziesiętnej.
14. Opisz algorytm zamiany ułamka z postaci dziesiętnej na postać dwójkową.
15. Ile maksymalnie pytań z odpowiedziami TAK/NIE trzeba zadać, aby odgadnąć licz-
bę: a) z przedziału od 0 do 100 000 b) z przedziału od 0 do 1 000 000?
16. Zastosuj algorytm" " pierwiastków do znalezienia następujących pier-
wyznaczania
" "
2 2 3 4
wiastków: 256, 1000, 512, 256.
17. Sprawdz, czy liczby 111, 1111 są potęgami liczb całkowitych.
1.15 Problemy
1.15.1 Uzupełnieniowy zapis liczb ujemnych
Aby całkowitą liczbę ujemną x z przedziału od -32768 do -1 przedstawić w postaci
uzupełnieniowej na dwóch bajtach:
" zapisz wartość bezwzględną |x| w postaci dwójkowej na szesnastu bitach.Jeżeli
zapis jest krótszy niż szesnaście bitów, uzupełnij go na początku zerami.
" Zamień wszystkie szesnaście bitów: 0 na 1, a 1 na 0,
" Dodaj 1.
Wypróbuj ten sposób na kilku liczbach. Udowodnij, że działa on prawidłowo.
1.15.2 Liczby w postaci ósemkowei i szesnastkowej w języku C
Jak w języku C można zapisać liczby (stałe) w systemie ósemkowym lub szesnastkowym.
Jak w C zadać format, aby liczba całkowita została wydrukowana w systemie ósemko-
wym lub szesnastkowym.
1.15.3 Sumy potęg dwójki
Udowodnij, że jeżeli liczby a1, ... ,ak są różnymi potęgami dwójki, to dla każdego pod-
zbioru I �" {1, 2, . . . , k} suma
ai
i"I
jest inna. Pokaż, że tak nie musi być w przypadku dowolnego ciągu różnych liczb.
20 Rozdział 1. Arytmetyka
1.15.4 Waga
Wyobrazmy sobie wagę szalkową. Na jednej szalce, lewej, kładziemy jakiś przedmiot do
zważenia, a następnie na obu szalkach kładziemy odważniki. Jeżeli waga jest w równowa-
dze, to ważony przedmiot ma wagę równą sumie (nominałów) odważników położonych
na prawej szalce minus suma odważników położonych na lewej szalce, obok ważonego
przedmiotu. Na przykład, jeżeli na prawej szalce leżą odważniki 2 i 20 gramowe, a na
lewej odważniki 4 i 5 gramowe, to przedmiot waży 13 = (20 + 2) - (5 + 4) gramów.
Interesujące nas pytanie brzmi: jakie powinny być nominały poszczególnych odważ-
ników, aby można było zważyć każdy ciężar o wadze od 1 do N, przy jak najmniejszej
liczbie odważników. Zakładamy, że ważymy tylko przedmioty o wagach będących dodat-
nimi liczbami naturalnymi.
Pokaż, że
3k-1
(1) Za pomocą k odważników można zważyc co najwyżej różnych ciężarów.
2
(2) Jeżeli nominały odważników są kolejnymi potęgami trójki, to znaczy ci = 3i dla
0 d" i d" k - 1, to za ich pomocą można zważyć każdy ciężar o nominale od 1 do
3k-1
.
2
(3) Jak należy ułożyć na szalkach odważniki o nominałach 1, 3, 9, 27, aby odważyc
ciężar: a) 35, b) 29?
(4) Ile potrzeba odważników, aby zważyć każdy ciężar a) od 1 do 100, b) od 1 do 1000?
(5) Jak należy ułożyć na szalkach odważniki o nominałach będących potęgami trójki
aby odważyc ciężar: a) 50, b) 200, c) 500?
Wskazówki:
(1) Ponieważ każdy odważnik może się znajdować na prawej lub lewej szalce, lub na
stole, to mamy 3k różnych położeń odważników. Wśród tych położeń jest takie, gdzie
wszystkie odważniki leżą na stole (wtedy ważymy zerowy ciężar). Ponadto jeżeli od-
ważniki leżą na szalkach i odważają ciężar W , to zamieniwszy położenia odważników
na szalkach (odważniki z lewej przekładamy na prawą szalkę, i na odwrót), będziemy
odważać ciężar -W .
(2) Rozłożenie odważników przy ważeniu ciężaru W odpowiada przedstawieniu W w
postaci
k-1
W = di3i, (1.5)
i=0
gdzie di " {-1, 0, 1}. Aby przedstawić ciężar W w postaci (1.5), najpierw przedstawia-
3k-1 3k-1
my liczbę W + w systemie trójkowym: W + = (ek-1 . . . e1e0)3, a następnie
2 2
od każdej cyfry odejmujemy jedynkę: di = ei - 1. [ Pobierz całość w formacie PDF ]