そこで、C ++でカラツバのアルゴリズムを実装することにしました(生前の2番目のコーディングクラス以来、この言語を使用していないので、非常に錆びています)。とにかく、私は疑似コードを1行ずつ追跡したと思いますが、それでも私のアルゴリズムは間違った答えでポップアップし続けます。
x = 1234, y = 5678
Actual Answer: x*y ==> 7006652
Program output: x*y ==> 12272852
*注:私はMacで実行しており、実行する実行可能ファイルを作成するために以下を使用しています c++ -std=c++11 -stdlib=libc++ karatsuba.cpp
とにかく、ここにドラフトされたコードがあります。私が間違っていることや、c ++を改善する方法について自由に声をかけてください。
ありがとう!
コード:
#include <iostream>
#include <tuple>
#include <cmath>
#include <math.h>
using namespace std;
/** Method signatures **/
tuple<int, int> splitHalves(int x);
int karatsuba(int x, int y, int n);
int main()
{
int x = 5678;
int y = 1234;
int xy = karatsuba(x, y, 4);
cout << xy << endl;
return 0;
}
int karatsuba(int x, int y, int n)
{
if (n == 1)
{
return x * y;
}
else
{
int a, b, c, d;
tie(a, b) = splitHalves(x);
tie(c, d) = splitHalves(y);
int p = a + b;
int q = b + c;
int ac = karatsuba(a, c, round(n / 2));
int bd = karatsuba(b, d, round(n / 2));
int pq = karatsuba(p, q, round(n / 2));
int acbd = pq - bd - ac;
return pow(10, n) * ac + pow(10, round(n / 2)) * acbd + bd;
}
}
/**
* Method taken from https://stackoverflow.com/questions/32016815/split-integer-into-two-separate-integers#answer-32017073
*/
tuple<int, int> splitHalves(int x)
{
const unsigned int Base = 10;
unsigned int divisor = Base;
while (x / divisor > divisor)
divisor *= Base;
return make_tuple(round(x / divisor), x % divisor);
}
あなたのコードにはたくさんの問題があります...
まず、ここに間違った係数があります。
int q = b + c;
である必要があります:
int q = c + d;
次に、の実装はsplitHalves
機能しません。それを試してください:
tuple<int, int> splitHalves(int x, int power)
{
int divisor = pow(10, power);
return make_tuple(x / divisor, x % divisor);
}
それはあなたの入力に対して「正しい」答えを与えるでしょう、しかし...それはカラツバ法ではありません。
まず、「半分に分割」する必要がないことを覚えておいてください。半分の最初の数字が意味する12 * 3456分割を考慮してa = 0
、b = 12
あなたの実装が与えながらa = 1
、b = 2
。
Karastubaは全体として、整数ではなく配列で機能します。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加