dowód

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Kowal1998
Czasem tu bywam
Czasem tu bywam
Posty: 122
Rejestracja: 18 lis 2017, 21:17
Podziękowania: 40 razy
Otrzymane podziękowania: 1 raz
Płeć:

dowód

Post autor: Kowal1998 »

1.Uzasadnij poprawność tego algorytmu.
2.Co prawda w algorytmie działamy na liczbach zapisanych w sytemie dziesiętnym, ale istnieje związek tego algorytmu z rozwinięciem dwójkowym. Spróbuj opisać ten związek.

Algorytm mnożenia chłopów rosyjskich
Tradycyjny algorytm mnożenia, tzw. mnożenie pisemne, wymaga znajomo- ści tabliczki mnożenia w zakresie 100. Przedstawimy pewien efektywny algo- rytm mnożenia wymagający jedynie umiejętności mnożenia i dzielenia przez 2. Według niektórych źródeł algorytm ten miał być używany przez chłopów rosyjskich w XIX wieku. Inni nazywają go mnożeniem etiopskim. Niewąt- pliwie przypomina algorytm mnożenia opisany w papirusach staroegipskich, choć różni się od niego w pewnych aspektach.

Dane są dwie liczby całkowite dodatnie a i b. Chcemy obliczyć iloczyn ab. W tym celu stworzymy tabelę o dwóch kolumnach. W pierwszym wierszu tabeli wpiszemy w kolumny czynniki a i b. Każdy następny wiersz tabeli powstaje z poprzedniego przez dzielenie całkowite przez 2 w lewej kolumnie i przez mnożenie przez 2 w prawej kolumnie. Procedurę kontynuujemy aż do uzyskania 1 w lewej kolumnie. Następnie wykreślamy wszystkie wiersze tabeli, w których liczba w lewej kolumnie jest parzysta. Poszukiwany iloczyn jest sumą liczb z prawej kolumny.
Przykład: obliczenie iloczynu
37 × 41.
37 41
18 82
9 164
4 328
2 656
1 1312

Stąd 37×41 = 41+164+1312= 1517.
kerajs
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re: dowód

Post autor: kerajs »

\(37=1+4+32=1+2^2+2^5\\
37 \cdot 41=(1+4+32)\cdot 41=41+164+1312= 1517\)
Kowal1998
Czasem tu bywam
Czasem tu bywam
Posty: 122
Rejestracja: 18 lis 2017, 21:17
Podziękowania: 40 razy
Otrzymane podziękowania: 1 raz
Płeć:

Re: dowód

Post autor: Kowal1998 »

A taki bardziej formalny dowód przy użyciu litereczek?
kerajs
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re: dowód

Post autor: kerajs »

S'il vous plaît :
Niech \(2^k \le a <2^{k+1}\)
Liczbę a przedstawiam jako sumę potęg dwójki:
\(a= \sum_{i=0}^{k} \left[ \left( \lceil \frac{a}{2^i} \rceil \mod 2\right) \cdot 2^i\right] \)
a wtedy szukany iloczyn to:
\(ab=b \cdot \sum_{i=0}^{k} \left[ \left( \lceil \frac{a}{2^i} \rceil \mod 2\right) \cdot 2^i\right] =
\sum_{i=0}^{k} \left[ \left( \lceil \frac{a}{2^i} \rceil \mod 2\right) \cdot 2^ib\right]\)
ODPOWIEDZ