Квестон на Карацубе Рекурсия - PullRequest
Новая
       14

Квестон на Карацубе Рекурсия

0 голосов
/ 23 мая 2018

Я пытаюсь реализовать рекурсивный алгоритм Карацубы.Я успешно написал рекурсивный алгоритм для умножения, но он вычисляет ad и bc.Однако для этой программы я попытался записать каждое промежуточное значение, а именно: ac, bd, total, sum.Многие значения не отображаются в качестве ожидаемого значения.Я не могу понять, где мой код испортился.Я все еще программист-любитель, и я потратил уже несколько часов, пытаясь отлаживать, но теперь у меня нет выбора, кроме как разместить мой большой код здесь: 

#include <iostream>
using namespace std;

int approxLog(int n, int b) {
    return !(n/b < 1) ? 1+approxLog(n/b, b) : 1;
}

int power(int b, int e) {
    return (e < 1) ? 1 : b*power(b, e-1);
}

int odd1(int n) {
    if(n%2 != 0)
        return n-1;
    else
        return n;
}

int odd2(int n) {
    if(n%2 == 0)
        return n/2;
    else
        return n/2 + 1;
}

void num_split (int num, int d, int *a, int *b) {
    int  i = 1, tmp = 0, j = 1, k = 0;
    while (i <= d/2) {
        tmp += (num%10)*power(10, i-1);
        num /= 10;
        i++;
    }
    *b = tmp;
    tmp = 0;
    while (i <= d) {
        tmp += (num%10)*power(10, j-1);
        num /= 10;
        i++;
        j++;
    }
    *a = tmp;
    tmp = 0;
}

long long int multiply(int x, int y, int n) {
    int a = 0, b = 0, c = 0, d = 0;
    int ac = 0, bd = 0, total = 0, sum = 0;
    int *ptr_a = &a;
    int *ptr_b = &b;
    int *ptr_c = &c;
    int *ptr_d = &d;
    num_split(x, n, ptr_a, ptr_b);
    num_split(y, n, ptr_c, ptr_d);

    if((x < 10) || (y < 10)) {
        return x*y;
    }
    else {
        ac = multiply(a, c, odd2(n));
        bd = multiply(b, d, n/2);
        total = multiply((a+b), (c+d), odd2(n));
        // cout << total <<  endl;
        sum = total - ac - bd;
        return power(10, odd1(n))*ac + power(10, n/2))*sum + bd;
    }
}

int main() {
    int x = 1234, y = 1234;
    int n = approxLog(x, 10);
    long long int product = multiply(x, y, n);
    cout << product << endl;

    return 0;
}

1 Ответ

0 голосов
/ 23 мая 2018

Проблема в том, что в каждой рекурсии вы должны брать ок.журнал из более крупных x и y.Таким образом, следующее изменение в вашем коде решит проблему (обратите внимание также на закомментированные части!): 

long long int multiply(int x, int y)//, int n)
{
    int a = 0, b = 0, c = 0, d = 0;
    int ac = 0, bd = 0, total = 0, sum = 0;
    int *ptr_a = &a;
    int *ptr_b = &b;
    int *ptr_c = &c;
    int *ptr_d = &d;
    int n = (x>y)?approxLog(x, 10):approxLog(y, 10);
    num_split(x, n, ptr_a, ptr_b);
    num_split(y, n, ptr_c, ptr_d);

    if((x < 10) || (y < 10)) {
        return x*y;
    }
    else {
        ac = multiply(a, c);//, odd2(n));
        bd = multiply(b, d);//, n/2);
        total = multiply((a+b), (c+d));//, odd2(n));
        cout << total <<  endl;
        sum = total - ac - bd;
        return power(10, odd1(n))*ac + power(10, (n/2))*sum + bd;
    }
}

int main() {
    int x = 134546, y = 1234;
    //int n = approxLog(x, 10);
    long long int product = multiply(x, y);//, n);
    cout<<"Karatsuba: "<<product<<endl;
    cout<<"Normal:    "<<x*y<<endl;

    return 0;
}
...