Karatsuba 乘法演算法實作不輸出任何結果并以 code=3221225725 退出。
這是終端上顯示的訊息：
[Running] cd "d:\algorithms_cpp\" && g karatsube_mul.cpp -o karatsube_mul && "d:\algorithms_cpp\"karatsube_mul
[Done] exited with code=3221225725 in 1.941 seconds
這是代碼：
#include <bits/stdc .h>
using namespace std;
string kara_mul(string n, string m)
{
int len_n = n.size();
int len_m = m.size();
if (len_n == 1 && len_m == 1)
{
return to_string((stol(n) * stol(m)));
}
string a = n.substr(0, len_n / 2);
string b = n.substr(len_n / 2);
string c = m.substr(0, len_m / 2);
string d = m.substr(len_m / 2);
string p1 = kara_mul(a, c);
string p2 = kara_mul(b, d);
string p3 = to_string((stol(kara_mul(a b, c d)) - stol(p1) - stol(p2)));
return to_string((stol(p1 string(len_n, '0')) stol(p2) stol(p3 string(len_n / 2, '0'))));
}
int main()
{
cout << kara_mul("15", "12") << "\n";
return 0;
}
在解決這個問題后，我還想知道如何使用這種技術將兩個 664 位整數相乘。
uj5u.com熱心網友回復：
有幾個問題：
你得到的例外是由這個呼叫的無限遞回引起的：
kara_mul(a b, c d)由于這些變數是字串，因此
n和m，它們是函式當前執行的引數。正確的演算法將在此處執行數字加法，您需要為此提供實作（添加兩個可能非常長的整數的字串表示形式）
if (len_n == 1 && len_m == 1)檢測基本情況，但是當這些大小中的任何一個為 1 時，基本情況應該啟動，而不是兩者都必須。所以這應該是一個||運算子，或者應該寫成兩個單獨的if陳述句。輸入字串應該被拆分，使得
b和d大小相等。這不是您的代碼所做的。請注意Wikipedia 文章如何強調這一點：split_at 函式的第二個引數指定要從右邊提取的位數
stol永遠不應在可能太長而無法轉換為的字串上呼叫long. 因此，例如，stol(p1)不安全，因為p1可能有 20 位或更多位。作為前一點的結果，您需要實作對數字的兩個字串表示形式相加或相減的函式，以及一個可以將字串表示形式與單個數字相乘的函式（基本情況）。
這是一個糾正這些問題的實作：
#include <iostream>
#include <algorithm>
int digit(std::string n, int i) {
return i >= n.size() ? 0 : n[n.size() - i - 1] - '0';
}
std::string add(std::string n, std::string m) {
int len = std::max(n.size(), m.size());
std::string result;
int carry = 0;
for (int i = 0; i < len; i ) {
int sum = digit(n, i) digit(m, i) carry;
result = (char) (sum % 10 '0');
carry = sum >= 10;
}
if (carry) result = '1';
reverse(result.begin(), result.end());
return result;
}
std::string subtract(std::string n, std::string m) {
int len = n.size();
if (m.size() > len) throw std::invalid_argument("subtraction overflow");
if (n == m) return "0";
std::string result;
int carry = 0;
for (int i = 0; i < len; i ) {
int diff = digit(n, i) - digit(m, i) - carry;
carry = diff < 0;
result = (char) (diff carry * 10 '0');
}
if (carry) throw std::invalid_argument("subtraction overflow");
result.erase(result.find_last_not_of('0') 1);
reverse(result.begin(), result.end());
return result;
}
std::string simple_mul(std::string n, int coefficient) {
if (coefficient < 2) return coefficient ? n : "0";
std::string result = simple_mul(add(n, n), coefficient / 2);
return coefficient % 2 ? add(result, n) : result;
}
std::string kara_mul(std::string n, std::string m) {
int len_n = n.size();
int len_m = m.size();
if (len_n == 1) return simple_mul(m, digit(n, 0));
if (len_m == 1) return simple_mul(n, digit(m, 0));
int len_min2 = std::min(len_n, len_m) / 2;
std::string a = n.substr(0, len_n - len_min2);
std::string b = n.substr(len_n - len_min2);
std::string c = m.substr(0, len_m - len_min2);
std::string d = m.substr(len_m - len_min2);
std::string p1 = kara_mul(a, c);
std::string p2 = kara_mul(b, d);
std::string p3 = subtract(kara_mul(add(a, b), add(c, d)), add(p1, p2));
return add(add(p1 std::string(len_min2*2, '0'), p2), p3 std::string(len_min2, '0'));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482716.html
上一篇：如何將陣列的大O時間復雜度與索引找到的值與陣列切片進行比較
下一篇：合并兩個排序串列時輸出錯誤