Умножение с использованием рекурсивной функции C ++ - PullRequest
Новая
       50

Умножение с использованием рекурсивной функции C ++

1 голос
/ 01 августа 2020

Я выполнил рекурсивную функцию для вычисления x * y с x и y целыми числами (x и y> = 0). Моя формула: x * y =

  • 0 , если x равно 0
  • (x >> 1 ) * (y << 1) </strong>, если x - четное число
  • (x >> 1) * (y << 1) + y </strong>, если x - нечетное число

«<<» и «>>» - побитовые операторы сдвига влево и вправо. Вот мой код: 

int multiply(int x, int y) {
    int y1 = 0;
    if (x == 0) return 0;
    else if (x % 3 == 0) {
        y1 = y;
        x = x >> 1;
        y = y << 1;
        return (multiply(x, y) + y1);
    }
    else if (x % 2 == 0) {
        x = x >> 1;
        y = y << 1;
        return multiply(x, y);
    }
}

Рекурсивная функция выше должна возвращать значение (x * y), но все они были неправильными, когда я тестировал, и я не знаю почему. Что я сделал не так? Как я могу это исправить?

Ответы [ 3 ]

3 голосов
/ 01 августа 2020

Ваша проблема с x % 3, что будет, если x = 5? вы пропустите это. Вот улучшенная версия вашего кода. 

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    else if (x % 2 == 1)
        return (multiply(x >> 1, y << 1) + y);

    return multiply(x >> 1, y << 1);
}

или, может быть, даже это: 

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    int m = multiply(x >> 1, y << 1);

    if (x % 2 == 1)
        m += y;

    return m;
}

Вот супербыстрая версия, предложенная Энди: 

int multiply(int x, int y) {
    if (x == 0)
        return 0;
    int m = multiply(x >> 1, y << 1);

    if (x & 1)
        m += y;

    return m;
}

В качестве проблемы скорости, вот нерекурсивная версия: 

int multiply (int x, int y) {
    int y1 = 0;
    for (; x > 0; x = (x >> 1), y = (y << 1)) 
        if (x&1) 
            y1 += y;

    return y1; 
}

ПРИМЕЧАНИЕ. Я знаю, что этот вопрос касается рекурсивного метода, но в качестве проблемы я написал нерекурсивный алгоритм.

2 голосов
/ 01 августа 2020

Вы не проверяете, правильно ли x нечетное здесь: 

else if (x % 3 == 0) {  // e.g. fails on x = 1

Вместо этого вам нужно сделать 

else if (x % 2 == 1) {

Вот демонстрация .

Обратите внимание, что это делает следующую else проверку на четные значения x избыточной: 

else if (x % 2 == 0) {  // can just be an unconditional else

Кроме того, поскольку вы возвращаетесь из x == 0 и x % 2 == 1 ветки, условия else также могут быть удалены. Вы также можете исключить повторяющийся код, чтобы упростить функцию, например: 

int multiply(int x, int y) {
    if (x == 0) return 0;
    if (x % 2 == 1) 
        return (multiply(x >> 1, y << 1) + y);
    else 
        return multiply(x >> 1, y << 1); 
}

Вот демонстрация .

1 голос
/ 01 августа 2020

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

#include<iostream>
using namespace std;
 
float multiply(float a, float b) {
 
    //no zeros bro
    if (b == 0)
        return 0;
 
    //let the recursion begin
    if (b > 0)
        return x + multiply(a, b - 1);
 
    //negatives stay away pliz
    if (y < 0)
        return -multiply(a, -b);
}
 
int main() {
    float a, b, result;
    cout << "Enter the two numbers";
    cin >> a >> b;
 
    result = multiply(a, b);
 
    //And the result is.................
    cout << result;
    return 0;
}
...