Mnożenie chłopów rosyjskich dowód kaniaramia: 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.