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 12 = 0 + 1 ←⎯⎯⎯ 1
22 = 1 + 3 ←⎯⎯⎯ 3 = 1 + 2
32 = 4 + 5 ←⎯⎯⎯ 5 = 3 + 2
42 = 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: Cn Cn-1 Cn-2 . . . C1 C0
- wartość liczby:
Cn*10n+Cn-1*10n-1+Cn-2*10n-2+ ...+C1*101+C0*100
System dwójkowy (binarny):
- cyfry: 0,1
- postać liczby: Bn Bn-1 Bn-2 . . . B1 B0
- wartość liczby:
Bn*2n+Bn-1*2n-1+Bn-2*2n-2+ ...+B1*21+B0*20
Postać binarna liczby dziesiętnej:
(13) 10= 8+4+1= 1*23+1*22+1*20 = 1*23+1*22+0*21+1*20
(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.