ˇ P. J. Vejvanovske ´ho Krome ˇr ˇ´ıˇ Konzervator z Predispozice pro v´ yuku IKT (2015/2016)
Z´akladn´ı algoritmy pro poˇc´ıt´an´ı s cel´ymi a racion´aln´ımi ˇc´ısly
ˇ ska Adam Siˇ
1
Sˇ c´ıt´ an´ı dvou kladn´ ych cel´ ych ˇ c´ısel
Probl´em: Jsou d´ ana dvˇe kladn´a cel´a ˇc´ısla a ≥ b v soustavˇe o z´akladu z, napˇr.: a = 853, b = 183 a z = 10. M´ame za u ´kol nal´ezt souˇcet ˇc´ısel c = a + b. ˇ sen´ı pˇr´ıkladu 853 + 183: Reˇ ˇ C´ısla nap´ıˇseme pod sebe zarovnan´a zprava (totoˇzn´e ˇr´ady ˇc´ıseln´e soustavy v obou ˇc´ıslech mus´ı b´ yt pod sebou). Postupujeme zprava, vezmeme dvˇe ˇc´ıslice (cifry) zapsan´e pod sebou a vˇzdy tzv. zkontrolujeme palec (tj. jestli si z pˇredchoz´ıho kroku neneseme z´ aklad soustavy – des´ıtku1 ). Pokud prov´ad´ıme prvn´ı krok palec pochopitelnˇe nedrˇz´ıme. V naˇsem pˇr´ıpadˇe 3 + 3 = 6. Meziv´ ysledek nepˇresahuje z´ aklad soustavy 6 < 10, takˇze pod pr´avˇe sˇc´ıtan´e cifry nap´ıˇseme 6 a palec pro pˇr´ıˇstˇe nedrˇz´ıme. 853 183 --6 V dalˇs´ım kroku tedy palec nedrˇz´ıme, opˇet seˇcteme pouze dvˇe cifry 5 + 8 = 13. Meziv´ ysledek pˇresahuje z´ aklad soustavy 13 ≥ 10, takˇze do pˇr´ıˇst´ıho kroku drˇz´ıme palec a pod pr´ avˇe sˇc´ıtan´e cifry zap´ıˇseme 13 − 10 = 3. 1 Pokud sˇ c´ıt´ ame dvˇ e ˇ c´ısla staˇ c´ı (bin´ arn´ı) palec, ale pokud sˇ c´ıt´ ame v´ıce ˇ c´ısel souˇ casnˇ e, m˚ uˇ zeme z pˇredchoz´ıho kroku pˇren´ aˇset i n´ asobky z´ akladu soustavy. Nejv´ıce ale tolik, kolik pˇriˇ c´ıt´ ame ˇ c´ısel k prvn´ımu.
1
853 183 --36 (palec) V n´ asleduj´ıc´ım kroku poprv´e drˇz´ıme palec, k obˇema cifr´am tud´ıˇz pˇriˇc´ıt´ame jeˇstˇe jedniˇcku, tj. 8 + 1 + palec = 8 + 1 + 1 = 10. Znovu plat´ı 10 ≥ 10, proto opˇet drˇz´ıme palec a pod aktu´ aln´ı cifry p´ıˇseme 10 − 10 = 0. 853 183 --036 (palec) V zad´ an´ı uˇz nem´ ame cifry, kter´e bychom mohli seˇc´ıst. Z pˇredchoz´ıho kroku ale drˇz´ıme palec. P´ıˇseme tedy 1 a v´ ypoˇcet je hotov´ y. 853 183 --1036 Obecn´ y postup sˇc´ıt´ an´ı: Zadan´ a ˇc´ısla a < b v soustavˇe o z´akladu z mohou obecnˇe vypadat n´asledovnˇe: a = A(n − 1)A(n − 2)...A(0) a b = B(m − 1)B(m − 2)...B(0), kde n ≥ m je poˇcet cifer jednotliv´ ych ˇc´ısel. Velk´a p´ısmena s indexem znaˇc´ı jednotliv´e cifry, napˇr. A(2) je poˇcet stovek (tj. 102 ) obsaˇzen´ ych v ˇc´ısle a, B(0) poˇcet jednotek (tj. 100 ) v ˇc´ısle b. Je vhodn´e si uvˇedomit ˇze libovoln´a cifra A(i) nebo B(i) je vˇzdy ˇc´ıslo z v´ yˇctu 0, 1, ..., z − 1. Pokud cifra B(i) neexistuje, bereme za jej´ı hodnotu nulu: B(i) = 02 . V algoritmu jeˇstˇe poˇc´ıt´ame s hodnotou P ∈ 0, 1, kter´a zaznamen´av´a drˇzen´ı palce. Na zaˇc´ atku v´ ypoˇctu je P = 0. N´ asleduje algoritmus: i=0 % P=0 % dokud i <= n opakuj: seˇ cti x = A(i) + B(i) + P pokud je v´ ysledek x vˇ etˇ s´ ı nebo roven z´ aklada drˇ z palec P=1 a zapiˇ s C(i) = x - z pokud je v´ ysledek x menˇ s´ ı neˇ z z zapiˇ s C(i) = x a nedrˇ z palec P=0 i=i+1 % zapiˇ s C(i) = P
poˇ c´ ıtadlo krok˚ u palec
soustavy z
dalˇ s´ ı krok
V´ ysledek sˇc´ıt´ an´ı je ˇc´ıslo c = C(n + 1)C(n)C(n − 1)...C( 1)C(0). S moˇznou poˇc´ ateˇcn´ı nulou pokud C(n + 1) 6= 1. 2 To m˚ uˇ ze nastat, pokud je ˇ c´ıslo a ˇr´ adovˇ e vyˇsˇs´ı neˇ z b, tj. obsahuje v´ıc cifer n > m a n≥i>m
2
2
Odˇ c´ıt´ an´ı dvou kladn´ ych ˇ c´ısel
Probl´em: Jsou d´ ana dvˇe kladn´a cel´a ˇc´ısla a, b v soustavˇe o z´akladu z, napˇr.: a = 183, b = 853 a z = 10. M´ame za u ´kol nal´ezt rozd´ıl tˇechto ˇc´ısel c = a − b. ˇ sen´ı, kter´e zˇrejmˇe vych´ Reˇ az´ı z postupu v pˇredchoz´ı ˇc´asti textu a prakticky vyˇzaduje pouze revizi z´ akladn´ıho kroku A(i) + B(i) + P , je ponech´ano ˇcten´aˇri. Oba postupy (sˇc´ıt´ an´ı a odˇc´ıt´an´ı kladn´ ych ˇc´ısel) lze pochopitelnˇe zobecnit na postup pro sˇc´ıt´ an´ı dvou cel´ ych ˇc´ısel.
3
N´ asoben´ı dvou kladn´ ych cel´ ych ˇ c´ısel
Probl´em: Jsou d´ ana dvˇe kladn´a cel´a ˇc´ısla a, b, napˇr.: a = 1024, b = 1024. M´ame za u ´kol nal´ezt souˇcin tˇechto ˇc´ısel c = a · b. ˇ sen´ı pˇr´ıkladu 1024 · 1024: Reˇ N´ asoben´ı ˇc´ısel pod sebou je zaloˇzeno na t´eto u ´vaze: 1024 · 1024 = 1024 · 1000 + 1024 · 20 + 1024 · 4. Pˇri v´ ypoˇctu postupujeme zprava a bereme jednotliv´e cifry druh´eho ˇc´ısla, kter´ ymi vˇzdy vyn´asob´ıme cel´e prvn´ı ˇc´ıslo. V prvn´ım kroku tedy dost´ av´ame 4 · 1024 = 4096. V druh´em kroku n´asob´ıme 20 · 1024 = 20480, prakticky ale n´asob´ıme ˇc´ıslem 2 a posledn´ı nulu meziv´ ysledku nep´ıˇseme, meziv´ ysledek ale vhodnˇe zarovn´ame. Tˇret´ı krok je trivi´aln´ı s meziv´ ysledkem 0, posledn´ı podobnˇe: pouze op´ıˇseme a vhodnˇe zarovn´ame ˇc´ıslo a. Vˇsechna takto zarovnan´ a ˇc´ısla nakonec seˇcteme. 1024 . 1024 ------4096 2048 0 1024 ------1048576 Obecn´ y postup v tomto pˇr´ıpadˇe neuv´ad´ıme. Algoritmizace tohoto probl´emu uˇz nen´ı u ´plnˇe trivi´ aln´ı3 . Je vhodn´e dodat, ˇze je tento postup nez´avisl´ y na volbˇe ˇc´ıseln´e soustavy. 3 viz
algoritmus v jazyce Pascal zde: –odkaz– nasobeni.pas
3
4
Dˇ elen´ı dvou kladn´ ych cel´ ych ˇ c´ısel s desetin´ ym rozvojem
Probl´em: Jsou d´ ana dvˇe kladn´a cel´a ˇc´ısla a, b, napˇr.: a = 50, b = 6. M´ame za u ´kol nal´ezt pod´ıl tˇechto ˇc´ısel c = a : b vyj´adˇren´ y jako desetinn´e ˇc´ıslo (s moˇzn´ ym periodick´ ym rozvojem). ˇ sen´ı pˇr´ıkladu 50 : 6: Reˇ Z´ akladn´ım krokem postupu dˇelen´ı je urˇcen´ı v´ ysledku dˇelen´ı se zbytkem. Bˇeˇznˇe se pt´ ame: Kolikr´ at se 6 vejde do 50? Odpovˇed’ je 7-kr´at, a jelikoˇz 6 · 7 = 48, do pades´ ati zb´ yv´ a 2. V´ıme tedy, ˇze v´ ysledek bude zaˇc´ınat ˇc´ıslem 7. 50 : 6 = 7 -48 --zb. 2 Abychom mohli poˇc´ıtat d´ al je potˇreba si uvˇedomit, ˇze ˇc´ıslo 50 = 50, 00000... a ˇze v´ ysledek napˇr´ıklad 50000 : 6 se od v´ ysledku 50 : 6 bude liˇsit pouze um´ıstˇen´ım desetinn´e ˇc´ arky. K urˇcen´ı dalˇs´ı cifry desetin´eho rozvoje proto poˇc´ıt´ame ˇ 20 : 6, meziv´ ysledek uˇz ale p´ıˇseme za desetinou ˇc´arku. Sestka se do dvaceti vejde 3-kr´ at a zb´ yv´ a opˇet 2. 50 : 6 = 7,3 -48 --20 -18 --2 Je zˇrejm´e, ˇze v´ ypoˇcet se od n´ asleduj´ıc´ıho kroku bude neust´ale opakovat (podruh´e jsme z´ıskali zbytek 2). V´ ysledn´e ˇc´ıslo tedy bude m´ıt neukonˇcen´ y periodick´ y rozvoj. __ 50 : 6 = 7,33 -48 --20 -18 --20 -18 --2 atd... 4
Dalˇs´ı pˇr´ıklady: 98 : 8 = 12,25 -8 -18 -16 --20 -16 --40 -40 --0 (zbytek nula znamen´ a konec v´ ypoˇctu, ˇc´ıslo m´a ukonˇcen´ y rozvoj) ______ 1 : 7 = 0,142857 -0 -10 -7 -30 -28 --20 -14 --60 -56 --40 -35 --50 -49 --1 (zbytek 1 vyˇsel i v prvn´ım kroku, proto je ˇc´ıslo nekoneˇcn´e periodick´e)
5
5
Sˇ c´ıt´ an´ı, odˇ c´ıt´ an´ı, n´ asoben´ı a dˇ elen´ı zlomk˚ u
Probl´em: Jsou d´ ana dvˇe racion´aln ˇc´ısla ab a dc . M´ame za u ´kol nal´ezt souˇcet, rozd´ıl, souˇcin a pod´ıl tˇechto ˇc´ısel opˇet vyj´adˇren´ y zlomkem. Sˇc´ıt´ an´ı a odˇc´ıt´ an´ı:
N´ asoben´ı a dˇelen´ı:
6
a c a·d±c·b ± = b d b·d a c a·c a d · = = : b d b·d b c
Poˇ c´ıt´ an´ı s mocninami a b
Probl´em: Je d´ ano jedno racion´aln´ı ˇc´ıslo n-tou mocninu ˇc´ısla ab . Mocnina:
a n b a −n
=
b
6
=
a cel´e ˇc´ıslo n. M´ame za u ´kol nal´ezt
an bn bn an
