Przykład: znajdowanie liczby najmniejszej.
Wskazać najmniejszą spośród trzech różnych liczb: a, b, c.
Inne sformułowanie zadania:
Mając trzy różna liczby a,b,c, wyznaczyć liczbę m , tak aby
m =a lub m = b lub m = c, przy czym m
≤ a , m ≤ b , m ≤ c.
Możliwe sytuacje:
1. a<b<c
2. a<c<b
3. b<a<c
4. b<c<a
5. c<a<b
6. c<b<a
Maszyna różnicowa Charlesa Babbage’a
Kolejne kwadraty Kolejne liczby nieparzyste
1
2
= 0 + 1
←⎯⎯⎯ 1
2
2
= 1 + 3
←⎯⎯⎯ 3 = 1 + 2
3
2
= 4 + 5
←⎯⎯⎯ 5 = 3 + 2
4
2
= 9 + 7
←⎯⎯⎯ 7 = 5 + 2
Aby policzyć kwadrat kolejnej liczby należy:
1. Ustawić liczby 0, 1 i 2 jako wartości początkowe
2. Wykonać dwa dodawania
• Dodać 2 dla uzyskania następnej liczby nieparzystej
• Dodać wynik do poprzedniego kwadratu
Systemy liczenia:
System dziesiętny:
- cyfry: 0,1,2,3,4,5,6,7,8,9
- postać liczby: C
n
C
n-1
C
n-2
. . . C
1
C
0
- wartość liczby:
C
n
*10
n
+C
n-1
*10
n-1
+C
n-2
*10
n-2
+ ...+C
1
*10
1
+C
0
*10
0
System dwójkowy (binarny):
- cyfry: 0,1
- postać liczby: B
n
B
n-1
B
n-2
. . . B
1
B
0
- wartość liczby:
B
n
*2
n
+B
n-1
*2
n-1
+B
n-2
*2
n-2
+ ...+B
1
*2
1
+B
0
*2
0
Postać binarna liczby dziesiętnej:
(13)
10
= 8+4+1= 1*2
3
+1*2
2
+1*2
0
= 1*2
3
+1*2
2
+0*2
1
+1*2
0
(13)
2
= 1101
(191)
10
191:2=95 r 1
↑ (191)
2
= 10111111
95:2=47 r 1
⏐
47:2=23 r 1
⏐ Sumowanie
23:2=11 r 1
⏐ dziesiętne: binarne:
11:2=5 r 1
⏐ 7 111
5:2=2 r 1
⏐ + 5 +101
2:2=1 r 0
⏐ 12 1100
1:2=0 r 1
⏐
Maszyny podstawowe (bramki i sumatory):
Bramka NOT
:
Input (A) Output (B)
1
0
0
1
Bramka AND:
Input(A) Input(B) Output(C)
1 1 1
1 0 0
0 1 0
0 0 0
Bramka OR:
Input(A) Input(B) Output(C)
1 1 1
1 0 1
0 1 1
0 0 0
Bramka OR
Sumator dwójkowy jednopozycyjny:
Input(A) Input(B) Input(Z1) Output(C) Output(Z2)
0 0 0 0 0
0 0 1
0 1 0 1 0
1 0 0
1 1 0
0 1 1 0 1
1 0 1
1 1 1 1 1
Algorytm Euklidesa
Dane są dwie nieujemne liczby całkowite m , n . Liczba
k=NWD(m,n) jest największym wspólnym dzielnikiem m i n jeśli
dzieli m oraz n i jest największą liczbą o tej własności.
Algorytm Euklidesa znajduje największy wspólny podzielnik.
Załóżmy n
≥ m ⇒ n = q *m + r gdzie 0 ≤ r < m.
Stąd:
• Jeśli r = 0 to NWD(m,n)=m
Jeśli jedna z liczb dzieli drugą bez reszty to mniejsza z tych
liczb jest największym wspólnym dzielnikiem.
• Jeśli r ≠ 0 to r = n – q*m
Każda liczba dzieląca n i m dzieli także r
⇒
NWD(m,n)=NWD(r,m) przy czym zgodnie z punktem
pierwszym NWD(0,m) = m.
Rozważmy liczby n=48, m=46.
48=1*46+2
46=23*2+0
czyli NWD(46,48)=NWD(2,46)=NWD(0,2) = 2
Zależność n = q *m + r zapewnia, że możemy generować pary
liczb o tym samym największym wspólnym dzielniku, elementy
tych par tworzą malejący ciąg liczb naturalnych.
Ciąg ten jest skończony, na jego końcu otrzymujemy szukany
dzielnik.