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.
dowód
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 2963
- Rejestracja: 14 lis 2016, 14:38
- Podziękowania: 33 razy
- Otrzymane podziękowania: 1303 razy
- Płeć:
Re: dowód
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]\)
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]\)