Алгоритм - Как бы вы определили минимальное количество умножений для оценки X до степени 30?

Question

В книге Алгоритмы для интервьюеров , есть такой вопрос:

Как бы вы определили минимальное количество умножений для оценки X до степени 30?

Может кто-нибудь сказать мне, что означает этот вопрос?

Что значит «оценить Х до степени 30»?

Есть два возможных значения, я думаю:

1. у нас есть X, тогда этот вопрос спрашивает меня: «Сколько умножений мне нужно, чтобы вычислить X ^ 30?».
2. У нас есть X, затем он спрашивает меня: «Что такое y, так что y ^ 30 = X, и сколько умножений нужно для вычисления y?»

Я не знаю, что из того, что я думаю, является правильным, или оно имеет 3-е значение?

Спасибо

Answer 1

Вопрос предполагает, что есть способ написать функцию:

int f(int x) { return pow(x, 30); }

, используя только умножения.

Фактически одним из способов будет следующее:

int f(int x)
{
    int y = 1;
    for (int i = 0; i < 30; i++)
        y *= x;
    return y;
}

Это использует 30 умножений.

Однако учтите это:

int f(int x)
{
    int z = x*x;
    int y = 1;
    for (int i = 0; i < 15; i++)
        y *= z;
    return y;
}

Это использует 16 умножений.

Таким образом, вопрос заключается в том, каково минимальное количество умноженийвозможно?

Вот 6 умножений, и, вероятно, идеальное решение для интервьюеров:

int f(int x)
{
    x_3 = x * x * x;
    x_6 = x_3 * x_3;
    x_12 = x_6 * x_6
    x_24 = x_12 * x_12
    return x_24 * x_6
}

Это скорее головоломка, чем проблема программирования.Реальная степенная функция не использует умножение (или, по крайней мере, не так, как подразумевается в вопросе)

Answer 2

Обычный способ сделать это с повторным удвоением, которое, как показали другие люди, занимает 7 умножений. В зависимости от числа, однако, это может быть сделано с меньшим умножением. В этом случае вы можете сделать это всего за 6:

x3 = x * x * x
x6 = x3 * x3
x12 = x6 * x6
x24 = x12 * x12
x30 = x24 * x6

Answer 3

Хех, забавная нота - технически, ответ на вопрос «ноль».Вы можете использовать нулевое умножение, предполагая, что мы работаем с числами с плавающей запятой, двойными числами, целыми числами и т. Д. В конце концов, вы можете эмулировать любую из этих операций с помощью просто целочисленной математики, а вы можете эмулировать целочисленную математику с приращением / уменьшением.Итак, вот версия для целых чисел, которая использует только приращение (и сравнения):

// This runs faster than you might think -- this gets optimized fairly well by GCC.

int fakeUnsignedIntegerAdd(int a, int b)
{
    int i = 0, c = a;
    for (; i < b; i++, c++);
    return c;
}

int fakeUnsignedIntegerMul(int a, int b)
{
    int i = 0, c = 0;
    for (; i < b; i++, c = fakeUnsignedIntegerAdd(c, a));
    return c;
}

int fakeUnsignedIntegerPow(unsigned int b, unsigned int e)
{
    int i = 0, c = 1;
    for (; i < e; i++, c = fakeUnsignedIntegerMul(c, b));
    return c;
}

int main()
{
    printf("%i\n", fakeUnsignedIntegerPow(2, 30));
    return 0;
}

... Хотя это, вероятно, не то, что они имели в виду.Или, может быть, это так - некоторые вопросы интервью намеренно вводят в заблуждение, чтобы понять, насколько вы «проницательны».

Answer 4

В случае x ^ 30 есть хороший специальный метод - только 6 умножений: http://en.wikipedia.org/wiki/Addition-chain_exponentiation. В большинстве случаев достаточно возведения в квадрат по квадрату.

Answer 5

Я думаю, что это будет первым, и вы можете использовать возведение в степень, возводя в квадрат, чтобы уменьшить количество умножений на основе названия книги.

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Answer 6

Вычисление по квадрату - хороший, общий алгоритм, но он даст вам 7 умножений.Эта конкретная проблема может быть решена с помощью 6:

x2 = x*x
x3 = x2*x
x5 = x2*x3
x10 = x5*x5
x20 = x10*x10
x30 = x20*x10