Завязан с алгоритмом косвенного умножения - PullRequest
Новая
       42

Завязан с алгоритмом косвенного умножения

0 голосов
/ 19 декабря 2018

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

Вопрос:

Два целых числа p и q можно косвенно умножить следующим способом:

Если ожидаемый продукт равен r (изначально 0), тогда, если q нечетное p добавляется к r и q уменьшается на 1, если q четное p удваиваетсяи добавляется к r и q , делится пополам (т.е. q становится q / 2)

Itдалее утверждается, что косвенное умножение используется в цифровых компьютерах, в которых прямое умножение стоит дорого

И, пытаясь часами, мне удалось найти итеративный и рекурсивный алгоритм, но они не идеальны.

Итеративный 

int multiply(int p, int q){
    int r=0;
    while(q!=0){
        if(q%2==1){
            r += p;
            q--;
        }
        else{
            r += 2*p;
            q = q/2;
        }
    }
    return r;
}

Рекурсивный 

int multiplyRec(int p, int q){
    if(q==1)
        return p;
    if(q%2==1){
        return (p + multiplyRec(p, q-1));
    }
    else{
        return (2*p + multiplyRec(p, q/2));
    }
}

Например, когда я умножаю 6 на 5, ответ в обоих алгоритмах равен 36, адолжно быть 30. Но если я изменил его таким образом, чтобы получить 30, то умножение на 1. не удастся.

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

Ответы [ 2 ]

0 голосов
/ 19 декабря 2018

Алгоритм будет работать нормально, если вы будете следовать приведенному ниже правилу вместо того, которое вы указали:

Если ожидаемый продукт равен r (изначально 0), то, если q нечетно, p добавляется кr, если q является четным, то p удваивается, а q уменьшается вдвое (т.е. q становится q / 2)

Пример кода: 

int mult(int p,int q){

int r=0;

if(q%2==1)
{
    if(q!=1)
    {
        r+=p;
        //q--;
        return r*q;
    }

    r+=p;
    return r*q;
}

else if(q%2==0)
{
    if(q!=0)
    {
        p=p*2;
        r+=p;
        q=q/2;

        return r*q;
    }

    return 0;

}}
0 голосов
/ 19 декабря 2018

Алгоритм в вашем кавычке неверен.Должно быть:

Если ожидаемый продукт равен r (изначально 0), то, если q нечетно, p добавляется к r, а q уменьшается на 1, если q равно четному, p удваивается, а qв два раза (т.е. q становится q / 2)

То есть, когда q четное, вы просто удваиваете p, вы НЕ добавляете его к r.

Также отсутствуетусловие неявного завершения q == 0

Это соответствует простой двоичной длинной мультипликации - для каждого 1 бита в q вы добавляете p влево, смещенную на позицию 1 бита;для каждого 0 бита в q вы ничего не делаете.

Это обычно записывается как 

while (q != 0) {
    if (q & 1)  // q is odd
        r += p;
    p *= 2;
    q /= 2;
}

Это потому, что когда q нечетно, вычитание 1 сделает его четным, так что вы можете сразу сделатьСледующий шаг удвоения р и деления пополам д.Поскольку целочисленное деление округляется в меньшую сторону, деление нечетного числа на 2 также делает неявное значение -1. ​​

...