AK1-4-09-Dzielenie.pdf

(518 KB) Pobierz
Microsoft Word - AK1-4-09-Dzielenie.doc
Dzielenie
Dzielenie pozycyjne
dzielenie całkowite : dzielna X ( dividend ), dzielnik D ¹ 0 ( divisor )
Iloraz Q ( quotient ) i reszta R ( remainder ) z dzielenia to liczby takie, e
X = Q × D + R, |R| < |D|
• s 2 rozwi zania ( Q 1 ,R 1 ) oraz ( Q 2 ,R 2 ) takie, e X – R i = Q i × D , przy tym
|R 1 –R 2 | = |D| , –|D|< R 1 , R 2 < |D| oraz |Q 1 –Q 2 | = 1
X × R > 0 – dzielenie znakowane ( signed division ) – znak reszty = znak dzielnej
R > 0 – dzielenie modularne ( modulus division ) – znak reszty dodatni
W systemie stałobazowym (pozycyjnym) o podstawie B i ze zbiorem cyfr D,
iloraz X / D mo na obliczy z dokładno ci nie gorsz ni B –r jako:
X
@
Q
=
q
q
− ∑
q
=
s
q
B
X
−
Q
<
B
r
q
Î
D
s
s
−
r
B
i
i
D
D
i
=
−
r
© Janusz Biernat , AK1-4-09-Dzielenie.doc, 23 wrze
nia 2009
DIV– 1
i
−
321134382.060.png 321134382.071.png 321134382.082.png 321134382.093.png 321134382.001.png 321134382.011.png
Dzielenie
Przybli enia ilorazu w systemie naturalnym (1)
£ ,
okre la pozycj s i warto pierwszej cyfry ilorazu q s Î{0, 1, 2, … , B– 1} i reszt
Q
=
q
B
s
takie, e
q
B
s
D
X
<
( +
q
1
B
D
s
,
s
s
s
0
£
R
=
X
−
q
B <
s
D
B
s
D
1
s
Dokładniejsze przybli enie to
{
q
,
q
,...,
0
=
Q
=
Q
+
q
B
s
−
1
takie, e
s
s
−
1
B
s
,
2
s
,
s
−
1
q
B
s
−
1
D
£
R
=
X
−
Q
D
<
(
q
+
1
B
s
−
1
D
,
s
−
1
1
s
,
s
−
1
0
£
R
=
R
−
q
B
s
−
1
D
<
B
s
−
1
D
2
1
s
−
1
Kolejnymi przybli eniami ilorazu s
Q
=
Q
+
q
B
s
−
i
takie, e
s
,
i
+
1
s
,
i
s
−
i
q
B
s
−
i
D
£
R
=
X
−
Q
D
<
(
q
+
1
B
s
−
i
D
,
s
−
i
i
s
,
i
s
−
i
0
£
R
=
R
−
q
B
s
−
i
D
<
B
s
−
i
D
i
+
1
i
s
−
i
co po skalowaniu reszty (
r
i R
=
B ) prowadzi do nierówno ci parametrycznej
D
i
−
s
−
i
0
£
r
i
+ B
1
=
r
i
−
q
s
−
i
D
<
© Janusz Biernat , AK1-4-09-Dzielenie.doc, 23 wrze
nia 2009
DIV– 2
Pierwsze przybli enie ilorazu
s
321134382.012.png 321134382.013.png 321134382.014.png 321134382.015.png 321134382.016.png
Dzielenie
Zbie no procedury dzielenia
W systemie stałobazowym kolejne przybli enie ilorazu Q s,i +1 jest dokładniejsze
od poprzedniego, je li spełniony jest warunek
X
−
Q
<
X
−
Q
,
D
s
i
+
D
s
i
St d wynika, e to kolejna reszta (znormalizowana) musi spełnia nierówno
r
p
+
=
B
r
p
−
q
s
−
p
D
<
D
,
Je li warunek ten nie jest spełniony, czyli D
r p
+
³
, to kolejna nierówno
r
(
p
+
2
)
=
B
r
(
p
+
1
−
q
s
−
(
p
+
1
D
<
D
,
nie ma rozwi zania w zbiorze dozwolonych warto ci cyfr (
q ).
<
B
Na przykład przy dodatnich r # oraz D , je li
r p
+
=
D
+
D
, to
r
p
+
2
)
=
B
(
D
+
D
−
q
s
−
(
p
+
1
D
=
(
B
−
q
s
−
(
p
+
1
)
D
+
BD
³
D
+
BD
>
r
(
p
+
a wi c kolejne reszt s nie tylko wi ksze od dzielnika ale te coraz wi ksze.
© Janusz Biernat , AK1-4-09-Dzielenie.doc, 23 wrze
nia 2009
DIV– 3
)
(
1
321134382.017.png 321134382.018.png 321134382.019.png 321134382.020.png 321134382.021.png 321134382.022.png 321134382.023.png 321134382.024.png 321134382.025.png 321134382.026.png 321134382.027.png 321134382.028.png 321134382.029.png 321134382.030.png 321134382.031.png 321134382.032.png 321134382.033.png 321134382.034.png 321134382.035.png
Dzielenie
Procedura dzielenia sekwencyjnego w systemie naturalnym
Warunek zbie no ci procedury – wybór takiej cyfry q # , aby reszta była < D
•
r
<
D
⇒
$
0
£
q
s
−
i
<
B 0
)
:
£
B
r
i
−
q
s
−
i
D
<
D
r
³
D
⇒
"
(
0
£
q
s
−
i
<
B :
)
B
r
i
−
q
s
−
i
D
³
D
Graficzny schemat dzielenia
B= 4
r i +1
q s–i = 0
q s–i = 3
D
4 r i
4 r i +1
4 D
2 D
(0,0)
(0,0)
2 D
4 D
q s–i = 3
q s–i = 0
r i +2
r i < D
0 £ q < B
(zbie ne)
r i ³ D
? q =B–1
rozbie ne
r i +2 > r i +1
© Janusz Biernat , AK1-4-09-Dzielenie.doc, 23 wrze
nia 2009
DIV– 4
( ,
w przeciwnym razie wszystkie kolejne reszty b d coraz wi ksze
•
i
i
321134382.036.png 321134382.037.png 321134382.038.png 321134382.039.png 321134382.040.png 321134382.041.png 321134382.042.png 321134382.043.png 321134382.044.png 321134382.045.png 321134382.046.png 321134382.047.png 321134382.048.png 321134382.049.png 321134382.050.png 321134382.051.png 321134382.052.png 321134382.053.png 321134382.054.png 321134382.055.png 321134382.056.png
Dzielenie
Schemat dzielenia w systemie dwójkowym
a)
r i +1
b)
r i +1
D
D
q s–i = 0
q s – i = 1
q s–i = 0
q s–i = 1
(2)
(1)
...(2)
(2)
(1)
...(2)
2 r i
2 r i
a) wyznaczanie cyfry ilorazu (1) i reszty cz ciowej (2), b) skalowanie reszty (3)
(0,0)
D
2 D
(0,0)
(3)
D
(3)
2 D
B= 2
r i +1
r i +1
q s–i = 0
q s–i = 1
D
D
2 r i
2 r i +1 2 D
D
(0,0)
(0,0)
D
2 D
D
r i < D
0 £ q £ 1
(zbie ne)
r i ³ D
q = 1 !
rozbie ne
q s–i = 1
q s–i = 0
r i +2 > r i +1
© Janusz Biernat , AK1-4-09-Dzielenie.doc, 23 wrze
nia 2009
DIV– 5
321134382.057.png 321134382.058.png 321134382.059.png 321134382.061.png 321134382.062.png 321134382.063.png 321134382.064.png 321134382.065.png 321134382.066.png 321134382.067.png 321134382.068.png 321134382.069.png 321134382.070.png 321134382.072.png 321134382.073.png 321134382.074.png 321134382.075.png 321134382.076.png 321134382.077.png 321134382.078.png 321134382.079.png 321134382.080.png 321134382.081.png 321134382.083.png 321134382.084.png 321134382.085.png 321134382.086.png 321134382.087.png 321134382.088.png 321134382.089.png 321134382.090.png 321134382.091.png 321134382.092.png 321134382.094.png 321134382.095.png 321134382.096.png 321134382.097.png 321134382.098.png 321134382.099.png 321134382.100.png 321134382.101.png 321134382.102.png 321134382.103.png 321134382.002.png 321134382.003.png 321134382.004.png 321134382.005.png 321134382.006.png 321134382.007.png 321134382.008.png 321134382.009.png 321134382.010.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin