Швидке множення та її наслідки. Опис прикладів Швидкого множення
Ответы
Ответ:
Приклад поліноміального множення:
Припустимо, маємо два полінома:
A(x) = 3x^3 + 2x^2 + x + 5
B(x) = x^2 + 4x + 1
Застосуємо швидке множення. Розділимо поліноми на дві частини:
A(x) = 3x^3 + 2x^2 + x + 5 = 3x^2(x + 1) + (2x + 5)
B(x) = x^2 + 4x + 1 = x(x + 1) + 1
Тепер множимо ці дві частини:
A(x) * B(x) = (3x^2(x + 1) + (2x + 5)) * (x(x + 1) + 1)
Застосовуємо рекурсивний алгоритм для множення підполіномів:
A(x) * B(x) = 3x^2 * x(x + 1) + 3x^2 * 1 + (2x + 5) * x(x + 1) + (2x + 5) * 1
Виконуємо операції:
A(x) * B(x) = 3x^3 + 3x^2 + 2x^2 + 2x + 5x + 5
Об'єднуємо подібні терміни:
A(x) * B(x) = 3x^3 + 5x^2 + 7x + 5
Таким чином, результатом множення двох поліномів буде поліном C(x) = 3x^3 + 5x^2 + 7x + 5.
Приклад множення матриць:
Припустимо, маємо дві матриці:
A = | 2 3 |
| 4 1 |
B = | 5 6 |
| 7 8 |
Застосуємо швидке множення. Розділимо матриці на менші підматриці:
A = | 2 3 | B = | 5 6 |
| 4 1 | | 7 8 |
Тепер множимо ці дві підматриці:
A * B = | (2 * 5) + (3 * 7) (2 * 6) + (3 * 8) |
| (4 * 5) + (1 * 7) (4 * 6) + (1 * 8) |
Виконуємо операції:
A * B = | 29 38 |
| 39 50 |
Таким чином, результатом множення двох матриць буде матриця C = | 29 38 |
| 39 50 |