Створити проєкт футбол в скретчі. футболіст повинен рухотися відповідно до натиснутих стрілок на клавіатурі. Треба додати м'яч який буде змінювати своє положення коли футболіст доторкаеться до нього. Якщо м'яч потрапляє до воріт футболіст має крикнути Гол!!

Показать ответ

Ответ:

79869106698

03.02.2022 07:45

ответ:Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.

Представим, что есть два числа A и B длиной n в какой-то системе счисления BASE:

A = an-1an-2...a0

B = bn-1an-2...a0, где a?, b? — значение в соотв. разряде числа.

Каждое из них можно представить в виде суммы их двух частей, половинок длиной m = n / 2 (если n нечетное, то одна часть короче другой на один разряд:

A0 = am-1am-2...a0

A1 = an-1an-2...am

A = A0 + A1 * BASEm

B0 = bm-1bm-2...b0

B1 = bn-1bn-2...bm

B = B0 + B1 * BASEm

Тогда: A * B = ( A0 + A1 * BASEm ) * ( B0 + B1 * BASEm ) = A0 * B0 + A0 * B1 * BASEm + A1 * B0 * BASEm + A1 * B1 * BASE2 * m = A0 * B0 + ( A0 * B1 + A1 * B0 ) * BASEm + A1 * B1 * BASE2 * m

Здесь нужно 4 операции умножения (части формулы * BASE? * m не являются умножением, фактически указывая место записи результата, разряд). Но с другой стороны:

( A0 + A1 ) * ( B0 + B1 ) = A0 * B0 + A0 * B1 + A1 * B0 + A1 * B1

Посмотрев на выделенные части в обоих формулах. После несложных преобразований количество операций умножения можно свести к 3-м, заменив два умножения на одно и несколько операций сложения и вычитания, время выполнения которых на порядок меньше:

A0 * B1 + A1 * B0 = ( A0 + A1 ) * ( B0 + B1 ) — A0 * B0 — A1 * B1

Окончательный вид выражения:

A * B = A0 * B0 + (( A0 + A1 ) * ( B0 + B1 ) — A0 * B0 — A1 * B1 ) * BASEm + A1 * B1 * BASE2 * m

Объяснение:

0,0(0 оценок)

Ответ: