Matematyka dyskretna (tryb zaoczny) – cz. II
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu
1
1
>
p
{
}
1
,...,
2
,
1
,
0
−
=
p
Z
p
Z
b
a
∈
,
p
Z
p
a
∈
mod
p
p
p
a
mod
2
2 +
=
a div p
−
=
p
a
p
a
p
a mod
2
mod
5
−
1
2
2
5
2
5
2
5
=
⋅
−
=
−
4
mod
20
0
20
20
4
20
4
20
=
−
=
−
3
mod
5
−
( )
1
2
3
5
3
5
3
5
=
−
⋅
−
−
=
−
−
−
(
)
p
c
a
c
p
a
c
⋅
⋅
=
⋅
mod
mod
p
c
a
c
p
c
a
c
p
c
a
c
p
a
p
c
a
c
p
a
p
a
c
⋅
⋅
=
⋅
⋅
⋅
⋅
−
⋅
=
⋅
⋅
−
⋅
=
⋅
⋅
mod
mod
(
)
(
)
4
2
2
3
3
11
2
3
11
3
11
2
3
mod
11
2
=
⋅
=
⋅
−
⋅
=
⋅
−
⋅
=
⋅
4
3
6
22
6
22
6
22
6
mod
22
=
⋅
−
=
⋅
−
=
p
Z
b
a
∈
,
(
)
p
b
a
b
p
a
mod
+
=
⋅
+
0
1
1
1
0
0
1
0
\ b
a
dodawanie
( )
p
b
a
b
p
a
mod
⋅
=
⋅
⋅
1
0
1
0
0
0
1
0
\ b
a
mno enie
2
=
p
4
=
p
{
}
3
,
2
,
1
,
0
4
=
Z
2
1
0
3
3
1
0
3
2
2
0
3
2
1
1
3
1
1
0
0
3
2
1
0
4
+
1
2
3
0
3
2
0
2
0
2
3
1
1
0
1
0
0
0
0
0
3
2
1
0
4
∗
(
)
(
) (
)
p
b
p
a
p
b
a
p
mod
mod
mod
+
=
+
Matematyka dyskretna (tryb zaoczny) – cz. II
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu
2
( )
(
) (
)
p
b
p
a
p
b
a
p
mod
mod
mod
∗
=
⋅
(
)
1
2
mod
6
5
=
+
(
)
(
) (
)
1
0
1
2
mod
6
2
mod
5
2
mod
6
5
2
2
=
+
=
+
=
+
(
)
(
)
2
3
3
4
mod
19
)
4
mod
11
(
4
mod
19
11
4
4
=
+
=
+
=
+
(
)
(
) (
)
1
3
3
4
mod
19
4
mod
11
4
mod
19
11
4
4
=
∗
=
∗
=
∗
--
Dzielenie liczb
Z
n
m
∈
,
(
)
0
≥
≥ n
m
m
k \ - liczba k jest podzielnikiem liczby m
ik
m
m
k
=
⇔
\
(
)
0
mod
≠
k
m
( )
m
k
m
k
\
\
−
{
}
m
k
m
k
k
n
m
NWD
\
,
\
:
max
)
,
(
=
m
m
NWD
=
)
0
,
(
)
12
,
30
(
NWD
...
17
13
11
7
5
3
2
30
0
0
0
0
1
1
1
⋅
⋅
⋅
⋅
⋅
⋅
⋅
=
{
}
i
i
i
i
n
m
P
n
m
NWD
,
min
)
,
(
1
∏
∞
=
=
...
11
7
5
3
2
12
0
0
0
1
1
⋅
⋅
⋅
⋅
⋅
=
{ }
{ }
{ }
6
3
2
3
3
2
)
12
,
30
(
0
,
1
min
1
,
1
min
2
,
1
min
=
⋅
=
⋅
⋅
=
NWD
)
,
( n
m
NWD
n
m
≥
0
≠
n
Wspólne dzielniki s takie same jak wspólne dzielniki
n
m
n
mod
,
var a, b : integer;
d : integer;
( )
n
m
NWD
a
,
=
a := m;
b := n;
repeat
(a, b) :=
(
)
b
a
b mod
,
r := a mod b;
until
(
)
0
=
b
z := b;
d := a;
b := r;
end;
)
20
,
63
(
NWD
0
1
0
1
2
1
2
3
2
3
20
3
20
63
modb
a
r
b
a
=
Algorytm ten wykonuje si max.
(
)
n
m
+
2
log
2
razy.
)
,
( n
m
NWD
Matematyka dyskretna (tryb zaoczny) – cz. II
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu
3
var a,b,g : integer
a := m;
b := n;
repeat
q := 20 i r b;
( )
b
a, :=
(
)
b
q
a
b
=
−
,
until
(
)
0
=
b
; d := 2;
0
5
0
10
2
9
10
10
30
2
13
40
15
120
3
40
135
2
2
−
−
−
−
−
−
+
b
q
qb
b
b
a
--
Algorytm Euklidesa
)
,
( n
m
AE
( )
n
m
NWD
d
.
=
n
t
Sm
a
⋅
=
m
a
= ;
2′
:= n; S := 1; S′ := 0; t := 0;
q
:= a div a′ ;
( ) (
)
a
q
a
a
′
∗
−
′
=
′
,
2
,
2
(
)
S
S ′
,
:=
(
)
S
q
S
S
′
∗
−
′,
( )
t
t ′
, :=
(
)
t
q
t
t
′
−
−
′,
until
(
)
0
=
′
a
;
d
:= a;
−
−
−
−
−
−
−
−
−
∗
−
′
′
+
−
′
3
27
10
0
5
2
27
10
7
0
2
5
10
1
10
7
3
5
1
10
15
0
7
3
1
10
2
15
40
1
3
1
0
15
3
40
135
2
2
t
q
t
t
t
a
q
q
a
( )
5
400
405
40
10
135
3
=
−
=
⋅
−
+
⋅
=
⋅
+
⋅
n
t
m
s
3
10
5
=
−
=
=
b
t
d
( )
( )
(
)
n
g
O
n
f
=
je eli istnieje
0
>
c
o tej własno ci, e
( )
( )
n
g
c
n
f
⋅
≤
dla dostatecznie
du ych warto ci n
( )
1
=
n
g
( ) ( )
1
O
n
f
=
istnieje pewne
0
>
c
takie, e
( )
c
n
f
≤
Matematyka dyskretna (tryb zaoczny) – cz. II
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu
4
( )
n
n
f
1
=
1
=
c
( )
1
5
+
= n
n
f
( )
2
n
n
g
=
1
=
c
2
2
1
5
n
n
n
≤
+
≤
−
-36
31
36
dla
6
=
n
--
( )
2
2
10
5
n
O
n
n
=
+
−
istnieje takie c, e
( )
2
n
c
n
f
⋅
≤
( )
2
2
2
2
2
10
5
10
5
10
5
n
n
n
n
n
n
n
n
f
+
+
≤
+
−
+
≤
+
−
=
b
a
b
a
+
≤
+
b
a
b
a
⋅
=
⋅
2
n
n
≤
1
2
≥
n
dla
1
≥
n
-- --
1.
...
...
1
3
2
3
4
<
<
<
<
<
<
<
n
n
n
n
n
wyka , e dowolne
( )
( )
( )
3
2
n
O
n
n
O
n
n
O
n
=
<
=
<
=
// ka dy wyraz jest
<
od tego po jego prawej
2.
1
≥
k
;
wyka , e
=
+
k
n
O
n
1
1
-- --
Własno ci
1)
( )
( )
(
)
n
g
O
n
f
=
oraz
7
.
=
= const
k
( )
( )
(
)
n
g
O
n
f
k
=
⋅
Istnieje takie c, e
( )
( )
n
g
c
n
f
⋅
≤
( )
( )
( )
( )
n
g
c
n
g
k
c
n
f
k
n
f
k
⋅
=
⋅
⋅
≤
⋅
=
⋅
2)
( )
( )
(
)
n
g
O
n
f
=
,
( )
( )
(
)
h
g
O
n
h
=
( ) ( )
( )
(
)
n
g
O
n
h
n
f
=
+
( ) ( )
( ) ( ) (
) ( )
n
g
c
c
n
h
n
f
n
h
n
f
⋅
+
≤
+
≤
+
1
2
c
( ) ( )
( ) ( )
(
)
n
b
n
a
O
n
h
n
f
⋅
=
⋅
( )
( )
(
)
n
g
O
n
f
=
oraz
( )
( )
( )
n
h
O
n
g
=
( )
( )
( )
n
h
O
n
f
=
( )
( )
n
g
c
n
f
⋅
≤
( )
( )
( )
( )
n
h
c
c
n
f
n
h
c
n
g
⋅
⋅
≤
⋅
≤
1
1
Wyszukiwarka
Podobne podstrony:
mat dys2
Wyklad2 mat
Mat 10 Ceramika
Mat dla stud 2
Wyklad7 mat
mat skale pomiarowe
logika mat
Magn mat
7Komunikacja org mat
mat bud 006 (Kopiowanie) (Kopiowanie)
Materialy do seminarium inz mat 09 10 czesc III
mat bud 102 (Kopiowanie) (Kopiowanie)
mat 2013 k11
Mat 3
MB2 mat pom 1 id 289843 Nieznany
więcej podobnych podstron