20319 Str124

Odpowiedzi

do ćwiczeń

1.1

i. (112111)3.

²- (²⁶° ii)

3. 10001100101; 1101 IT

1010

1011

WE - LIKJE + IT - lu-

4.    MPJNS; LIKE ■ —- (inaczej mówiąc, JQVXHJ bimy to). ^WE

5.    (a)10,101101111110000; (b) C,SR0.

6.    Jeśli b^r — 1 jest wielokrotnością d, to ten ułamek może być zapisany w postaci a/(b* — 1), gdzie a jest liczbą mającą co najwyżej f cyfr. Wtedy skorzystaj ze wzoru na sumę ciągu geometrycznego o pierwszym wyrazie a - b~^f i ilorazie bNa odwrót, jeśli mamy dane rozwinięcie okresowe czyste liczby x, o okresie długości f, to liczba b^fx różni się odro liczbę całkowitą /^cyfrową a, co oznacza, że x = al(b^f — 1).

7.    (a) (BAD)_l6; (b) żadne dzielenie nie jest potrzebne: na przykład, aby zamienić podstawę z dwójkowej na szesnastkową, oddzielamy po cztery cyfry, począwszy od prawej strony i każdą taką czwórkę cyfr traktujemy jak cyfrę szesnastkową (lub zastępujemy jednym z symboli 0-9, A-F).

8.    (1) Popatrz na górny i dolny bit oraz na to, czy jest przeniesienie; (2) jeśli oba bity są takie same i nie ma przeniesienia lub jeśli górny bit jest równy 1, dolny bit jest równy 0 i jest przeniesienie, to zapisz 0 i przejdź dalej; (3) jeśli górny bit jest równy 1, dolny bit jest równy 0 i nie ma przeniesienia, to zapisz 1 i przejdź dalej; (4) jeśli górny bit jest równy 0, dolny bit jest równy 1 i jest przeniesienie, to zapisz 0, zaznacz przeniesienie w następnej kolumnie i przejdź dalej; (5) jeśli oba bity są równe i jest przeniesienie lub jeśli górny bit jest równy 0, dolny bit jest równy 1 i nie ma przeniesienia, to zapisz 1, zaznacz przeniesienie w następnej kolumnie i przejdź dalej.

. (a) Potrzebujemy n — 1 mnożeń; za każdym razem iloczyn częściowy 3^J ma co najwyżej 0(ń) cyfr, a 3 ma dwie cyfry, zatem wykonujemy 0(ń) operacji na bitach; łącznie jest ich 0(n²).

(b) Tu iloczyn częściowy ma 0(n log n) cyfr, zatem każde mnożenie wymaga 0(n log^z/i) operacji na bitach; łącznie jest ich 0(n² log² ń).

10. 0(n²log²w).

U. (a) Ć7(nIog²/i); (b) 0(\og²n).

12.    0(rsn(\og²m + logn)).

13.    (a) Iloczyn 0(n/logn) liczb mających po 0(Iogn) cyfr ma

0(n/logn) • 0(logn) = 0(ń) cyfr;

(b) 0(nlogn); (c) 0(n²).

14.    (a) 0(7«log²w); (b) 0(sfn logn).

15.    0(mlogn).

16.    Przypuśćmy, że liczba n ma HI bitów. Jako pierwsze przybliżenie m = [yjn] weźmy liczbę złożoną z jedynki i [fc/2] zer. Znajdujemy cyfry m, występujące po tej jedynce, od lewej do prawej, za każdym razem próbując zmienić zero na jedynkę; jeśli kwadrat powstałej w ten sposób liczby m jest większy od «, to przywracamy cyfrę zero.

1.2

1.    (b) Prosty kontrprzykład: b= -a.

2.    16 dzielników: 1, 3, 5, 7, 9,15,21,27, 35,45,63,105, 135,189, 315, 945.

3.    (a) Jeśli a|n, to niech n = ab i wtedy a*-»ó.

(b)    Dla danej liczby n = ab, gdzie O 6, niech s = (a + b)j2 i t = (a- b)l2. Na odwrót, jeśli n = j² - /², to biorąc a = s +1 i ó =.? -1, otrzymujemy przyporządkowanie odwrotne.

(c)    473² - 472², 159² - 156², 97² - 92², 71² - 64², 57² - 48², 39² - 24², 33² - 12², 31²-4².

4. (b) 100! = 2⁹⁷ • 3⁴⁸ • 5²⁴ • 7¹⁶ • ll⁹ • 13⁷ • 17⁵ • 19⁵ • 23* • 29³ •

31³ • 37² • 41² • 43² • 47² ■ 53 • 59 • 61 • 67 • 71 • 73 ■ 79 • 83 • 89 • 97.

(c) Oto wzór: (n - S_p(n))ftp -1). Aby go dowieść, zapiszmy liczbę n w postaci n = d_k__lp^k~¹ +... + d_{p + d₀ i zauważmy, że dla każdego j: [n/p^J] as d_k^_ip^k^~ⁱ +... + d_]+lp + dj. Wtedy korzystamy ze wzoru z punktu (a).

6. (a) 1 = 11- 19-8*26; (b) 17= 1 • 187-5 • 34; (c) 1 =205-160 + - 39 • 841; (d) 13 = 65 - 2171 - 54 - 2613.

'* Na przykład, oto porównanie między dwiema metodami w przypadku punktu (d):

2613 = 2171 +442 2171 =4 - 442 + 403 442 = 403 + 39 403 = 10-39 + 13 39 = 3 • 13.

2613 = 2171 +442 2171 =5-442- 39 442= 11-39+ 13 39 = 3-13.